Ir al contenido principal

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:

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.

Comentarios

Entradas populares de este blog

Manejo de recursos HTML para tus páginas web con PHP

Déjame saber si te resulta familiar esta situación: páginas web que descargan el mismo recurso (sean estilos CSS o código Javascript) más de una vez o incluyen recursos remotos que tardan una eternidad en cada descarga. Yo lo he visto en más de una ocasión y no es difícil imaginar el porqué ocurre. Un desarrollador incluye el recurso de estilos que necesita su segmento de código y otro hace lo mismo, sin reparar (o sin que siquiera importe) que comparten el mismo recurso. En otro escenario muy común, acostumbran incluir muchos recursos remotos, con lo que el rendimiento de la página depende de lo rápido que responda dicho recurso. ¿Puede hacerse algo al respecto? Claro que si. Vamos a crear una clase en PHP que se encargue de administrar estos recursos y que nos facilite su despliegue en la página sin repeticiones . ¿Y respecto a la demora en la carga de recursos remotos? Atendamos una cosa por vez, porque como dicen por ahí: «Vísteme despacio, que tengo prisa». Administrando ...

Manejo de clases globales únicas en PHP

¿Cómo acceder desde cualquier script en tu proyecto a Clases y/o funciones de uso común? Este puede ser una de las primeras directrices a establecer para cualquier proyecto porque siempre, siempre , sea en  PHP  u otro lenguaje, será necesario usar recursos comunes. En PHP existen diferentes alternativas para su manejo, ya sea por medio de variables globales o de clases/objetos estáticos. A continuación consideraremos una propuesta para este manejo. Creación de recursos globales Para ilustrar esta solución, partimos de la necesidad de implementar una librería para manejo de servicios relacionados con el servidor Web, que de forma amigable nos permita disponer de información como: Valores almacenados de la variable superglobal $_SERVER de PHP. Valores asociados a la consulta realizada por el usuario, por Ej. la dirección IP del usuario o la URL ingresada. Valores asociados al servidor web usado, por Ej. la dirección IP del servidor o la ubicación del script que ej...

¿Qué tan bueno es realmente el “foreach” en PHP?

Como toda buena historia, esta comienza hace algún tiempo. El que fuera mi jefe por allá en la primera década del 2000, realmente odiaba (y mucho) el uso del foreach en el código PHP . Prefería que usáramos alguna alternativa diferente, alguna combinación del  for o del while . ¿Por qué? Ve tú a saber, nunca fue abierto respecto a las razones de su aprensión hacia ese constructor propio del lenguaje. Pero antes de continuar, veamos qué es y para qué nos puede servir. Arreglos, tenían que ser arreglos ¿Qué es foreach ? De acuerdo al manual de PHP , su definición es la siguiente: El constructor foreach proporciona un modo sencillo de iterar sobre arrays . foreach funciona sólo sobre arrays y objetos , y emitirá un error al intentar usarlo con una variable de un tipo diferente de datos o una variable no inicializada. Para su uso correcto existen dos sintaxis validas, a saber: foreach (expresión_array as $value) { ... } foreach (expresión_array as $key => $value) { ....