Ease And Toil: Analyzing Sudoku

摘要

Sudoku is a logic puzzle in which the numbers 1 through 9 are arranged in a 9 × 9 matrix, subject to the constraint that there are no repeated numbers in any row, column, or designated 3 × 3 square. In addition to being entertaining, Sudoku promises insight into computer science and mathematical modeling. Since Sudoku-solving is an NP-complete problem, algorithms to generate and solve puzzles may offer new approaches to a whole class of computational problems. Moreover, Sudoku construction is essentially an optimization problem. We propose an algorithm to construct unique Sudoku puzzles with four levels of difficulty. We attempt to minimize the complexity of the algorithm while still maintaining separate difficulty levels and guaranteeing unique solutions. To accomplish our objectives, we develop metrics to analyze the difficulty of a puzzle. By applying our metrics to published control puzzles with specified difficulty levels, we develop classification functions. We use the functions to ensure that our algorithm generates puzzles with difficulty levels analogous to those published. We also seek to measure and reduce the computational complexity of the generation and metric measurement algorithms. Finally, we analyze and reduce the complexity involved in generating puzzles while maintaining the ability to choose the difficulty level of the puzzles generated. To do so, we implement a profiler and perform statistical hypothesis-testing to streamline the algorithm.