Lb = zeros(9,9,9) % an initial zero array M = 4*9^2 % number of constraints, see the construction of AeqĪeq = zeros(M,N) % allocate equality constraint matrix Aeq*x = beqīeq = ones(M,1) % allocate constant vector beqį = (1:N)' % the objective can be anything, but having nonconstant f can speed the solver N = 9^3 % number of independent variables in x, a 9-by-9-by-9 array If sum() % enforces entries 1-9Įrror('Entries must be integers from 1 to 9') = meshgrid(1:9) % make i,j entriesĮrror('The input matrix must be N-by-3 or 9-by-9') % 9-by-9 matrix, the function first converts it to 3-column form.
% element is the value of the clue, an integer from 1 to 9. % elements in each row are the i,j coordinates of a clue, and the third % puzzle needs at least 17 entries to be uniquely solvable). % The matrix B should have 3 columns and at least 17 rows (because a Sudoku % expressed in matrix B, calls intlinprog to solve the puzzle, and returns % This function sets up the rules for Sudoku. What properties does x have? First, each square in the 2-D grid (i,j) has exactly one value, so there is exactly one nonzero element among the 3-D array entries x ( i, j, 1 ). Suppose a solution x is represented in a 9-by-9-by-9 binary array. Express the Rules for Sudoku as Constraints However, for tie breaking in the internals of the integer programming solver, giving increased solution speed, use a nonconstant objective function. The problem is really just to find a feasible solution, meaning one that satisfies all the constraints. The objective function is not needed here, and might as well be 0.
This formulation is precisely suited for binary integer programming. The ninth layer has a 1 wherever the solution or clue has a 9. The second layer has a 1 wherever the solution or clue has a 2. The top grid, a square layer of the array, has a 1 wherever the solution or clue has a 1. Think of the cubic array as being 9 square grids stacked on top of each other.
The key idea is to transform a puzzle from a square 9-by-9 grid to a cubic 9-by-9-by-9 array of binary values (0 or 1). Just express the rules of Sudoku, express the clues as constraints on the solution, and then intlinprog produces the solution. This approach is particularly simple because you do not give a solution algorithm. This example shows a straightforward approach using binary integer programming. There are many approaches to solving Sudoku puzzles manually, as well as many programmatic approaches. This puzzle, and an alternative MATLAB® solution technique, was featured in Cleve's Corner in 2009.