Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Metaheuristics can solve sudoku puzzles

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2007. Metaheuristics can solve sudoku puzzles. Journal of Heuristics 13 (4) , pp. 387-401. 10.1007/s10732-007-9012-8

[thumbnail of LEWIS metaheuristics can solve sudoku puzzles.pdf]
Preview
PDF - Accepted Post-Print Version
Download (278kB) | Preview

Abstract

In this paper we present, to our knowledge, the first application of a metaheuristic technique to the very popular and NP-complete puzzle known as ‘sudoku’. We see that this stochastic search-based algorithm, which uses simulated annealing, is able to complete logic-solvable puzzle-instances that feature daily in many of the UK’s national newspapers. We also introduce a new method for producing sudoku problem instances (that are not necessarily logic-solvable) and use this together with the proposed SA algorithm to try and discover for what types of instances this algorithm is best suited. Consequently we notice the presence of an ‘easy-hard-easy’ style phase-transition similar to other problems encountered in operational research.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: Metaheuristics; Sudoku; Puzzles; Phase-transition
Additional Information: Pdf uploaded in accordance with the publisher’s policy at http://www.sherpa.ac.uk/romeo/issn/1381-1231/ (accessed 07/08/2014)
Publisher: Springer
ISSN: 1381-1231
Date of First Compliant Deposit: 30 March 2016
Last Modified: 07 Nov 2023 00:16
URI: https://orca.cardiff.ac.uk/id/eprint/27746

Citation Data

Cited 75 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics