Rating and Generating Sudoku Puzzles Based On Constraint Satisfaction Problems

Authors: Bahare Fatemi, Seyed Mehran Kazemi, Nazanin Mehrasa

Abstract:

Sudoku is a logic-based combinatorial puzzle game which people in different ages enjoy playing it. The challenging and addictive nature of this game has made it a ubiquitous game. Most magazines, newspapers, puzzle books, etc. publish lots of Sudoku puzzles every day. These puzzles often come in different levels of difficulty so that all people, from beginner to expert, can play the game and enjoy it. Generating puzzles with different levels of difficulty is a major concern of Sudoku designers. There are several works in the literature which propose ways of generating puzzles having a desirable level of difficulty. In this paper, we propose a method based on constraint satisfaction problems to evaluate the difficulty of the Sudoku puzzles. Then we propose a hill climbing method to generate puzzles with different levels of difficulty. Whereas other methods are usually capable of generating puzzles with only few number of difficulty levels, our method can be used to generate puzzles with arbitrary number of different difficulty levels. We test our method by generating puzzles with different levels of difficulty and having a group of 15 people solve all the puzzles and recording the time they spend for each puzzle.

Keywords: Constraint satisfaction problem, generating Sudoku puzzles, hill climbing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1096421

References:

[1] R. Lewis, "Metaheuristics can solve sudoku puzzles,” Journal of heuristics, vol. 13, no. 4, pp. 387–401, 2007.
[2] H. Poor, An Introduction to Signal Detection and Estimation. New York: Springer-Verlag, 1985, ch. 4.
[3] Y. Takayuki and S. Takahiro, "Complexity and completeness of finding another solution and its application to puzzles,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003.
[4] M. R. Garey and D. S. Johnson, Computers and intractability, vol. 174. Freeman New York, 1979.
[5] T. Mantere and J. Koljonen, "Solving and rating Sudoku puzzles with genetic algorithms,” in New Developments in Artificial Intelligence and the Semantic Web, Proceedings of the 12th Finnish Artificial Intelligence Conference STeP, pp. 86–92, 2006.
[6] S. M. Kazemi, B. Fatemi, "A retrievable genetic algorithm for efficient solving of Sudoku puzzles,” International Journal of Computer, Information Science and Engineering, Vol. 8, No. 5, 2014.
[7] K. N. Das, S. Bhatia, S. Puri, and K. Deep, "A retrievable GA for solving Sudoku puzzles,” Citeseer, 2012.
[8] T. Boothby, L. Svec, and T. Zhang, "Generating sudoku puzzles as an inverse problem,” Mathematical contest in modeling, 2008.
[9] C. Chang, Z. Fan, and Y. Sun, "A Difficulty Metric and Puzzle Generator for Sudoku,” UMAPJournal, p. 305, 2007.
[10] Y. Xue, B. Jiang, Y. Li, G. Yan, and H. Sun, "Sudoku puzzles generating: from easy to evil,” Mathematics in practice and theory, vol. 21, p. 000, 2009.
[11] D. L. Poole and A. K. Mackworth, Artificial Intelligence: foundations of computational agents. Cambridge University Press, 2010.
[12] S. J. Russell, P. Norvig, J. F. Canny, J. M. Malik, and D. D. Edwards, Artificial intelligence: a modern approach, vol. 74. Prentice hall Englewood Cliffs, 1995.