UM ETheses Collection (澳門大學電子學位論文庫)
 Title

Application of linear programming in Sudoku
 English Abstract

Show / Hidden
University of Macau Abstract APPLICATION OF LINEAR PROGRAMMING IN SUDOKU by Leong Fu Fai alias Leong Chan Meng Thesis Supervisor: Dr. Leong Ieng Tak Master of Science in Mathematics Sudoku is a popular puzzle involving filling digits from 1 through 9 into 81 cells of a 9x9table, such that there are digits 1 to 9 appeared exactly once in each row, each column, and each of the nine nonoverlapping 3x3 subtables. In each game.some digits are filled in, so the player starts to fill the digits in the remaining empty entries under the constraints stated above. We want to set up a mathematical model so that the game can be formulated in terms of mathematical ideas, and then we provide a general method of determining when a Sudoku puzzle is solvable or not, and then give out some solution if the puzzle is wellposed. This thesis is divided into three chapters. In the first chapter, we review the basic concepts of linear programming and the simplex method of locating the optimal solution. There is nothing new in chapter one, it is only used to fix the notations and terminology. In the second chapter, we explain what Sudoku puzzle is, and introduce the rules of this game. Then we formulate the rules into a system of linear equations by means of indicator variables, which we call Sudoku linear system. These variables play significant roles in this formulation. Originally they are 0/1valued variables which correspond to all possible solutions of Sudoku by the rules of Sudoku, but in the Sudoku linear system, the variables become realvalued. However, the Sudoku system is related to a wellstructured 0/1 matrix, which we call Sudoku matrix. If one can solve the system of linear equations in general, then all the Sudoku puzzles can immediately be solved. Instead of exploring the matrix structure, we propose to use the linear programming to search for an optimal solution which corresponds to an original solution of a given Sudoku puzzle, so we introduce an unrelated objective function which can accelerate the search of the solution. As a consequence of this formulation, we obtain a necessary condition of a wellposed Sudoku puzzle, which can be used as a criterion of solvability of the Sudoku puzzle. Then we proceed to justify the basis of applying simplex method in solving Sudoku. This is accomplished by reformulating the linear programming as a combinatorial matrix problem related to graph theory. In fact, this method has been successfully implemented in computer, and it is very effective in terms of solving actual Sudoku puzzle. In the final chapter, we propose a 3dimensional Sudoku puzzle concerning 16x6 entries on the 6 faces of4x4x4 cube, and similar results of planar Sudoku are obtained.
 Issue date

2006.
 Author

Leong, Fu Fai
 Faculty

Faculty of Science and Technology
 Department

Department of Mathematics
 Degree

M.Sc.
 Subject

Computer science  Mathematics
Linear programming
Sudoku
 Supervisor

Leong, Ieng Tak
 Files In This Item
 Location
 1/F Zone C
 Library URL
 991000166429706306