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

A
puesto que al igual que yo, piensas que crear un tablero de Sudoku es llenar una cuadrícula y luego simplemente remover celdas al azar. También, que para definir la dificultad de un Sudoku basta con definir cuántas celdas fijas dejar. Bueno, parece que estamos equivocados o al menos yo lo estaba. Hay reglas a considerar para la creación correcta de un Sudoku y en este último artículo, relacionado con la creación de Sudokus usando PHP, te lo contaré.

Esta es la última parte de esta serie de artículos, donde si recuerdan bien, estamos siguiendo la siguiente ruta de desarrollo:

• Llenar una cuadricula de Sudoku en blanco. 
• Solucionar un Sudoku existente. 
• Finalmente, crear un Sudoku para ser impreso.

Cómo mencioné antes, para la creación de un tablero de Sudoku no basta con rellenar una cuadrícula en blanco y que fue cubierta en un artículo anterior. De acuerdo con la información en Wikipedia, existen al menos un par de reglas que deben tenerse en cuenta:

• El menor número posible de celdas fijas para un Sudoku de 9x9 es 17 (aprox. 21% del total de 81 celdas en un Sudoku de 9x9).
• Cada Sudoku tiene una única posible solución. Ojo con esta regla porque se debe garantizar esa única posible solución al establecer qué celdas fijas mantener.

Respecto al nivel de dificultad también hay consideraciones a tener presente, al menos de acuerdo con las definiciones encontradas en www.sudokulovers.com y de las que podemos concluir que:

• Sudokus fáciles y medios pueden ser resueltos usando deducciones lógicas directas, es decir, no tienes que esforzarte demasiado, solamente estar muy atento.
• Sudokus fáciles tienen al menos tres celdas fijas por fila, columna, caja y al menos una por cada número, lo que en promedio (para Sudokus de 9x9) deja al menos 27 celdas por tablero (usualmente un poco más).
• Sudokus difíciles tienen menos de 27 celdas fijas pero no menos de 17, muy seguramente con cajas, filas, columnas o números completos sin valores.
• Para Sudokus difíciles probablemente tendrás que suponer valores y si te equivocas, pues a empezar de nuevo.

Vaya... Implementar estas condiciones no parece cosa fácil, pero tampoco es para perder la cabeza. Vamos “pasito a pasito, suave, suavecito”, como decía aquella popular canción de Luis Fonsi. Para ello, seguiremos estas “sencillas” reglas:

• Remover una celda por vez y validar que cumple con los requerimientos de “solución única” y de un tablero de nivel fácil arriba descritas.
• Preservar ese último Sudoku posible que cumple con las condiciones dadas, será precisamente el tablero de nivel “fácil”.
• Continuar removiendo celdas validando únicamente que tenga una “única solución”, hasta encontrar el último Sudoku posible. 
• Preservar ese último tablero como el de nivel “difícil”.
• El Sudoku de nivel “medio” será aquel que quede en la posición media (redundancia intencional) entre el difícil y el fácil encontrados.

Antes de continuar, un pequeño descargo:

Favor tener presente que esta es mi propuesta respecto a cómo obtener tableros con diferentes niveles de dificultad y que no es ni mucho menos absoluta o definitiva. Pueden existir (y seguro existen) otras formas para determinar la complejidad de los tableros a proponer, pero para efectos de los alcances y limitaciones de este desarrollo, esta será la guía a seguir.

Retomando, aquí el truco de magia realmente consiste en evaluar esa única solución. ¿Cómo lo logramos? Bueno, si recuerdan, durante el proceso de solución anterior se maneja un arreglo de datos asociado a cada celda y uno de los elementos de dicho arreglo corresponde a los valores disponibles para cada celda, listado que se va modificando mientras se va llenando el tablero con las posibles soluciones. En este caso, como se conoce la solución deseada, lo que haremos será modificar ese listado de disponibles y ubicar al final el valor que sabemos que debe tomar la celda. Así, cada que se remueva una celda se deberá ejecutar el método de solución de tablero para:

• Garantizar que las restantes celdas permitan encontrar una solución, y
• Tentar al algoritmo para que encuentre una solución diferente forzándolo a probar primero con los valores que sabemos que no son los esperados.

Esto nos lleva a modificar la clase implementada con los siguientes métodos:

class miSudoku {

	// Propiedades y métodos previamente declaradas…

	// Total de celdas fijas
	private $totalFijas = 0;

	/**
	 * Valida que la solución dada para un Sudoku sea única.
	 *
	 * @param string $fijas Cadena de texto con la asignación de celdas fijas.
	 * @param array $data_solucion Arreglo que contiene la cadena de texto con la
	 *        solución a validar ("valores") y la estructura de tablero de dicha
	 *        solución ("data").
	 * @return bool TRUE si la validación es éxitosa, FALSE si encontró otra posible
 	 *        solución.
	 */
	public function validarSolucionPrevia(string $fijas, array $data_solucion) {

		// Fija la solución para capturar rapidamente los datos
		$tablero_solucion = $data_solucion['data'];
		$valores_solucion = $data_solucion['valores'];

		// … ejecuta solución usando el listado de celdas dado en $fijas

		// Compara que la solución obtenida (Si alguna) sea la esperada.
		return ($this->infoerror === '' && 
				$valores_solucion === $this->valores());
	}

	/**
	 * Valida las celdas fijas para determinar que corresponden a un Sudoku fácil.
	 * Debe cumplir las siguientes condiciones:
	 * - Tienen al menos tres celdas fijas por fila, columna, caja
	 * - Tiene al menos una celda para cada número.
	 * 
	 * @param string $fijas Cadena de texto con la asignación de celdas fijas.
	 * @return bool TRUE si las celdas fijas indicadas proveen una solución "fácil", 
 	 *         FALSE en otro caso.
	 */
	public function validarFacil(string $fijas) {
		// …

		return $retornar;
	}

	/**
	 * Crea un tablero de Sudoku nuevo.
	 *
	 * @return array Datos para nuevo Sudoku.
	 */
	public function nuevo() {
		// …
		return $retornar;
	}

Es así como podemos generar tableros con diferentes niveles de solución para una misma cuadricula, tal como los mostrados a continuación:

Un tablero de Sudoku nivel difícil

Un tablero de Sudoku nivel medio

Un tablero de Sudoku nivel fácil

El mismo tablero de Sudoku nivel fácil ya solucionado

El script completo para esta clase, así como un ejemplo de uso, puede consultarse en https://github.com/jjmejia/sudoku/tree/main/parte-4 y recuerden checar los cambios respecto al repositorio del modelo anterior.

Con esto terminamos este recorrido. Ya tenemos las herramientas para solucionar Sudokus y para crear Sudokus nuevos usando PHP. Resta implementar una interfaz apropiada para poderlo usar en línea pero eso se los dejo de tarea y si pueden y lo quieren compartir, los invito a que lo hagan en los comentarios de este artículo.

Hasta una próxima y gracias por la compañía.