Hace tiempo escribí un artículo sobre un método de generación de sudokus en wakicode, ahora se me ha ocurrido obtener un método sencillo de resolución de sudoku. En esta primera parte mostraré como intentar resolverlos por pura lógica, con operaciones lógicas en pura esencia, sin necesidad de efectuar simulaciones por fuerza bruta o prueba error. Eso será más adelante cuando la lógica no tenga cabida.
El método que se me ha ocurrido lo hago del siguiente modo.
1.- Definiciones.
- Ln. Capa de posición de un elemento n, se corresponde con un 1 si existe n (o es visible) y 0 si no es visible. En el ejemplo, podemos visualizar para un n=2, la matriz resultado de L2.
- Bnc. Byte de columna para n. En el ejemplo B2c=110101111 que corresponde a un 1 si la columna tiene un 1 y 0 si la columna es ausente de 1.
- Bnr. Byte de fila para n. En el ejemplo B2r=110110111 que corresponde (de arriba hacia abajo) a un 1 si la fila tiene un 1 y 0 si esta es ausente de 1.
- Bns. Byte de bloque 3×3 para n. En el ejemplo B2s=101011111 que corresponde (de izquierda a derecha y de arriba abajo) a un 1 si el bloque 3×3 tiene un 1 y 0 si el bloque 3×3 es ausente de 1.
- Mo. Matriz de elementos ocupados. Matriz 9×9 identificada por un 1 si la celda tiene un valor visible y un 0 si no lo tiene.
- Mnc. Matriz de columnas. Operación OR de cada uno de los elementos de Mo con el bit correspondiente de Bnc. Mo OR Bnc
- Mnr. Matriz de filas. Operación OR de cada uno de los elementos de Mnc con el bit correspondiente de Bnr. Mnc OR Bnr
- Mns. Matriz de bloque. Operación OR de cada uno de los elementos de Mnr con Bns. Mnr OR Bns
Una vez que conocemos los elementos participantes en el método pasamos a describir su desarrollo:
- Generar Mnc. Buscar en la matriz elementos únicos con valor 0. Esto significa que al realizar la operación OR del byte de columna con los elementos ocupados, queremos discriminar los elementos en los que únicamente pueden estar en esa posición. En el caso del ejemplo para n=2 no existen elementos únicos puesto que las columnas que tienen 0, tienen más de un 0. La columna 3ª tiene tres «0» y 5ª columna tiene dos «0».
- Generar Mnr. Buscar en la matriz elementos únicos con valor 0. En el caso del ejemplo para n=2 la matriz resultante si tiene elementos únicos puesto que las columnas que tienen 0, tienen más de un 0. La columna 3ª tiene tres «0» y la 5ª columna tiene dos «0».
El caso de la figura indica que el lugar ocupado por los ceros únicos, es una celda ocupada en este caso por un 2 - Generar Mns. Buscar en la matriz elementos únicos con valor 0. En este caso se buscan elementos únicos en el bloque 3×3 y que para el caso concreto, ha coincidido con los elementos obtenidos de en Mnr.
La matriz de la derecha corresponde con la operación OR del Byte y la matriz origen - En cada generación de una nueva Matriz se realiza una búsqueda de estos elementos únicos. Solo en el caso de ubicaciones ambiguas en las que es posible ocupar dos celdas o tres o más celdas con 3 o más números posibles, habría que usar otros métodos de fuerza bruta o prueba y error hasta que no se me ocurra otro método lógico para este caso. Esto lo dejaremos para otro post.
Para terminar os dejo el diagrama de clases y cuando se me ocurra un método lógico de resolución del sudoku pondré el código en GitHub.
He aquí una muestra con C# y WPF resolviendo Sudokus generados aleatoriamente con 50 celdas ocultas. El algoritmo en la mayoría de los casos, para unas 50 celdas ocultas, no ha necesitado más de 7 iteraciones para resolver todos los elementos por lógica. Le he indicado que dependiendo del número de iteraciones cambie de color el número encontrado, del azul, verde, amarillo al rojo como el color de mayor iteración.
wakicode 