Metaheuristics can solve sudoku puzzles

Article English OPEN
Lewis, Rhyd (2007)

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.
  • References (10)

    Kirkpatrick, S., C. Gelatt, and M. Vecchi. (1983). 'Optimization by Simulated Annealing.' Science 4598, 671- 680.

    Lourenco, H. R., O. Martin, and T. Stützle. (2002). 'Iterated Local Search.' In F. Glover and G. Kochenberger, (eds.) Handbook of Metaheuristics. Norwel, MA: Kluwer Academic Publishers. 321 - 353 Lynce, I. and Ouaknine. (2006). 'Sudoku as a SAT problem' In proceedings of the 9th Symposium on Artificial Intelligence and Mathematics, 2006.

    Pendlebury, P. (2005). 'Can you Sudoku'. Article appearing in The Mail on Sunday, London, 8th May 2005. An online version is also available at the following address (accessed July 2005) http://www.mailonsunday.co.uk/pages/live/articles/news/news.html?in_article_id=348348&in_page_id =1770&in_a_source=

    Ross, P, D. Corne, and H-L. Fang. (1994). 'Improving Evolutionary Timetabling with Delta Evaluation and Directed Mutation.' In Y. Davidor, H. Schwefel, M. Reinhard (eds.) Parallel Problem Solving From Nature III (PPSN) Springer-Verlag LNCS 866, 556 - 565.

    Ross, P., D. Corne, and H. Terashima-Marin. (1996). 'The Phase-Transition Niche for Evolutionary Algorithms in Timetabling.' In Edmund Burke and Peter Ross (eds.) The Practice and Theory of Automated Timetabling (PATAT), Springer-Verlag LNCS 1153, 309 - 325.

    Simonis, H. (2005). 'Sudoku as a Constraint Problem'. In CP Workshop on Modelling and Reformulating Constraint Satisfaction Problems, pages 13-27, Spain, October 2005.

    Smith, B. (1994) 'Phase Transitions and the Mushy Region in Constraint Satisfaction Problems'. In A. Cohn (ed) Proceedings of the 11th European Conference on Artificial Intelligence, John Wiley and Sons Ltd, 100 - 104.

    Turner, J. S. (1988). 'Almost all k-Colorable Graphs are Easy to Color.' Journal of Algorithms, 9, 63 - 82.

    van Laarhoven, P, E. Aarts. (1987). Simulated Annealing: Theory and Applications. D. Reidel Publishing Company, The Netherlands.

    Yato, T. and T. Seta. (2003). 'Complexity and Completeness of Finding Another Solution and Its Application to Puzzles'. IEICE Trans. Fundamentals, Vol. E86-A, No. 5, pp. 1052-1060.

  • Metrics
    No metrics available
Share - Bookmark