Cómo resolver y/o crear un Sudoku usando PHP (parte 3)

C
ontinuamos 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ó inicialmente, 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, 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 tablero:

Un tablero de Sudoku por resolver

Su representación en texto sería la siguiente:

..9|7..|3..
..8|...|659
.1.|...|7..
-----------
.96|837|1.4
1..|...|...
.2.|...|..3
-----------
...|..4|..1
4..|..3|8..
2..|9.6|..5

Para 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. Tanto es así, que sería igualmente válido ingresar un texto como:

..97..3..
..8...659
.1....7..
.968371.4
1........
.2......3
.....4..1
4....38..
2..9.6..5

Sin embargo, esta última versión no se ve muy amigable, ¿verdad?

De cualquiera de las dos maneras mostradas o cualquier combinación de las mismas, el código deberá interpretar correctamente la carga y asignar los valores fijos deseados. 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, jeje).

Ya con estos ajustes finales, es posible resolver el Sudoku con nuestro código y obtener algo como lo siguiente:

Un tablero de Sudoku completamente lleno

o la siguiente:

El mismo tablero de Sudoku completamente lleno

¿Cómo es esto posible? ¿Dos soluciones para un mismo Sudoku? 

Si, si observan cuidadosamente, estas dos imágenes muestran el mismo Sudoku con dos soluciones ligeramente diferentes. Estos Sudokus pueden resultar muy difíciles de resolver y son un verdadero dolor de cabeza. Aparecen cuando no han sido correctamente creados, porque como veremos en la siguiente entrega, existen algunas reglas a seguir cuando se crea un Sudoku.

Como de costumbre, el script completo para esta etapa puede consultarse en https://github.com/jjmejia/sudoku/tree/main/parte-3 y aquellos más curiosos pueden checar los cambios respecto al repositorio del modelo anterior, checando el listado de commits realizados.

Los espero para el capítulo final de esta serie de artículos, hasta entonces, diviértanse solucionando Sudokus.

Este artículo también se encuentra disponible en medium.com.