Resolver sudokus mediante la programación de enteros: enfoque basado en problemas
Este ejemplo muestra cómo resolver un sudoku mediante la programación de enteros binaria. Si desea ver el enfoque basado en solvers, consulte Solve Sudoku Puzzles via Integer Programming: Solver-Based.
Probablemente sepa lo que es un sudoku. Se trata de un rompecabezas que consiste en rellenar una cuadrícula de 9 por 9 con números enteros del 1 al 9, de modo que cada número entero aparezca solo una vez en cada fila, columna y cuadrado interior de 3 por 3. La cuadrícula está parcialmente rellena con pistas y la tarea consiste en rellenar el resto de la cuadrícula.
Sudoku inicial
Aquí puede ver una matriz de datos B
, relativa a las pistas. La primera fila, B(1,2,2)
, significa que el valor de la pista de la fila 1, columna 2, es 2. La segunda fila, B(1,5,3)
, significa que el valor de la pista de la fila 1, columna 5, es 3. A continuación se muestra la matriz B
en su totalidad.
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 sudoku, y una técnica alternativa para solucionarlo con MATLAB®, se publicó en Cleve's Corner en 2009.
Hay muchos enfoques para resolver sudokus manualmente, así como muchos métodos programáticos. Este ejemplo muestra un enfoque sencillo utilizando programación de enteros binaria.
Este enfoque es especialmente sencillo porque no proporciona un algoritmo de solución. Basta con expresar las reglas del sudoku, expresar las pistas como restricciones de la solución y, a continuación, MATLAB produce la solución.
Enfoque de programación de enteros binaria
La idea principal consiste en transformar el sudoku de una cuadrícula cuadrada de 9 por 9 en un arreglo cúbico de 9 por 9 por 9 de valores binarios (0 o 1). Piense en el arreglo cúbico como si fueran 9 cuadrículas apiladas las unas sobre las otras, donde cada capa corresponde a un número entero del 1 al 9. La cuadrícula superior, una capa cuadrada del arreglo, tiene un 1 en la posición en la que la solución o la pista tiene un 1. La segunda capa tiene un 1 en la posición en la que la solución o la pista tiene un 2. La novena capa tiene un 1 en la posición en la que la solución o la pista tenga un 9.
Esta formulación se adapta perfectamente a la programación de enteros binaria.
La función objetivo no es necesaria en este caso y también puede ser un término constante 0. El problema consiste en encontrar una solución factible, es decir, que satisfaga todas las restricciones. Sin embargo, para desempatar en el interior del solver de programación de enteros, ofreciendo una mayor velocidad de solución, utilice una función objetivo no constante.
Expresar las reglas del sudoku como restricciones
Suponga que la solución se representa en un arreglo binario de 9 por 9 por 9. ¿Qué propiedades tiene ? En primer lugar, cada cuadrado de la cuadrícula bidimensional (i,j) tiene exactamente un valor, por lo que hay exactamente un elemento distinto de cero entre las entradas del arreglo tridimensional . En otras palabras, para cada y ,
De forma similar, en cada fila de la cuadrícula bidimensional, hay exactamente un valor de cada uno de los dígitos del 1 al 9. En otras palabras, para cada y ,
Y cada columna de la cuadrícula bidimensional tiene la misma propiedad: para cada y ,
Las cuadrículas interiores de 3 por 3 tienen una restricción similar. Para los elementos de la cuadrícula y , y para cada ,
Para representar las nueve cuadrículas interiores, basta con añadir 3 o 6 a cada índice y :
donde
Expresar las pistas
Cada valor inicial (pista) puede expresarse como una restricción. Suponga que la pista es para ciertos . Entonces, . La restricción garantiza que todas las demás para .
Sudoku con formato de problema de optimización
Cree una variable de optimización x
que sea binaria y de tamaño 9 por 9 por 9.
x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1);
Cree un problema de optimización con una función objetivo arbitraria. La función objetivo puede ayudar al solver destruyendo la simetría inherente del problema.
sudpuzzle = optimproblem; mul = ones(1,1,9); mul = cumsum(mul,3); sudpuzzle.Objective = sum(sum(sum(x,1),2).*mul);
Represente las restricciones que establecen que las sumas de x
en cada dirección de coordenadas son uno.
sudpuzzle.Constraints.consx = sum(x,1) == 1; sudpuzzle.Constraints.consy = sum(x,2) == 1; sudpuzzle.Constraints.consz = sum(x,3) == 1;
Cree también las restricciones que establecen que las sumas de las cuadrículas interiores suman uno.
majorg = optimconstr(3,3,9); for u = 1:3 for v = 1:3 arr = x(3*(u-1)+1:3*(u-1)+3,3*(v-1)+1:3*(v-1)+3,:); majorg(u,v,:) = sum(sum(arr,1),2) == ones(1,1,9); end end sudpuzzle.Constraints.majorg = majorg;
Incluya las pistas iniciales estableciendo límites inferiores de 1 en las entradas de las pistas. Esta configuración fija el valor de la entrada correspondiente en 1 y, por lo tanto, fija la solución en cada valor de la pista.
for u = 1:size(B,1) x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1; end
Resuelva el sudoku.
sudsoln = solve(sudpuzzle)
Solving problem using intlinprog. LP: Optimal objective value is 405.000000. 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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.
sudsoln = struct with fields:
x: [9x9x9 double]
Redondee la solución para asegurarse de que todas las entradas son números enteros y muestre la solución.
sudsoln.x = round(sudsoln.x); y = ones(size(sudsoln.x)); for k = 2:9 y(:,:,k) = k; % multiplier for each depth k end S = sudsoln.x.*y; % multiply each entry by its depth S = sum(S,3); % S is 9-by-9 and holds the solved puzzle drawSudoku(S)
Puede comprobar fácilmente que la solución es correcta.
Función para diseñar el sudoku
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