Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Lewis, Rhyd (2007)
Publisher: Springer
Languages: English
Types: Article
Subjects: QA, QA75
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article