Skip to main content
SpringerLink
Log in

A comparison of several enumerative algorithms for Sudoku

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

Sudoku is a puzzle played of an n × n grid where n is the square of a positive integer m. The most common size is n=9. The grid is partitioned into n subgrids of size m × m. The player must place exactly one number from the set N={1, …, n} in each row and each column of as well as in each subgrid. A grid is provided with some numbers already in place, called givens. In this paper, some relationships between Sudoku and several operations research problems are presented. We model the problem by means of two mathematical programming formulations. The first one consists of an integer linear programming model, while the second one is a tighter non-linear integer programming formulation. We then describe several enumerative algorithms to solve the puzzle and compare their relative efficiencies. Two basic backtracking algorithms are first described for the general Sudoku. We then solve both formulations by means of constraint programming. Computational experiments are performed to compare the efficiency and effectiveness of the proposed algorithms. Our implementation of a backtracking algorithm can solve most benchmark instances of size 9 within 0.02 s, while no such instance was solved within that time by any other method. Our implementation is also much faster than an existing alternative algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Applegate DL and Cook WJ (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing 30 (2): 149–156.

    Article  Google Scholar 

  • Apt K (2003). Principles of Constraint Programming. Cambridge University Press: Cambridge.

    Book  Google Scholar 

  • Bartlett AC and Langville AN (2006). An integer programming model for the Sudoku problem. http://www.cofc.edu/~langvillea/Sudoku/sudoku2.pdf, accessed 21 May 2013.

  • Colbourn CJ, Colbourn MJ and Stinson DR (1984). The computational complexity of recognizing critical sets. In: Koh K and Yap H (eds). Graph Theory Singapore 1983, Volume 1073 of Lecture Notes in Mathematics. Springer: Heidelberg: pp 248–253.

    Google Scholar 

  • Dànes J and Keedwell AD (1974). Latin Squares and their Applications. English Universities Press: London.

    Google Scholar 

  • Felgenhauer B and Jarvis F (2005). Enumerating possible Sudoku grids. http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf, accessed 7 January 2013.

  • Garns H (1979). Number place. Dell Pencil Puzzles & Word Games (16): 6.

  • Golomb SW and Baumert LD (1965). Backtrack programming. Journal of the ACM 120 (4): 516–524.

    Article  Google Scholar 

  • Higgins A, Kozan E and Ferreira L (1996). Optimal scheduling of trains on a single line track. Transportation Research Part B: Methodological 300 (2): 147–161.

    Article  Google Scholar 

  • Jensen TR and Toft B (1994). Graph Coloring Problems. Vol. 39. Wiley-Interscience: New York.

    Book  Google Scholar 

  • Laporte G and Pesant G (2004). A general multi-shift scheduling system. Journal of the Operational Research Society 55 (11): 1208–1217.

    Article  Google Scholar 

  • Lewis R (2007a). On the combination of constraint programming and stochastic search: The Sudoku case. http://rhydlewis.eu/papers/HM2007.pdf, accessed 7 January 2013.

  • Lewis R (2007b). Metaheuristics can solve Sudoku puzzles. Journal of Heuristics 130 (4): 387–401.

    Article  Google Scholar 

  • Lustig IJ and Puget J-F (2001). Program does not equal program: Constraint programming and its relationship to mathematical programming. Interfaces 310 (6): 29–53.

    Article  Google Scholar 

  • Mantere T and Koljonen J (2006). Solving and rating Sudoku puzzles with genetic algorithms. In: Hyvönen E, Kauppinen T, Kortela J, Raiko T, Laukkanen M and Viljanen K (eds). New Developments in Artificial Intelligence and the Semantic Web-Proceedings of the 12th Finnish Artificial Conference. Finnish Artificial Intelligence Society: Espoo, Finland: pp 86–92.

    Google Scholar 

  • Mantere T and Koljonen J (2007). Solving, rating and generating Sudoku puzzles with GA. In: 2007 IEEE Congress on Evolutionary Computation. IEEE: Singapore, pp 1382-1389.

  • McGuire G, Tugemann B and Civario G (2012). There is no 16-clue Sudoku: Solving the Sudoku minimum number of clues problem. http://arxiv.org/pdf/1201.0749v1.pdf, accessed 7 January 2013.

  • Naveh Y, Richter Y, Altshuler Y, Gresh DL and Connors DP (2007). Workforce optimization: Identification and assignment of professional workers using constraint programming. IBM Journal of Research and Development 51 (3.4): 263–279.

    Article  Google Scholar 

  • Rodgers JL and Nicewander WA (1988). Thirteen ways to look at the correlation coefficient. The American Statistician 420 (1): 59–66.

    Article  Google Scholar 

  • Rossi F, Van Beek P and Walsh T (2006). Handbook of Constraint Programming. Vol. 2. Elsevier: Amsterdam.

    Google Scholar 

  • Royle G. Sudoku dataset: 49151 instances with 17 givens, University of Western Australia. http://school.maths.uwa.edu.au/~gordon/sudokumin.php, accessed 20 September 2013.

  • Russell E and Jarvis F (2005). There are 5472730538 essentially different Sudoku grids. http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html, accessed 30 May 2013.

  • Sellmann M, Zervoudakis K, Stamatopoulos P and Fahle T (2002). Crew assignment via constraint programming: Integrating column generation and heuristic tree search. Annals of Operations Research 1150 (1): 207–225.

    Article  Google Scholar 

  • Simonis H (2005). Sudoku as a constraint program. http://4c.ucc.ie/~hsimonis/sudoku.pdf, accessed 7 January 2013.

  • Tadei R and Mancini S (2006). Sudoku game theory, models and algorithms. http://www.polito.it/polymath/htmlS/Studenti/Tesi/SudokuGame/tesi_Mancini_Simona%20SUDOKU.pdf, accessed 21 May 2013.

  • Takayuki Y and Takahiro S (2003). Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 860 (5): 1052–1060.

    Google Scholar 

  • Walker RJ (1960). An enumerative technique for a class of combinatorial problems. In: Bellman RE and Hall M (eds) Proceedings of Symposia in Applied Mathematics. American Mathematical Society: Providence, RI. Vol. 10, pp 91–94.

Download references

Acknowledgements

The authors thank the associate editor and the anonymous referees for their valuable comments. This work was partly supported by the Canadian Natural Sciences and Engineering Research Council under grant 39682-10. This support is gratefully acknowledged.

Author information

Authors and Affiliations

  1. CIRRELT—Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Québec, Canada

    Leandro C Coelho & Gilbert Laporte

  2. Université Laval, Québec, Canada

    Leandro C Coelho

  3. HEC Montréal, Montréal, Canada

    Gilbert Laporte

Authors
  1. Leandro C Coelho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gilbert Laporte
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Coelho, L., Laporte, G. A comparison of several enumerative algorithms for Sudoku. J Oper Res Soc 65, 1602–1610 (2014). https://doi.org/10.1057/jors.2013.114

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2013.114

Keywords

Search

Navigation