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

R2026b

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.

9-by-9 Sudoku puzzle grid with initial clues placed in various cells

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 tanto, 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.
Running HiGHS 1.14.0: Copyright (c) 2026 under MIT licence terms
MIP has 324 rows; 729 cols; 2916 nonzeros; 729 integer variables (708 binary)
Coefficient ranges:
  Matrix  [1e+00, 1e+00]
  Cost    [1e+00, 9e+00]
  Bound   [1e+00, 1e+00]
  RHS     [1e+00, 1e+00]
Presolving model
229 rows, 253 cols, 1018 nonzeros 0s
50 rows, 34 cols, 182 nonzeros 0s
31 rows, 18 cols, 121 nonzeros 0s
9 rows, 9 cols, 29 nonzeros 0s
7 rows, 7 cols, 24 nonzeros 0s
5 rows, 6 cols, 18 nonzeros 0s
0 rows, 0 cols, 0 nonzeros 0s
Presolve reductions: rows 0(-324); columns 0(-729); nonzeros 0(-2916) - Reduced to empty
Presolve: Optimal

Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
     I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
     S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
     Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   405             405                0.00%        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      405
  Dual bound        405
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    405 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0
  LP iterations     0

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

sudsoln = struct with fields:
    x: [9×9×9 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)

9-by-9 grid showing solution of Sudoku puzzle

Puede comprobar fácilmente que la solución es correcta.

Función para diseñar el sudoku

Este código crea la función 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