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
© Copyright 2024 ExpyDoc