Solución del Sudoku de n 2 × n2 con MatLab

Soluci´on del Sudoku de n2 × n2 con MatLab
R. Espejel-Morales
Facultad de Ciencias, Universidad Nacional Aut´onoma de M´exico.
Resumen
En las siguientes l´ıneas se presenta una forma de abordar el problema de automatizar la soluci´on
del Sudoku de n2 ×n2 . Se utiliza c´odigo MatLab en su forma m´as simple, dividiendo el problema
en varias funciones para facilitar su comprensi´on cuando se utiliza como material pedag´ogico,
asimismo se evita el uso de funciones recursivas, aunque su empleo podr´ıa reducir la extensi´on
del c´odigo notablemente.
Introducci´
on
El objetivo del Sudoku tradicional es rellenar una cuadr´ıcula de 9×9 celdas dividida en regiones
de 3 × 3 con cifras del 1 al 9, partiendo de n´
umeros en algunas de las celdas, sin repetir ninguna
cifra en una misma fila, columna o regi´on (las celdas delimitadas por lineas gruesas en la figura).
El problema puede simplificarse o´ extenderse para plantear Sudokus de 4×4, 16×16 o´ en general
de n2 × n2 . En cualquier caso, un Sudoku debe tener soluci´on u
´nica.
1
8 A 3
D
3 F 2
D E
C 8
6
7
2
2
4 8
4 1
3
5
4 8
4 8
9 7
9 2
6
4
6 3
9 1
8
5
3
1
Figura 1. Ejemplo de
Sudoku de 9 × 9.
G
A
D
2
5
7 3
4
A
1 C
6
F D A E
9
C
D 3
4
2
3
G
8
C
8
2
B
C
1
3 1
5
D
8 4
E
D
1
1 7 C
E
A F
2
6
8 3 B
1 4 F
B
6
2 4
D
1
4
E 7
8
B
A
3 B
6
C
5 E
5
9
4
6
E
4 3
2
F G
9
D 7 B
B 4
D
A 6 1
5
C
A 9
Figura 2. Ejemplo de Sudoku de 16 × 16. Se han utilizado las
letras de la A a la G para representar los n´
umeros del 10 al 16.
1
La estrategia que generalmente seguimos para resolver un Sudoku puede describirse como
sigue: Identificamos aquellas celdas sobre las que tenemos m´as informaci´on, es decir, donde
los posibles n´
umeros son m´ınimos, o de hecho, se tiene informaci´on suficiente para conocer el
n´
umero correcto, entonces al colocarlo, se reducen las posibilidades en otras celdas, lo cual
nos puede llevar a llenar otras que ahora son obvias. Si seguimos este proceso hasta que
no existan celdas vac´ıas obvias, nos veremos obligados, para continuar, a elegir un n´
umero
cualquiera de los posibles para una celda, con lo cual habr´a m´as celdas obvias que llenaremos
hasta encontrarnos con que tenemos que hacer m´as conjeturas. As´ı, podemos llegar a que
la u
´ltima conjetura es incorrecta y entonces probamos con otro n´
umero de los posibles en la
celda correspondiente, borrando todas las celdas que llenamos como consecuencia de haber
elegido el n´
umero err´oneo. Si hemos usado todos los n´
umeros y no encontramos la soluci´on,
entonces cambiamos la conjetura anterior y comenzamos de nuevo. El reto est´a en comunicar
este proceso a la computadora.
MatLab es un int´erprete enfocado al manejo y operaci´on de matrices y vectores, permitiendo
incluso operarlos como conjuntos, lo cual lo hace ideal para la implementaci´on del programa
que nos ocupa ya que relacionarermos el Sudoku con una matriz cuyos ceros representan celdas
en blanco y las dem´as entradas contendr´an los n´
umeros correspondientes. De esta forma, el
programa final recibir´a una matriz como argumento y devolver´a otra con la soluci´on. Dividiremos el problema en varias partes; cada una ser´a resuelta por una o m´as funciones que ser´an
incorporadas al programa final.
Desarrollo
Comenzaremos por obtener los n´
umeros posibles para una celda vac´ıa Mr,c . Para ello necesitamos encontrar la uni´on del conjunto de los n´
umeros contenidos en la columna c con los contenidos en el rengl´on r y con los contenidos en la regi´on correspondiente. Despu´es obtendremos
la diferencia de este conjunto con el de los n´
umeros del 1 al n2 .
Para obtener una lista o vector que contenga las entradas de un rengl´on o una columna de
una matriz en MatLab podemos usar las siguientes instrucciones:
h=M(y,:);
La lista o vector h contendr´a al rengl´on y de la matriz M .
v=M(:,x)’; La lista o vector v contendr´a a la columna x de la matriz M (ya que extraemos
un vector columna, empleamos el ap´ostrofe para transponerlo y obtener un vector rengl´
on).
Ahora bien, para obtener una lista que contenga a los n´
umeros de la regi´on correspondiente
a la celda, debemos extraer una submatriz, para ello debemos especificar qu´e renglones y qu´e
columnas queremos incluir. Veamos el siguiente ejemplo:


1 1 1 1 1
 1 2 2 2 2 



1
2
3
3
3
M =


 1 2 3 4 4 
1 2 3 4 5
2
Si quisi´eramos extraer la matriz formada por los renglones 2 al 4 y las columnas 3 a 5,
podr´ıamos escribir H=M(2:4,3:5); con lo cual obtendr´ıamos:


2 2 2
H= 3 3 3 
3 4 4
De modo que para obtener los n´
umeros de la regi´on que contiene a la celda Mr,c podemos
implementar la siguiente funci´on:
function v=region(M,r,c)
k=sqrt(length(M));
Calcula la ra´ız cuadrada del tama˜
no de la matriz M.
cc=ceil(c/k);
Calcula la parte entera de los cocientes.
rr=ceil(r/k);
vv=M(k*rr-k+1:k*rr,k*cc-k+1:k*cc);
v=vv(:)’;
Concatena los renglones de la matriz correspondiente a la regi´on en el vector v.
Podemos ahora implementar la siguiente funci´on con la que obtendermos el conjunto de los
n´
umeros posibles para la celda Mr,c :
function m=posibles(M,r,c)
h=M(r,:);
v=M(:,c)’;
k=[h v region(M,r,c)];
m=setdiff(1:length(M),k);
donde hemos empleado la funci´on setdiff para calcular la diferencia de los conjuntos.
El objetivo es ahora implementar una funci´on iterativa, que rellene las casillas donde existe
una u
´nica posibilidad as´ı como aquellas donde, a consecuencia de la iteraci´on anterior, se
reduzcan a uno las posibilidades. Para ello implementaremos primero una funci´on con la que
obtengamos una matriz con el n´
umero de posibilidades de cada casilla. Esta matriz nos ser´a
u
´til para identificar, tanto las celdas triviales (con una u
´nica posibilidad), como las de menor
n´
umero de ellas, que son por las que comenzaremos a hacer conjeturas posteriormente.
function z=explora(M)
k=length(M);
z=zeros(k,k)+(k+1);
for c=1:k
for r=1:k
if M(r,c)==0
z(r,c)=length(posibles(M,r,c));
end
end
end
As´ı, si aplicamos esta funci´on al Sudoku de la Figura 1, obtendremos la matriz:
3














4
10
10
4
4
4
4
3
4

2 10 2 1 10 3 10 4
2 4 3 10 10 4 4 5 

10 3 3 2 10 4 2 4 

3 3 3 10 3 10 10 3 

10 10 2 2 2 10 10 4 

10 10 3 10 2 2 3 2 

3 3 10 3 2 3 10 10 

4 3 10 10 3 3 2 10 
10 3 10 3 2 10 2 4
donde se identifica con el n´
umero 10 (el tama˜
no de la matriz m´as uno) a las casillas llenas que
forman el Sudoku original.
Ahora implementemos la funci´on minimo, que devuelve un vector que contiene el valor
m´ınimo, y su posici´on, de la matriz que recibe como argumento. La salida es de la forma
[valor r c], y est´a dada por:
function m=minimo(M)
[A,R]=min(M);
[b,c]=min(A);
m=[b R(c) c];
As´ı, al ejecutar las funciones en el ejemplo, tendremos:
>>minimo(explora(M))
ans =
1 1 5
Es decir, tenemos un valor m´ınimo igual a uno en M1,5 (primer rengl´on, quinta columna de
la matriz M ).
Podemos ahora elaborar la funci´on que cumple con el objetivo de esta parte:
function M1=PonUnicos(M)
M1=M;k=minimo(explora(M1));
while k(1)==1
r=k(2); c=k(3);
b=posibles(M1,r,c);
M1(r,c)=b(1);
k=minimo(explora(M1));
end
Ciertos Sudokus pueden ser resueltos en su totalidad con esta funci´on, sin embargo no es el
caso general. Si aplicamos esta funci´on al ejemplo de la Figura 1 tendremos:
4
6
9 7
2
2
4 8
4 1
2 3
5
4 8
4 8
3
9 7
9 2
6
4
6 3
9 1
8
5
3
1
Figura 3. Soluci´on parcial del Sudoku de la Fig. 1.
La funci´on anterior nos garantiza una soluci´on parcial, donde cualquier celda vac´ıa tiene,
al menos, dos posibilidades. As´ı, para poder continuar, debemos dise˜
nar un m´etodo que nos
permita hacer conjeturas, regresar a estados anteriores y modificarlas en caso de no obtener la
soluci´on.
Para determinar cuando una matriz M corresponde a un Sudoku resuelto podemos emplear
la funci´on termino que ser´a u
´til en el siguiente desarrollo.
function t=termino(M)
k=minimo(M);
t=(k(1)∼=0);
El m´etodo de b´
usqueda que emplearemos es el llamado “vuelta atr´as” (backtracking), ´este
realiza un recorrido en profundidad en un a´rbol de decisiones en busca de un nodo (hoja)
favorable. Esto se logra tomando como v´alidas conjeturas, esto es, recorriendo ramas que nos
llevan a soluciones parciales a medida que progresa la b´
usqueda; estas soluciones parciales van
reduciendo las posibilidades mediante las cuales se puede encontrar una soluci´on. Si en alguna
etapa no se puede continuar por haber llegado a una soluci´on que identificamos como incorrecta,
se vuelve atr´as, hasta que se llega a un nodo que tiene una o m´as posibilidades sin explorar,
siguiendo por alguno de ellos en busca de la soluci´on correcta.
La clave para implementar el m´etodo, es una estructura de datos tipo LIFO (por las siglas
de “Last In, First Out”). Se hace una analog´ıa con un la acci´on de apilar elementos, de modo
que el u
´nico que podemos tomar ser´a el u
´ltimo que colocamos, por lo cual tambi´en llamamos
pila a esta estructura.
La manera de implementar la pila en MatLab es mediante una matriz a la cual se le van
a˜
nadiendo renglones en la parte superior, y cuando se requiera, se tomar´a informaci´on del
primero (el u
´ltimo que se a˜
nadi´o) y se eliminar´a. Estos renglones contendr´an la informaci´on
sobre el estado del Sudoku, la celda sobre la cual se hizo la conjetura y el conjunto de n´
umeros
posibles que a´
un no hemos probado. La informaci´on del estado del Sudoku, es decir, cada
soluci´on parcial, se almacenar´a en un arreglo de matrices, que en el listado del programa final
llamamos borrador.
El programa Resuelve consta de un ciclo while que se ejecuta mientras que no se encuentre
la soluci´on. Dentro de ´el, se llama a la funci´on PonUnicos y se comprueba si se ha llegado a la
soluci´on, de ser as´ı se sale del ciclo y se devuelve la matriz obtenida, de lo contrario se verifica
si hay conjeturas que probar, y en su caso se anexa la matriz del Sudoku actual al arreglo, y se
5
coloca un n´
umero, en la celda con el menor n´
umero de posibilidades. Con el resto de ellas, el
´ındice del arreglo y la posici´on de la celda, se forma el rengl´on de la pila, se anexa a ella y se
cierra el ciclo. En caso contrario, es decir, en el cual ya no hay conjeturas que probar, se tiene
que se han agotado las posibilidades de una celda y no se ha llegado a la soluci´on, en este caso
ser´a necesario regresar en el ´arbol para seguir otra rama, esto es, seleccionar otro n´
umero de
la lista almacenada en el primer rengl´on de la pila antes de cerrar el ciclo. En el caso de haber
agotado la lista, se elimina el rengl´on completo de la pila, con lo cual, en la siguiente iteraci´on,
el primer rengl´on corresponder´a a otra celda con su lista de posibilidades respectiva.
En MatLab es necesario generar la siguiente funcion auxiliar gsort que ordena las entradas
del vector en orden descendente, sin embargo, en SciLab est´a ya implementada.
function r=gsort(x)
k=length(x);
x1=sort(x);
r=x1(k:-1:1);
Un an´alisis cuidadoso del listado de la funci´on Resuelve, poniendo atenci´on a las notas a
la derecha, y un ligero estudio de las funciones b´asicas de MatLab, puede dar mayor claridad
al procedimiento.
N´otese que la u
´nica restricci´on que hemos hecho respecto al tama˜
no de la matriz original,
es que la ra´ız cuadrada sea un entero, de modo que, aunque hemos tomado el ejemplo de un
Sudoku de 9 × 9, nuestro programa podr´a resolver cualquier Sodoku bien planteado de n2 × n2 .
6
7
function M1=Resuelve(M)
M1=M;pag=0; pila=[ ];
borrador=[ ];
while ∼termino(M1)
M1=PonUnicos(M1);
k=minimo(explora(M1));
if termino(M1) break; end
r=k(2);c=k(3);
numeros=posibles(M1,r,c);
if k(1)∼=0
Hay conjeturas v´
alidas
que probar.
borrador=cat(3,borrador,M1);
Almacena el Sudoku actual en el arreglo
 de matrices.
M1(r,c)=numeros(1);
Se coloca uno de los n´
umeros posibles en la



numeros(1)=[ ];
casilla, se forma un rengl´on con los n´
umeros
otros=gsort([numeros zeros(1,(length(M)+1)-length(numeros))]); 
restantes junto con el ´ındice del arreglo


pila=[size(borrador,3) r c otros; pila];
y posici´on para anexarlo a la pila.
Se lleg´
o a un resultado err´oneo, se recurre
else
a la pila para regresar a la conjetura
anterior.

RT=pila(1,:);




reg=RT(1); r=RT(2); c=RT(3);

Se toma informaci´on del primer rengl´on de
M1=borrador(:,:,reg);
la pila y se elige un n´
umero como conjetura.


numeros=RT(4:length(RT));



M1(r,c)=numeros(1); if numeros(2)==0
Si era el u
´nico numero posible, se
pila(1,:)=[ ];
quita el rengl´on de la pila.
end
end
end

Download Report