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.