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 9x9-table, such that there are digits 1 to 9 appeared exactly once in each row, each column, and each of the nine non-overlapping 3x3 sub-tables. 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 well-posed. 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/1-valued variables which correspond to all possible solutions of Sudoku by the rules of Sudoku, but in the Sudoku linear system, the variables become real-valued. However, the Sudoku system is related to a well-structured 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 well-posed 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 3-dimensional Sudoku puzzle concerning 16x6 entries on the 6 faces of4x4x4 cube, and similar results of planar Sudoku are obtained.