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.

Resolver Sudoku Puzzles a través de programación de enteros: basado en problemas

Este ejemplo muestra cómo resolver un Sudoku Puzzle utilizando la programación de enteros binarios. Para el enfoque basado en el solucionador, consulte.Resuelve Sudoku Puzzles a través de programación de enteros: basado en Solver

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.

Puzzle inicial

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, a continuación, MATLAB producirá la solución.

Enfoque de programación de enteros binarios

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, donde cada capa corresponde a un entero del 1 al 9. 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 un término constante 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.

Exprese las reglas para el Sudoku como restricciones

Supongamos que una solución

<math display="block">
<mrow>
<mi>x</mi>
</mrow>
</math>
se representa en una matriz binaria de 9 por 9 por 9. ¿Qué propiedades
<math display="block">
<mrow>
<mi>x</mi>
</mrow>
</math>
¿Tener? En primer lugar, cada cuadrado en la cuadrícula 2-D (i, j) tiene exactamente un valor, por lo que hay exactamente un elemento distinto de cero entre las entradas de la matriz 3-D
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo>.</mo>
<mo>.</mo>
<mo>.</mo>
<mo>,</mo>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mn>9</mn>
<mo stretchy="false">)</mo>
</mrow>
</math>
. En otras palabras, por cada
<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>j</mi>
</mrow>
</math>
,

<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>k</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>9</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
<mo>.</mo>
</mrow>
</math>

Del mismo modo, en cada fila

<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
de la rejilla 2-D, hay exactamente un valor de cada uno de los dígitos de 1 a 9. En otras palabras, para cada
<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>k</mi>
</mrow>
</math>
,

<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>9</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
<mo>.</mo>
</mrow>
</math>

Y cada columna

<math display="block">
<mrow>
<mi>j</mi>
</mrow>
</math>
en la cuadrícula 2-D tiene la misma propiedad: para cada
<math display="block">
<mrow>
<mi>j</mi>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>k</mi>
</mrow>
</math>
,

<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>9</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
<mo>.</mo>
</mrow>
</math>

Las principales rejillas 3-por-3 tienen una restricción similar. Para los elementos de rejilla

<math display="block">
<mrow>
<mn>1</mn>
<mo></mo>
<mi>i</mi>
<mo></mo>
<mn>3</mn>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mn>1</mn>
<mo></mo>
<mi>j</mi>
<mo></mo>
<mn>3</mn>
</mrow>
</math>
, y para cada
<math display="block">
<mrow>
<mn>1</mn>
<mo></mo>
<mi>k</mi>
<mo></mo>
<mn>9</mn>
</mrow>
</math>
,

<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</munderover>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
<mo>.</mo>
</mrow>
</math>

Para representar las nueve cuadrículas principales, solo tiene que añadir 3 o 6 a cada

<math display="block">
<mrow>
<mi>i</mi>
</mrow>
</math>
Y
<math display="block">
<mrow>
<mi>j</mi>
</mrow>
</math>
Índice:

<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</munderover>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>3</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>+</mo>
<mi>U</mi>
<mo>,</mo>
<mi>j</mi>
<mo>+</mo>
<mi>V</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
</mrow>
</math>
Dónde
<math display="block">
<mrow>
<mi>U</mi>
<mo>,</mo>
<mi>V</mi>
<mspace width="0.5em"></mspace>
<mi>ϵ</mi>
<mspace width="0.5em"></mspace>
<mo stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>6</mn>
<mo stretchy="false">}</mo>
<mo>.</mo>
</mrow>
</math>

Las pistas expresas

Cada valor inicial (pista) se puede expresar como una restricción. Supongamos que el

<math display="block">
<mrow>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
pista es
<math display="block">
<mrow>
<mi>m</mi>
</mrow>
</math>
para algunos
<math display="block">
<mrow>
<mn>1</mn>
<mo></mo>
<mi>m</mi>
<mo></mo>
<mn>9</mn>
</mrow>
</math>
. Entonces
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
</mrow>
</math>
. La restricción
<math display="block">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>k</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mn>9</mn>
</mrow>
</munderover>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>1</mn>
</mrow>
</math>
garantiza que todos los demás
<math display="block">
<mrow>
<mi>x</mi>
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>0</mn>
</mrow>
</math>
Para
<math display="block">
<mrow>
<mi>k</mi>
<mo></mo>
<mi>m</mi>
</mrow>
</math>
.

Sudoku en forma de problema de optimización

Cree una variable de optimización que sea binaria y de tamaño 9-por-9-por-9.x

x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1);

Crear un problema de optimización con una función objetiva bastante arbitraria. La función objetiva puede ayudar al solucionador 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 las sumas de cada dirección de coordenadas son una.x

sudpuzzle.Constraints.consx = sum(x,1) == 1; sudpuzzle.Constraints.consy = sum(x,2) == 1; sudpuzzle.Constraints.consz = sum(x,3) == 1;

Cree las restricciones que las sumas de las cuadrículas principales suman a una también.

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 los límites inferiores de 1 en las entradas de pista. Esta configuración corrige el valor de la entrada correspondiente a 1 y, por lo tanto, establece la solución en cada valor de clued para que sea la entrada de pista.

for u = 1:size(B,1)     x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1; end

Resuelve el puzle de Sudoku.

sudsoln = solve(sudpuzzle)
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 default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). 
sudsoln = struct with fields:
    x: [9x9x9 double]

Redondee la solución para asegurarse de que todas las entradas son números enteros y mostrar 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 dibujar el Sudoku Puzzle

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