Sudoku Puzzle Complexity

A Sudoku grid is a 9×9 grid, arranged into nine 3×3 mini-grids each containing the values 1,…,9 such that no value is repeated in any row, column (or mini-grid). The Sudoku grid has been shown to be an interesting mathematical structure. A Sudoku puzzle contains some given values, enabling a solver to arrange the missing values so as to complete the grid uniquely. Typically, published puzzles (such as those found in newspapers or puzzle books) are accompanied by ratings such as 'easy', 'medium' and 'hard' for example. These complexity ratings are assigned through a number of different means, such as by the length of time taken, or the difficulty of the methods required, to solve the puzzle. In this paper, a new measure of complexity is defined which is related to the number of states in a search space for its automatic solution. This complexity measure is compared to those of a test set of 100 published puzzles, which leads to the conclusion that the size of a search space is a useful measure for identifying the complexity of the puzzle. However, the search space size is shown to not provide all the information required to rate a puzzle.