Cómo resolver y/o crear un Sudoku usando PHP (parte 3)
Continuamos con esta serie de artículos donde comparto con ustedes la implementación de una solución a los Sudokus usando PHP. Como se planteó, la ruta de desarrollo a seguir es la siguiente:
- Llenar una cuadricula de Sudoku en blanco.
- Solucionar un Sudoku existente.
- Finalmente, crear un Sudoku para ser impreso.
El proceso de llenar una cuadrícula de Sudoku en blanco fue cubierto en el artículo anterior. A partir de este punto, nos queda definir el cómo registrar los valores existentes en un Sudoku que deseemos resolver, esto es, indicarle a nuestro código los valores de aquellas celdas iniciales o fijas. Para esto (y vamos a ponernos un poco técnicos conforme avanzamos, así que paciencia), se propone que dichos valores se ingresen mediante un bloque de texto donde cada línea corresponda a una fila, cada posición en la línea a una columna, cada celda vacía se identifique con un punto (“.”) y los valores fijos por números entre 1 y 9 (para un Sudoku de 9x9). Por ejemplo, usando como base el siguiente Sudoku:
Su representación en texto sería algo así:
..9|7..|3..
..8|...|659
.1.|...|7..
-----------
.96|837|1.4
1..|...|...
.2.|...|..3
-----------
...|..4|..1
4..|..3|8..
2..|9.6|..5Para efectos de facilitar su visualización para los ojos humanos como los míos y los tuyos, me he tomado la libertad de adicionar caracteres para separar las filas y cajas, pero estos serán ignorados por el script al interpretarlo.
Una vez inicializado el Sudoku con estos valores fijos y antes de comenzar al proceso de llenado de filas, es prudente (de acuerdo a la lógica planteada en la implementación realizada y descrita en la entrega anterior) revisar los valores disponibles para las celdas a las que esos valores fijos pueden afectar, esto es, a aquellas que están en la misma fila, columna y caja. Así, la clase implementada se modificaría para incluir los siguientes métodos:
class miSudoku {
// Propiedades y métodos previamente declaradas...
/**
* Asigna valores fijos.
* Requiere ejecutar primero $this->construirBase().
* Recibe texto con la estructura del Sudoku deseado, usando "." para indicar las
* celdas vacias, números para las celdas ocupadas (1..9 en un Sudoku de 9x9). Una
* linea por fila. Las líneas en blanco * y tabuladores o espacios al inicio/final
* de cada línea son ignoradas. Opcionalmente puede separar las cajas usando el
* carácter "|" en las fijas e incluyendo una fila con "-" para separar las cajas
* en horizontal.
*/
public function setFijas(string $texto) {
// …
}
/**
* Recorre tablero y si encuentra que existen celdas fijas, revisa valores
* disponibles asociados.
*/
private function inicializarDisponibles() {
// …
}
}Ya con estos cambios podemos pasar felizmente a ejecutar el programa y dejar que resuelva el Sudoku por nosotros.
Pero… (siempre hay un “pero”, ¿verdad?)
Al ejecutar el script es muy probable que a) use demasiados ciclos para resolverlo o b) puede no resolverlo del todo. Antes de entrar en pánico y mandar todo a la papelera de reciclaje, permíteme explicar el porqué puede ocurrir esto: Como no se está abordando una cuadrícula en blanco sino una con valores previos, es posible que la cantidad de validaciones a realizar supere el límite fijado o que por cuenta de aquellas celdas fijas, existan celdas que solamente puedan tomar uno y solamente un valor, pero que al intentar buscar la solución a “fuerza bruta”, el algoritmo tropiece y falle al relacionar dicho “valor deseado”. Al menos esta es la conclusión a la que llegué luego de seguir un “paso a paso” del proceso (algo que puede resultar tedioso, frustrante y hasta insoportable, pero completamente necesario). Al observarlo, noté que estos tropiezos no suceden cuando soluciono manualmente un Sudoku en papel, precisamente porque primero busco aquellos números que se repiten y que hacen que ciertas celdas en blanco puedan tomar uno y solamente un valor posible. Esos son los primeros valores que ubico en una solución en papel y supuse que sería prudente hacer que el programa hiciera lo mismo.
Así, adicioné un nuevo método a ejecutar cada que se asigne un nuevo valor a una celda:
class miSudoku {
// Propiedades y métodos previamente declaradas...
/**
* Recorre el tablero buscando celdas en blanco que pueden tomar uno y solamente
* un valor disponible.
*
* @return bool TRUE si el valor es aceptable por las reglas del Sudoku, FALSE en
* otro caso.
*/
private function validarUnicos() {
// …
return true;
}
/**
* Revisa el tablero solucionado y garantiza que todos los valores cumplen con
* las reglas del Sudoku. Imprime mensaje de texto opcionalmente.
*
* @param bool $solo_validar TRUE no imprime mensajes de texto.
* @return bool TRUE si el tablero quedó bien solucionado, FALSE en otro caso.
*/
public function validarSolucion(bool $solo_validar = false) {
// …
return true;
}
}Adicionalmente incluí un método de chequeo que revise la cuadrícula final y garantice que la solución presentada satisface todas las reglas del Sudoku, para de esta forma evitarme la tarea de hacerlo manualmente (esas son las cosas que hacemos los programadores, escribir código para ejecutar tareas que no queremos hacer, yeah).
Ya con estos ajustes finales, es posible resolver el Sudoku con nuestro código y obtener algo como lo siguiente:
Si realizaste la implementación del código (el cual puedes obtener en https://github.com/jjmejia/sudoku/tree/main/parte-3) y al ejecutar este ejemplo llegaste a una solución diferente a la ilustrada en la imagen, no te asustes. Estos casos aparecen cuando el Sudoku no ha sido correctamente creado y se puede llegar a dos o más soluciones alternativas, porque como veremos en la siguiente entrega, existen algunas reglas a seguir para crear correctamente un tablero de Sudoku.
Los espero para el capítulo final de esta serie de artículos, hasta entonces, diviértanse solucionando Sudokus.
¿Tienes alguna sugerencia? ¿Consideras que esta lógica puede mejorarse? ¿Te interesan este tipo de contenidos? Te invito a compartirlo en los comentarios para beneficio de todos.
También puedes leer este y otros artículos en mi Blog de programador.
