C
ontinuamos con la solución de un Sudoku usando PHP. Si te perdiste la primera parte, puedes consultarla en este mismo blog.
Como se planteó en la entrega anterior, la ruta de desarrollo que estamos siguiendo para implementar una solución de Sudoku usando PHP es la siguiente:
- Llenar una cuadricula de Sudoku en blanco.
- Solucionar un Sudoku existente.
- Finalmente, crear un Sudoku para ser impreso.
Según esto, la fase de desarrollo que ha de corresponder a este artículo es la del llenado de una cuadrícula de Sudoku en blanco. Antes de comenzar, quizás quieras saber ¿por qué hacerlo así? Primero, porque es un reto interesante en si mismo (uno que quizás usen algunos profesores de programación como proyectos de final de curso) y segundo, porque de esta forma se limitan las variables que afectan el proceso de llenado del tablero al no tener que preocuparnos por las implicaciones de manejar valores fijos y así centrarnos en esa lógica de llenado, misma que luego adaptaremos (con cambios menores, espero) para el escenario de solución de Sudokus reales.
Aclarado esto, ¿por dónde comenzar? Bueno, en mi caso, luego de intentar plasmar mi proceso mental de solución de forma infructuosa, pasé a consultar en Internet cuáles son los procedimientos sugeridos para este tipo de escenarios. De nuevo, Wikipedia vino al rescate con la siguiente sugerencia:
Algunos jugadores han desarrollado programas de computador que resuelven Sudokus usando algoritmos de backtracking, el cuál es un tipo de búsqueda por fuerza bruta.
(Segmento traducido de Wikipedia)
Esto básicamente se traduce en un procedimiento como el descrito a continuación:
- Se toma una primera celda y se le asigna un posible valor (entre 1 y 9 para Sudokus de 9x9).
- Se valida que este valor cumpla con las reglas del Sudoku, esto es: “Cada celda puede contener un número del uno al nueve y cada número solo puede aparecer una vez en cada fila, cada columna o cada caja”.
- Si el número no es valido, se toma uno diferente y se repite el proceso hasta encontrar uno que cumpla.
- Si ninguno de los números cumple, se debe regresar una celda, cambiar el valor asignado y repetir el proceso a partir de allí. Si en esa celda ya se probaron todos los posibles valores, se regresa una más atrás y así hasta encontrar los valores validos para todas las celdas.
- Si ningún valor satisface la primer celda (lo que por supuesto no debiera ocurrir en un tablero en blanco), entonces se determina que el Sudoku no tiene solución, es decir, se tiene un tablero mal definido.
¿Cómo proceder a implementar esta solución de “fuerza bruta”? Empezando por lo más inmediato y en apariencia sencillo. No es algo complicado el recorrer cada celda del tablero, asignar valores random a cada celda y evaluar que esos valores cumplan con las reglas del Sudoku. Estos son procesos que pueden reflejarse implementando métodos como los siguientes:
class miSudoku {
// Propiedades y métodos previamente declaradas...
/**
* Recorre las celdas libres de una fila y les asigna un valor valido.
*/
public function llenarFilas() {
// …
return true;
}
/**
* Asigna valor a una celda, tomado del primero en su listado de valores disponibles.
* Si el valor selecto no cumple, toma el siguiente en el listado de disponibles.
*
* @param int $x Fila (base 0)
* @param int $y Columna (base 0)
* @return bool TRUE si encuentra un valor valido, FALSE en otro caso.
*/
private function llenarCelda(int $x, int $y) {
$encontrado = false;
// …
return $encontrado;
}
/**
* Evalua si el valor sugerido para una celda es valido.
* Esto es, si las celdas de la fila, columna y caja actuales no contienen
* el mismo valor.
*
* @param int $x Fila (base 0)
* @param int $y Columna (base 0)
* @param string $valor Valor sugerido (numérico de base 1).
* @return bool TRUE si encuentra un valor valido, FALSE en otro caso.
*/
private function evalCelda(int $x, int $y, string $valor) {
$encontrado = false;
// ...
return $encontrado;
}
}La parte realmente interesante es el cómo controlar el proceso de llenado cuando se encuentra una celda donde ningún valor satisface las reglas del Sudoku. En este caso como se indicó, se debe retornar a la celda anterior y repetir el proceso con un valor diferente. Es por esto que para cada celda se definieron previamente los siguientes elementos de control:
- Valor de la celda (usaremos el carácter “.” para identificar una celda si valor asignado).
- Indicador de si es una celda fija (en este caso, por tratarse de un tablero en limpio, ninguna es fija).
- Posibles valores permitidos en la celda (números del 1 al 9 que cambiarán conforme vayamos llenando el Sudoku).
¿Cómo se refleja en la lógica el proceso de exploración a “fuerza bruta” descrito antes? Sería algo así:
- Los posibles valores (o valores “disponibles”) en todas las celdas inicializa con todos los valores (1,2,3…).
- Cuando se asigna un valor a una celda, se retira dicho valor a este listado para todas las celdas relacionadas, es decir, a todas las celdas que compartan la misma fila, columna y caja a que pertenece la celda modificada.
- En la medida que se avanza en el recorrido del tablero, se tomará un valor de celda de dicho listado de disponibles, reduciendo el número de errores.
Pero ojo, que “reducir” no es lo mismo que “eliminar” los errores al asignar un valor. Los errores pueden ocurrir porque no se asigna el valor en el orden correcto, lo que suele ocurrir (aunque no exclusivamente) al llegar a las últimas celdas de cada fila. Por ejemplo, en una fila pueden quedar al final disponibles los valores “4,8” pero resulta que para que funcione con las reglas del Sudoku deben ubicarse en el orden “8,4”. Esto significa, que:
- Si la penúltima celda se asigna con “4” (que podría ser un valor valido en ese contexto), se remueve este valor de los disponibles de la última fila.
- La última fila tendrá como valor disponible "8", lo que en el contexto de este ejemplo, producirá un error al ser asignado.
- El sistema deberá retornar a la penúltima celda, remover de los disponibles el valor de “4” y restablecer los valores disponibles de la última fila (restablecer el "4") antes de evaluarla de nuevo.
- Asignar el valor "8" a la penúltima celda y evaluar de nuevo la última.
- Retroceder a la penúltima celda, detectar que ya probó con todos los valores que tenía disponibles (en este caso, “4” y “8”) y retroceder una celda mas.
- Retirar el valor asignado a esta celda, restablecer los historiales de las celdas penúltima y última, asignar un nuevo valor tomado de su respectivo listado de “disponibles” y repetir el proceso de validación para la penúltima y última celdas.
- Continuar así hasta dar con todas las combinaciones correctas.
Como se aprecia, la lógica deberá llevar cuidadosa cuenta de:
- Los valores disponibles para cada celda.
- Información histórica de los valores disponibles en las celdas que son modificadas, lo que se puede lograr incluyéndolo como un nuevo elemento a la estructura de cada celda.
Vale anotar que una alternativa al uso de históricos, es la de reconstruir cada vez el listado de “disponibles”, pero esto aumentaría considerablemente los ciclos de computo. En este caso, habría que validar qué es más rentable, si consumir ciclos o consumir memoria. Para esta solución, considero (sin ningún soporte estadístico, más como intuición basada en la experiencia) que es más rápida la opción de llevar cuenta de los historiales de cambio.
Con esto en consideración, adicionamos nuevos métodos para gestionar tanto los valores disponibles como los historiales, a saber:
class miSudoku {
// Propiedades y métodos previamente declaradas...
/**
* Recupera información del historial de cambios.
* Actualiza las celdas modificadas durante el cambio registrado en cada historial.
*
* @param int $x Fila (base 0)
* @param int $y Columna (base 0)
* @return bool TRUE si encuentra un historial valido, FALSE en otro caso.
*/
private function recuperarHistorial(int &$x, int &$y) {
// ...
// TRUE si encontró un historial valido
return $hay_historial;
}
/**
* Remueve del listado de disponibles el valor asignado a la celda actual.
*
* @param int $x Fila (base 0)
* @param int $y Columna (base 0)
*/
public function actualizarDisponibles(int $x, int $y) {
$removidos = array();
// ...
return $removidos;
}
/**
* Elimina valor selecto del listado de disponibles en las celdas afectadas.
* Guarda copia del elemento original (histórico) en caso que requiera deshacer
* esta selección.
*
* @param int $x Fila (base 0)
* @param int $y Columna (base 0)
* @param string $valor Valor a remover.
* @param array $removidos Arreglo donde registra los valores de la celda actual
* antes de modificarla.
*/
private function removerDisponible(int $x, int $y, string $valor, array &$removidos){
$retornar = false;
// ...
return $retornar;
}
}
El script completo para esta etapa puede consultarse en https://github.com/jjmejia/sudoku/tree/main/parte-2 (para los curiosos, al checar el listado de commits se pueden visualizar las modificaciones realizadas al script liberado en la parte 1).
Un comentario antes de terminar:
Si siempre se usa una secuencia de validaciones ordenada, “123…”, el total de ciclos para un Sudoku de 9x9 será siempre el mismo (en esta implementación, corresponde a un valor de 527 iteraciones). Esto significaría que todos los tableros serían llenados con la misma secuencia en cada fila, comenzando con la primera siempre en “123…”. Para prevenir esto, se aleatorizan el orden de las opciones para cada celda, no basta solamente con la primera (esto limitaría las combinaciones de Sudokus al orden de los números en esa primera fila). Con este ajuste, se pueden generar tableros diferentes cada vez. Es de anotar también que los ciclos encontrados en este escenario, pueden variar entre 81 y un número indeterminado de posibilidades, ya que es realmente una cosa que queda al azar.
¿Tienes alguna sugerencia o consideras que esta lógica puede mejorarse? Te invito a compartirlo en los comentarios para beneficio de todos y mejorar este algoritmo de solución.
Ahora que ya sabemos cómo llenar un tablero en blanco, podemos pasar a resolver Sudokus reales, lo que será el desarrollo a cubrir en la próxima entrega de esta serie.
Este artículo también se encuentra disponible en medium.com.
Comentarios
Publicar un comentario