caa a22 4500 463202767 CHVBK 20180405153116.0 cr unu---uuuuu 170326e20070801xx s 000 0 eng 10.1007/s10732-007-9012-8 doi (NATIONALLICENCE)springer-10.1007/s10732-007-9012-8 Lewis Rhyd Centre for Emergent Computing, School of Computing, Napier University, EH10 5DT, Edinburgh, Scotland, UK aut Metaheuristics can solve sudoku puzzles [Elektronische Daten] [Rhyd Lewis] 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. Springer Science+Business Media, LLC, 2007 Metaheuristics nationallicence Sudoku nationallicence Puzzles nationallicence Phase-transition nationallicence Journal of Heuristics Kluwer Academic Publishers-Plenum Publishers; http://www.springer-ny.com 13/4(2007-08-01), 387-401 1381-1231 13:4<387 2007 13 10732 https://doi.org/10.1007/s10732-007-9012-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10732-007-9012-8 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lewis Rhyd Centre for Emergent Computing, School of Computing, Napier University, EH10 5DT, Edinburgh, Scotland, UK aut NATIONALLICENCE 773 0- Journal of Heuristics Kluwer Academic Publishers-Plenum Publishers; http://www.springer-ny.com 13/4(2007-08-01), 387-401 1381-1231 13:4<387 2007 13 10732 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer