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

Metaheuristics can solve sudoku puzzles

Lewis, Rhyd 2007. Metaheuristics can solve sudoku puzzles. Journal of Heuristics 13 (4) , pp. 387-401. 10.1007/s10732-007-9012-8

[img]
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
Last Modified: 04 Jun 2017 07:08
URI: http://orca.cf.ac.uk/id/eprint/27746

Citation Data

Cited 90 times in Google Scholar. View in Google Scholar

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

Cited 15 times in Web of Science. View in Web of Science.

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics