Sudoku puzzle generation using mathematical programming and heuristics: Puzzle construction and game development

Abstract

In this study, first, a new mathematical programming formulation for generating Sudoku puzzles is proposed. It is possible to generate specially-configured puzzle instances using the proposed formulation which is flexible enough to control not only the numbers of the Sudoku matrix entries shown in each column, row and sub-matrix, but also the times each number appears by setting up the corresponding model parameters accordingly. The initially developed non-linear program with a quadratic constraint is reformulated as a linear-integer program by using appropriate variate transformations. The resulting mathematical program is then solved to generate Sudoku puzzles and its computational performance is analyzed through computational experiments. It is noted that the formulation is fast enough to generate Sudoku puzzles in reasonable time periods using a commercial solver on a personal computer. The study then discusses how to ensure the uniqueness of a solution for a puzzle instance generated by a hybrid approach that integrates the mathematical program with a heuristic algorithm. In the final part of the study, the idea of the proposed hybrid approach is extended and a backtracking algorithm-based puzzle generation procedure is designed and implemented by developing a standalone mobile-web game application.