Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.
Este ejemplo muestra cómo resolver un Sudoku Puzzle utilizando la programación de enteros binarios. Para el enfoque basado en problemas, vea.Resolver Sudoku Puzzles a través de programación de enteros: basado en problemas
Probablemente hayas visto puzles de Sudoku. Un puzzle es llenar una cuadrícula de 9 por 9 con números enteros del 1 al 9 para que cada entero aparezca una sola vez en cada fila, columna y cuadrado principal de 3 por 3. La cuadrícula se rellena parcialmente con pistas, y su tarea es rellenar el resto de la cuadrícula.
Aquí hay una matriz de datos de pistas.B
La primera fila, significa la fila 1, la columna 2 tiene una pista 2.B(1,2,2)
La segunda fila, significa la fila 1, la columna 5 tiene una pista 3.B(1,5,3)
Aquí está toda la matriz.B
B = [1,2,2; 1,5,3; 1,8,4; 2,1,6; 2,9,3; 3,3,4; 3,7,5; 4,4,8; 4,6,6; 5,1,8; 5,5,1; 5,9,6; 6,4,7; 6,6,5; 7,3,7; 7,7,6; 8,1,4; 8,9,8; 9,2,3; 9,5,4; 9,8,2]; drawSudoku(B) % For the listing of this program, see the end of this example.
Este puzzle, y una alternativa de MATLAB® técnica de solución, se presentó en 2009.Esquina de Cleve
Hay muchos enfoques para resolver puzzles de Sudoku manualmente, así como muchos enfoques programáticos. Este ejemplo muestra un enfoque sencillo mediante la programación de enteros binarios.
Este enfoque es particularmente sencillo porque no se da un algoritmo de solución. Simplemente exprese las reglas del Sudoku, exprese las pistas como restricciones en la solución y luego producirá la solución.intlinprog
La idea clave es transformar un puzzle de una cuadrícula cuadrada de 9 por 9 a una matriz cúbica de 9 por 9 por 9 de valores binarios (0 o 1). Piense en la matriz cúbica como 9 cuadrículas cuadradas apiladas una encima de la otra. La rejilla superior, una capa cuadrada de la matriz, tiene un 1 donde la solución o pista tiene un 1. La segunda capa tiene un 1 donde la solución o pista tiene un 2. La novena capa tiene un 1 donde la solución o pista tiene un 9.
Esta formulación es precisamente adecuada para la programación de enteros binarios.
La función objetiva no es necesaria aquí, y también podría ser 0. El problema es realmente sólo para encontrar una solución factible, lo que significa uno que satisface todas las restricciones. Sin embargo, para el TIE Breaking en las partes internas del solucionador de programación de enteros, dando una mayor velocidad de la solución, utilice una función objetiva no constante.
Supongamos que una solución
Del mismo modo, en cada fila
Y cada columna
Las principales rejillas 3-por-3 tienen una restricción similar. Para los elementos de rejilla
Para representar las nueve cuadrículas principales, solo tiene que añadir 3 o 6 a cada
Cada valor inicial (pista) se puede expresar como una restricción. Supongamos que el
Aunque las reglas de Sudoku se expresan convenientemente en términos de una matriz de solución de 9 por 9 por 9, las restricciones lineales se dan en términos de una matriz de solución vectorial.x
x(:)
Por lo tanto, cuando escribes un programa de Sudoku, tienes que utilizar matrices de restricción derivadas de 9-por-9-por-9 matrices iniciales.
Aquí hay un enfoque para configurar las reglas de Sudoku, y también incluir las pistas como restricciones. El archivo viene con su software.sudokuEngine
type sudokuEngine
function [S,eflag] = sudokuEngine(B) % This function sets up the rules for Sudoku. It reads in the puzzle % expressed in matrix B, calls intlinprog to solve the puzzle, and returns % the solution in matrix S. % % The matrix B should have 3 columns and at least 17 rows (because a Sudoku % puzzle needs at least 17 entries to be uniquely solvable). The first two % elements in each row are the i,j coordinates of a clue, and the third % element is the value of the clue, an integer from 1 to 9. If B is a % 9-by-9 matrix, the function first converts it to 3-column form. % Copyright 2014 The MathWorks, Inc. if isequal(size(B),[9,9]) % 9-by-9 clues % Convert to 81-by-3 [SM,SN] = meshgrid(1:9); % make i,j entries B = [SN(:),SM(:),B(:)]; % i,j,k rows % Now delete zero rows [rrem,~] = find(B(:,3) == 0); B(rrem,:) = []; end if size(B,2) ~= 3 || length(size(B)) > 2 error('The input matrix must be N-by-3 or 9-by-9') end if sum([any(B ~= round(B)),any(B < 1),any(B > 9)]) % enforces entries 1-9 error('Entries must be integers from 1 to 9') end %% The rules of Sudoku: N = 9^3; % number of independent variables in x, a 9-by-9-by-9 array M = 4*9^2; % number of constraints, see the construction of Aeq Aeq = zeros(M,N); % allocate equality constraint matrix Aeq*x = beq beq = ones(M,1); % allocate constant vector beq f = (1:N)'; % the objective can be anything, but having nonconstant f can speed the solver lb = zeros(9,9,9); % an initial zero array ub = lb+1; % upper bound array to give binary variables counter = 1; for j = 1:9 % one in each row for k = 1:9 Astuff = lb; % clear Astuff Astuff(1:end,j,k) = 1; % one row in Aeq*x = beq Aeq(counter,:) = Astuff(:)'; % put Astuff in a row of Aeq counter = counter + 1; end end for i = 1:9 % one in each column for k = 1:9 Astuff = lb; Astuff(i,1:end,k) = 1; Aeq(counter,:) = Astuff(:)'; counter = counter + 1; end end for U = 0:3:6 % one in each square for V = 0:3:6 for k = 1:9 Astuff = lb; Astuff(U+(1:3),V+(1:3),k) = 1; Aeq(counter,:) = Astuff(:)'; counter = counter + 1; end end end for i = 1:9 % one in each depth for j = 1:9 Astuff = lb; Astuff(i,j,1:end) = 1; Aeq(counter,:) = Astuff(:)'; counter = counter + 1; end end %% Put the particular puzzle in the constraints % Include the initial clues in the |lb| array by setting corresponding % entries to 1. This forces the solution to have |x(i,j,k) = 1|. for i = 1:size(B,1) lb(B(i,1),B(i,2),B(i,3)) = 1; end %% Solve the Puzzle % The Sudoku problem is complete: the rules are represented in the |Aeq| % and |beq| matrices, and the clues are ones in the |lb| array. Solve the % problem by calling |intlinprog|. Ensure that the integer program has all % binary variables by setting the intcon argument to |1:N|, with lower and % upper bounds of 0 and 1. intcon = 1:N; [x,~,eflag] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub); %% Convert the Solution to a Usable Form % To go from the solution x to a Sudoku grid, simply add up the numbers at % each $(i,j)$ entry, multiplied by the depth at which the numbers appear: if eflag > 0 % good solution x = reshape(x,9,9,9); % change back to a 9-by-9-by-9 array x = round(x); % clean up non-integer solutions y = ones(size(x)); for k = 2:9 y(:,:,k) = k; % multiplier for each depth k end S = x.*y; % multiply each entry by its depth S = sum(S,3); % S is 9-by-9 and holds the solved puzzle else S = []; end
S = sudokuEngine(B); % Solves the puzzle pictured at the start
LP: Optimal objective value is 29565.000000. Cut Generation: Applied 1 strong CG cut, and 3 zero-half cuts. Lower bound is 29565.000000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
drawSudoku(S)
Puede comprobar fácilmente que la solución es correcta.
type drawSudoku
function drawSudoku(B) % Function for drawing the Sudoku board % Copyright 2014 The MathWorks, Inc. figure;hold on;axis off;axis equal % prepare to draw rectangle('Position',[0 0 9 9],'LineWidth',3,'Clipping','off') % outside border rectangle('Position',[3,0,3,9],'LineWidth',2) % heavy vertical lines rectangle('Position',[0,3,9,3],'LineWidth',2) % heavy horizontal lines rectangle('Position',[0,1,9,1],'LineWidth',1) % minor horizontal lines rectangle('Position',[0,4,9,1],'LineWidth',1) rectangle('Position',[0,7,9,1],'LineWidth',1) rectangle('Position',[1,0,1,9],'LineWidth',1) % minor vertical lines rectangle('Position',[4,0,1,9],'LineWidth',1) rectangle('Position',[7,0,1,9],'LineWidth',1) % Fill in the clues % % The rows of B are of the form (i,j,k) where i is the row counting from % the top, j is the column, and k is the clue. To place the entries in the % boxes, j is the horizontal distance, 10-i is the vertical distance, and % we subtract 0.5 to center the clue in the box. % % If B is a 9-by-9 matrix, convert it to 3 columns first if size(B,2) == 9 % 9 columns [SM,SN] = meshgrid(1:9); % make i,j entries B = [SN(:),SM(:),B(:)]; % i,j,k rows end for ii = 1:size(B,1) text(B(ii,2)-0.5,9.5-B(ii,1),num2str(B(ii,3))) end hold off end