A Binary Integer Programming Approach to find a Sudoku Matrix

Paramacutty Paramadevan

Abstract

In the basic Sudoku game, players must fill the entries of a n×n matrix, except some given entries, under the conditions that each row, each column, and each m×m sub-matrix contains integers 1 through n exactly once. In this research paper, in addition to the basic game, conditions and solution process for three advanced versions, such as Sudoku X, Four Square Sudoku and Four Pyramid Sudoku were also studied. In this study, the above-mentioned conditions are converted into appropriate mathematical forms as constraints of the Integer Linear Programming Problem using Pascal Programming Language, such a way that the objective function and the constraints suit as an input mathematical model for the LINGO mathematical optimization software. Here, an unlimited version of the LINGO software has been used with the built-in Branch and Bound algorithm as the number of constraints is very high. Finally, solutions to the given Sudoku problems were obtained from the solutions acquired through LINGO software.

Keywords: Sudoku, Integer linear programming, Pascal programming, LINGO, Branch and Bound algorithm.

Full text:

Cite as: Paramadevan, P., 2022. A Binary Integer Programming Approach to find a Sudoku Matrix. Vavuniya Journal of Science, 1(1):26-30.