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

Como programador, he tenido que realizar proyectos profesionalmente, algunos con mayores retos que otros. Pero aparte de los retos profesionales, existen retos personales, programas que me nace escribir ya sea porque necesito solucionar una necesidad puntual o solamente por el placer de hacerlo. Uno de esos últimos retos fue el de solucionar un Sudoku. Si ya se, existen muchas aplicaciones allí afuera que lo hacen, pero el reto es hacerlo, no copiarlo.

Un tablero de Sudoku en limpio.

Habiendo aclarado las intenciones al respecto, lo primero a tener claro es cómo se define un Sudoku. Para esto, voy a apoyarme en la siempre disponible (aunque no siempre fiable) Wikipedia:

Un Sudoku estándar contiene 81 celdas, dispuestas en una trama de 9×9, que está subdividida en nueve cajas. Cada caja está determinada por la intersección de tres filas con tres columnas. 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. Un sudoku comienza con algunas celdas ya completas, conteniendo números (pistas), y el objetivo es rellenar las celdas restantes. Los sudokus bien planteados tienen una única solución. (https://es.wikipedia.org/wiki/Algoritmos_para_la_resoluci%C3%B3n_de_sudokus)

Ojo con esa última línea: “Los sudokus bien planteados tienen una única solución”, la tendremos que considerar más adelante.

Solucionar un Sudoku no es algo trivial, aunque así lo parece. Lo primero que intenté fue replicar mi forma de abordar estos pasatiempos, pero entonces me di cuenta que plasmar mi forma de pensar en un “algoritmo coherente” no iba a resultar porque, bueno, los humanos tenemos formas de pensar muy particulares y no siempre se trasladan bien al lenguaje de una máquina (de allí la trascendencia, relevancia e importancia de lo que se ha logrado con ChatGPT). Esto me llevo a que muchas veces abandonara este proyecto. Y a que muchas veces lo intentara de nuevo, hasta que finalmente decidí que lo mejor era comenzar por el principio, con algo “sencillo”, como llenar una cuadricula de Sudoku en limpio. Decidido eso, lo siguiente fue trazar la ruta de trabajo a seguir, que fue la siguiente:

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

Teniendo esta ruta definida, comencé con lo básico en estos casos, porque la urgencia en estos proyectos personales suele ser sentarse a programar (usando PHP en mi caso) y comenzar a ver resultados, así no sea la presentación lo más elegante del mundo. Con esto en mente, comencé la creación de una clase que inicialmente permitiera:

• Definir el tamaño base del Sudoku: 2 cajas de ancho, 4 celdas o 3 cajas de ancho, 9 celdas. Este último será la opción por defecto.
  Registrar el tablero de Sudoku en un arreglo bidimensional.
• Probablemente no la más adecuada forma pero si la representación más aproximada a la cuadricula de Sudoku a la que estamos acostumbrados.
• Generar un identificador único para cada celda y caja del tablero.
• Generar un identificador único o checksum para el tablero en su conjunto (esto para futuras implementaciones donde se requiera diferenciar un tablero de otro).

Adicionalmente, la clase debe definir cada celda y asignarle atributos como:

• Valor de la celda (usaremos el carácter “.” para identificar una celda si valor asignado).
• Si es una celda fija (a usar cuando queramos solucionar un Sudoku existente).
• Posibles valores permitidos en la celda (números del 1 al 9 que cambiarán conforme vayamos llenando el Sudoku).

Finalmente y aunque no es lo usual debido a que va en contra de algunos principios aplicables a las clases (¿has escuchado hablar de principios SOLID?), voy a incluir un método para visualizar el tablero de Sudoku en pantalla. Esto ayudará a visualizar el progreso de la solución. Posteriormente puede retirarse para tener una clase no dependiente de la salida a pantalla pero de momento nos servirá así.

Esto nos lleva a tener una clase con una estructura similar a la siguiente:

class miSudoku {

 // Numero de celdas a contener en cada grupo de celdas. Esto es, el tablero tendrá
 // $this->base cajas a lo ancho, cada una con $this->base celdas. Así, si la base es 
 // 2, el número de celdas a lo ancho (así como el número de celdas en cada caja) es
 // de 4, entanto que para base 3 el número de celdas es 9.
 public $base = 3;

 // Arreglo bidimensional con la información del tablero de Sudoku
 private $tablero = array();

 /**
  * Construye base para el tablero de Sudoku.
  * Las opciones validas para llenar cada celda son los números de 1 en adelante. El 
  * valor máximo depende de la base usada (4 o 9, usualmente para una base de 2 o 3
  * respectivamente).
  */
 public function construirBase() {
  // ...
 }

 /**
  * Genera texto HTML a pantalla para visualizar el tablero de Sudoku.
  */
 public function render() {
  $salida = '';
  // ...
  echo $salida;
 }

}

Una vez codificada (puedes consultar el script completo en https://github.com/jjmejia/sudoku/tree/main/parte-1), tendremos una presentación en pantalla como la siguiente:

Visualización de un tablero de Sudoku en blanco.

Y con esto podemos comenzar a llenar el tablero, pero eso lo veremos en detalle en la próxima entrega de esta serie (disponible en este enlace).

Nota: También puedes leer estos artículos en mi Blog de programador.