La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

Resolver sudokus mediante la programación de enteros: enfoque basado en problemas

Abrir script en vivo

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 $x$ se representa en un arreglo binario de 9 por 9 por 9. ¿Qué propiedades tiene $x$ ? 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 $x (i, j, 1), . . ., x (i, j, 9)$ . En otras palabras, para cada $i$ y $j$ ,

$\sum_{k = 1}^{9} x (i, j, k) = 1 .$

De forma similar, en cada fila $i$ 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 $i$ y $k$ ,

$\sum_{j = 1}^{9} x (i, j, k) = 1 .$

Y cada columna $j$ de la cuadrícula bidimensional tiene la misma propiedad: para cada $j$ y $k$ ,

$\sum_{i = 1}^{9} x (i, j, k) = 1 .$

Las cuadrículas interiores de 3 por 3 tienen una restricción similar. Para los elementos de la cuadrícula $1 \leq i \leq 3$ y $1 \leq j \leq 3$ , y para cada $1 \leq k \leq 9$ ,

$\sum_{i = 1}^{3} \sum_{j = 1}^{3} x (i, j, k) = 1 .$

Para representar las nueve cuadrículas interiores, basta con añadir 3 o 6 a cada índice $i$ y $j$ :

$\sum_{i = 1}^{3} \sum_{j = 1}^{3} x (i + U, j + V, k) = 1,$ donde $U, V ϵ {0, 3, 6} .$

Expresar las pistas

Cada valor inicial (pista) puede expresarse como una restricción. Suponga que la pista $(i, j)$ es $m$ para ciertos $1 \leq m \leq 9$ . Entonces, $x (i, j, m) = 1$ . La restricción $\sum_{k = 1}^{9} x (i, j, k) = 1$ garantiza que todas las demás $x (i, j, k) = 0$ para $k \neq m$ .

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