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

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:	08 Jan 2025 12:45
URI:	https://orca.cardiff.ac.uk/id/eprint/27746

Citation Data

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

Actions (repository staff only)

Edit Item