Page 6 of 24 Control #2858 is extremely powerful (see, for example 2 ) it is extremely difficult to determine its precise consequences, especially due to possible differences between solvers. Therefore we do not consider any intuitive component to pattern recognition and restrict our model to a complete search for strategy applications. Such a search will proceed between possible applications in the random ordering that we postulate Ts We define a possible application of a strategy to be a configuration on the board that checked by a human to determine if the given strategy can be applied; a list of exactly which configurations are checked varies by strategy and is given in Appendix A. We can now model our solver as following the algorithm Human Solve defined as follows Definition. Given a sudoku puzzle, the algorithm Human Solve repeats the following steps until there are no remaining empty squares 1. Choose the least difficult strategy that has not yet been searched for in the current board configuration 2. Search through possible applications of any of these strategies for a valid application of a strategy 3. Apply the first valid application found We take the difficulty of a single run of Human Solve to be the total number of possible applications that the solver must check: here we assume that each check takes roughly have different difficulties due to different valid s of this method on the same puzzle may now ready to define the difficulty metric of a sudoku board B Definition. For a sudoku board B, take its difficulty metric m(B)to be the average total number of possible applications checked by the solver while using the Human Solve algorithm 3.2 hsolve and metric Calculation In order to actually calculate the difficulty m(B)of a board B, we use hsolve, a pre grain which simulates the running of Human Solve and calculates the resulting difficulty. hsolve is implemented in Java 1.6, and its source code is attached in Appendix B Given a Sudoku puzzle b, hsolve does the following Set the initial difficulty d=0 2. Repeat the following actions in order until B is solved or the solver cannot progress (a)Choose the tier of easiest strategies S that has not yet been searched for in the current board configuration (b)Find the number p of possible applications of S (c) Find the set V of all valid applications of S and compute the size v of V 6Page 6 of 24 Control #2858 is extremely powerful (see, for example [2]), it is extremely difficult to determine its precise consequences, especially due to possible differences between solvers. Therefore, we do not consider any intuitive component to pattern recognition and restrict our model to a complete search for strategy applications. Such a search will proceed between possible applications in the random ordering that we postulate. We define a possible application of a strategy to be a configuration on the board that is checked by a human to determine if the given strategy can be applied; a list of exactly which configurations are checked varies by strategy and is given in Appendix A. We can now model our solver as following the algorithm HumanSolve defined as follows: Definition. Given a sudoku puzzle, the algorithm HumanSolve repeats the following steps until there are no remaining empty squares: 1. Choose the least difficult strategy that has not yet been searched for in the current board configuration. 2. Search through possible applications of any of these strategies for a valid application of a strategy. 3. Apply the first valid application found. We take the difficulty of a single run of HumanSolve to be the total number of possible applications that the solver must check; here we assume that each check takes roughly the same amount of time. Note that multiple runs of this method on the same puzzle may have different difficulties due to different valid applications being recognized first. We are now ready to define the difficulty metric of a sudoku board B. Definition. For a sudoku board B, take its difficulty metric m(B) to be the average total number of possible applications checked by the solver while using the HumanSolve algorithm. 3.2 hsolve and Metric Calculation In order to actually calculate the difficulty m(B) of a board B, we use hsolve, a program which simulates the running of HumanSolve and calculates the resulting difficulty. hsolve is implemented in Java 1.6, and its source code is attached in Appendix B. Given a Sudoku puzzle B, hsolve does the following: 1. Set the initial difficulty d = 0 2. Repeat the following actions in order until B is solved or the solver cannot progress: (a) Choose the tier of easiest strategies S that has not yet been searched for in the current board configuration. (b) Find the number p of possible applications of S. (c) Find the set V of all valid applications of S and compute the size v of V . 6