Page 5 of 24 Control #2858 unique solution. As there is no objective scale in difficulty and no fixed criteria that indicate the difference between puzzles of varying difficulties, we will interpret the given numbe of difficulty levels and the desired difficulty level as the division of the set of all Sudoku boards into the given number of difficulty percentile intervals of equal size and the choice of a particular desired percentile interval. We will take a sample of 1000 Sudoku boards and assume that the difficulty distribution of these boards, as measured by our human solver representative of the difficulty distribution of all Sudoku board Our second goal in puzzle generation is to minimize the complexity of the generation algorithm. We note that since the size of the 9 x 9 Sudoku board is fixed. the order of growth of our generation algorithm is irrelevant. Therefore, in this paper, we will interpret the complexity of a generation algorithm to be the expected amount of execution time required to find a Sudoku puzzle of the desired difficulty level 3 A Difficulty metric In this section, we describe and evaluate a difficulty metric for Sudoku puzzles based up a computer solver hsolve that simulates the actions of a human Sudoku expert 3.1 Assumptions and Metric Development As stated in Section 2, we define the difficulty of a puzzle as the average amount of tim expert Sudoku solver to solve it. In orde e this t essentially two possibilities model the process of solving the puzzle 2. Find some heuristic for board configurations that predicts the solve time There are some known heuristics for finding the difficulty of a puzzle; most notably, puzzles with a small number of initial givens are somewhat harder than most. However, according to 91, the overall correlation is weak. Other methods of this type have similar problems, and more importantly, they cannot be used to determine the difficulty of any specific puzzle Therefore, the second possibility can be used at most as a guide for the first, and we must model the actual process of solving the puzzle. We postulate that the following assumptions hold for the solver. 1. The possible strategies can be ranked in order of difficulty, and the solver always applies them from least to most difficult puzzles.We use a widely accepted ranking of strategies described in Appendix oku This is consistent with more or less all references on the subject of solving sudo 2. During the search for a strategy application, each ordering of possible strategy appli- cations occurs with equal probability There are two components of a human search for a possible location to apply a strategy complete search and intuitive pattern recognition. While human pattern recognitionPage 5 of 24 Control #2858 unique solution. As there is no objective scale in difficulty and no fixed criteria that indicate the difference between puzzles of varying difficulties, we will interpret the given number of difficulty levels and the desired difficulty level as the division of the set of all Sudoku boards into the given number of difficulty percentile intervals of equal size and the choice of a particular desired percentile interval. We will take a sample of 1000 Sudoku boards and assume that the difficulty distribution of these boards, as measured by our human solver, is representative of the difficulty distribution of all Sudoku boards. Our second goal in puzzle generation is to minimize the complexity of the generation algorithm. We note that since the size of the 9 × 9 Sudoku board is fixed, the order of growth of our generation algorithm is irrelevant. Therefore, in this paper, we will interpret the complexity of a generation algorithm to be the expected amount of execution time required to find a Sudoku puzzle of the desired difficulty level. 3 A Difficulty Metric In this section, we describe and evaluate a difficulty metric for Sudoku puzzles based upon a computer solver hsolve that simulates the actions of a human Sudoku expert. 3.1 Assumptions and Metric Development As stated in Section 2, we define the difficulty of a puzzle as the average amount of time required for an expert Sudoku solver to solve it. In order to measure this time, there are essentially two possibilities: 1. Model the process of solving the puzzle 2. Find some heuristic for board configurations that predicts the solve time. There are some known heuristics for finding the difficulty of a puzzle; most notably, puzzles with a small number of initial givens are somewhat harder than most. However, according to [9], the overall correlation is weak. Other methods of this type have similar problems, and, more importantly, they cannot be used to determine the difficulty of any specific puzzle. Therefore, the second possibility can be used at most as a guide for the first, and we must model the actual process of solving the puzzle. We postulate that the following assumptions hold for the solver: 1. The possible strategies can be ranked in order of difficulty, and the solver always applies them from least to most difficult. This is consistent with more or less all references on the subject of solving sudoku puzzles. We use a widely accepted ranking of strategies described in Appendix A. 2. During the search for a strategy application, each ordering of possible strategy appli￾cations occurs with equal probability. There are two components of a human search for a possible location to apply a strategy: complete search and intuitive pattern recognition. While human pattern recognition 5