Sudoku Puzzle Difficulty Rating based on Fuzzy Logic

Abstract

In this document, we propose a new fuzzy logic-based rating technique for Sudoku difficulty, which takes into account Sudoku instance parameters such as the number of filled cells as well as parameters relating to the distribution of filled numbers on the cells. This new technique is validated using historical data from a certificate paper [Mantere, 2008], which includes 45 Sudoku instances of all rank levels, three of each level, and the average/max time consumed in 100 runs using different algorithms for each instance. First and foremost, these instances were analyzed and parameterized, and their parameters were quantitatively analyzed to be considered in fuzzy logic. The instance parameters' correlation with their solving time is studied, and dimensionality reduction was performed on these as variables to ensure that no unnecessary variable was included in the study. As solving time parameters, the number of filled cells in the instance, the minimum number of filled cells in rows and columns, and the number of empty sub-squares (3*3) in the instance are all accepted. Because there should be a functional relationship between the Sudoku rank and the time required to solve it, a linear regression model was performed on the historical data between the old rank and the solving time, and the same regression model was performed on the new rank to validate it. As a result, a new clear and simple ranking technique that outputs more correlated ranks with the time required to solve Sudoku puzzles is validated.