Page 4 of 24 Control #2858 solving behavior. We then propose two different methods again based on solve to generate Sudoku puzzles of different difficulties 2 Problem Setup In this paper, we approach the problem in two portions. First, we define a difficulty metric for a Sudoku puzzle and determine an algorithm to compute it. We then create an algorithm to generate Sudoku puzzles with desired levels of difficulty. Before beginning to describe our model, however, we first specify the problem a bit more closely in both cases 2.1 Difficulty metric Our goal in this part of the paper is to create an algorithm that takes a Sudoku puzzle and returns a real number that represents its abstract "difficulty"according to some metric The central issue in determining such a metric is then what we mean by the "difficulty of a Sudoku puzzle. We base our definition of difficulty on the following general assumptions 1. The amount of time it takes for any given solver to solve a puzzle is monotonically increasing with difficulty 2. Every solver tries to solve Sudoku puzzles by applying various strategies The difficulty of a puzzle is an inherently subjective quantity and may vary among different solvers who use different methods of solving Sudoku puzzles. However, this type of subjective consideration is not inherent to the puzzle, so we must restrict ourselves to purely objective reactions. For this purpose, it is a useful intellectual tool to consider some hypothetical typical"solver of some postulated skill level Now, Assumption 1 suggests that we should measure difficulty by the amount of time spent solving the puzzle. Because difficulty is increasing in time spent, any definition of difficulty must give the same ordering as time spent. Since this gives an objectively precise definition, we adopt it; therefore, it only remains to determine more precisely what type of solver our metric should consider The difficulties of puzzles can vary for solvers of different skill levels, and it may be arg that one should measure each of these difficulties separately. However, we are assuming that all solvers' time spent will be consistent with difficulty, and assigning absolute difficulty alues has much practical value. Therefore, in order to avoid the dependence of our results on the novice's ignorance of various techniques and to extend the range of measurable puzzles we take our hypothetical solver to be an expert Hence, we define the difficulty of a Sudoku puzzle to be the average amount of time a hypothetical"typical " Sudoku expert would spend solving it. In the subsequent parts of this paper, our aim will be to create and evaluate a metric to determine this time 2.2 Puzzle generation A second objective of this paper is to develop a method of puzzle generation. Our main goal in puzzle generation is to produce a valid puzzle of a given desired difficulty level that has aPage 4 of 24 Control #2858 solving behavior. We then propose two different methods again based on hsolve to generate Sudoku puzzles of different difficulties. 2 Problem Setup In this paper, we approach the problem in two portions. First, we define a difficulty metric for a Sudoku puzzle and determine an algorithm to compute it. We then create an algorithm to generate Sudoku puzzles with desired levels of difficulty. Before beginning to describe our model, however, we first specify the problem a bit more closely in both cases. 2.1 Difficulty Metric Our goal in this part of the paper is to create an algorithm that takes a Sudoku puzzle and returns a real number that represents its abstract “difficulty” according to some metric. The central issue in determining such a metric is then what we mean by the “difficulty” of a Sudoku puzzle. We base our definition of difficulty on the following general assumptions: 1. The amount of time it takes for any given solver to solve a puzzle is monotonically increasing with difficulty. 2. Every solver tries to solve Sudoku puzzles by applying various strategies. The difficulty of a puzzle is an inherently subjective quantity and may vary among different solvers who use different methods of solving Sudoku puzzles. However, this type of subjective consideration is not inherent to the puzzle, so we must restrict ourselves to purely objective reactions. For this purpose, it is a useful intellectual tool to consider some hypothetical “typical” solver of some postulated skill level. Now, Assumption 1 suggests that we should measure difficulty by the amount of time spent solving the puzzle. Because difficulty is increasing in time spent, any definition of difficulty must give the same ordering as time spent. Since this gives an objectively precise definition, we adopt it; therefore, it only remains to determine more precisely what type of solver our metric should consider. The difficulties of puzzles can vary for solvers of different skill levels, and it may be argued that one should measure each of these difficulties separately. However, we are assuming that all solvers’ time spent will be consistent with difficulty, and assigning absolute difficulty values has much practical value. Therefore, in order to avoid the dependence of our results on the novice’s ignorance of various techniques and to extend the range of measurable puzzles, we take our hypothetical solver to be an expert. Hence, we define the difficulty of a Sudoku puzzle to be the average amount of time a hypothetical “typical” Sudoku expert would spend solving it. In the subsequent parts of this paper, our aim will be to create and evaluate a metric to determine this time. 2.2 Puzzle Generation A second objective of this paper is to develop a method of puzzle generation. Our main goal in puzzle generation is to produce a valid puzzle of a given desired difficulty level that has a 4