Rating and Generating Sudoku Puzzles Based On Constraint Satisfaction Problems

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.

• Bahare Fatemi
• Seyed Mehran Kazemi
• Nazanin Mehrasa

• Constraint satisfaction problem
• generating Sudoku puzzles
• hill climbing.

[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.