---

---

Fecha: 2/4/2021. Por: David Luna

---

• El repositorio con el código fuente completo está aquí

Retomando donde dejamos la última vez

En mi publicación anterior escribí sobre un algoritmo para resolver sudokus escrito en C++, el cual utiliza el algoritmo AC-3 para asegurar consistencia entre los arcos y después usa la heurística de menor cantidad de valores restantes para guíar la búsqueda hacia un sudoku resuelto en base al input recibido. Si no has leído la publicación, la recomiendo como un punto de inicio que provee contexto para el resto de este texto. La publicación puede ser encontrada aquí

Trabajando inteligentemente, no más fuerte

Al enfrentar el problema de cómo generar un sudoku desde cero, puede parecer difícil crear una técnica que se asegure que el sudoku generado sea válido y pueda ser resuelto. Es necesario tomar en cuenta las restricciones del problema, del mismo modo que estas fueron tomadas en cuenta al escribir el algoritmo para resolverlo. Una celda en la cuadrícula no puede tener el mismo valor que otra celda en el mismo renglón, columna o subcuadrícula de 3x3.

La ventaja es que contamos con algoritmo capaz de resolver cualquier cuadrícula parcialmente completada que le entreguemos, por lo cual sirve como un buen punto de partida. El único problema es que siempre regresará el mismo resultado dado el mismo input (lo cual no es realmente malo en el caso de resolver el problema, pero puede no ser tan conveniente para generar nuevos problemas). Algo de aleatoriedad es necesaria para entregarle una cuadrícula parcialmente completada al algoritmo resolvente, el cual entregará como resultado una cuadrícula completa. Después, sólo queda borrar tantas celdas como queramos y listo, ¡un sudoku generado aleatoriamente!

El código a continuación fue escrito en GDScript, ya que escribí un juego de Sudoku con el motor para videojuegos Godot. El lenguaje de programación es fácil de leer y usar para programar.

A escribir un algoritmo resolvente (de nuevo)

Ya que la explicación para el algoritmo resolvente fue cubierta en mi publicación anterior, me saltaré la implementation del algoritmo en esta ocasión. La versión del código escrita en GDScript puede ser encontrada aquí

Escribiendo el generador

Como un punto de inicio para el generador, es necesario encargarse del input aleatorio que es entregado al algoritmo resolvente que escribimos previamente. Un acercamiento sencillo es elegir un número aleatorio entre 1 y 9, el cual es posicionado en cada columna de la cuadrícula. Es necesario asegurar que los números son colocados en diferentes renglones y subcuadrículas de 3x3. Ya que este posicionamiento debe obedecer ciertas restricciones, podemos usar una de las funciones escritas previamente en el algoritmo para resolver sudokus: is_var_consistent:

func is_var_consistent(key):
	if domains.get(key).size() > 1:
		return false
	var val = domains.get(key).front()
	for neighbor in constraints.get(key):
		var domain = domains.get(neighbor)
		if domain.empty() || (domain.size() == 1 && domain.has(val)):
			return false
	return true

Esta función toma una llave (una posición [x][y] en la cuadrícula) y revisa si su dominio tiene valores en conflicto con respecto a sus vecinos. Si el dominio de una celda es mayor a 1, no es necesario preocuparse, ya que se puede borrar uno de los valores y eso no dejaría el dominio vacío y sin ningún otro valor que elegir. Si ambas celdas tienen una restricción del tipo X =/= Y, y ambas tienen un mismo valor en su respectivo dominio, entonces una tiene que eliminar dicho valor de su dominio, lo cual elimina las opciones de valores a elegir para la variable, llegando así a un estado inconsistente.

El valor y la posición del número generado aleatoriamente puede ser generado una y otra vez hasta conseguir un estado inicial que sea consistente.

func verify_rows(rows):
	for i in range(NCOLS):
		var row = rows[i]
		var key = str(row) + str(i)
		if !is_var_consistent(key):
			return false
	return true

func gen(difficulty):
	var randNum = (randi() % 9) + 1 # número aleatorio tal que 1 <= randNum <= 9
	var rows = range(9) # rows = [0,1,2,3,4,5,6,7,8]
	var verified = false
	while !verified:
		clear_domains()
		rows.shuffle()
		for x in range(NCOLS): # NCOLS = 9
			var row = rows[x]
			grid[row][x] = randNum
			domains[str(row) + str(x)] = [randNum]
		verified = verify_rows(rows)
    ...

El número inicial usaro para llenar parcialmente la cuadrícula es seleccionado aleatoriamente. Lo mismo aplica en el caso del renglón en el cual se colocará el valor en cada una de las columnas. La función verify_rows determina si podemos continuar o no.

El proceso de colocar el número en sus posiciones finales comienza con la función clear_domains, la cual asigna el dominio de cada celda en la cuadrícula al dominio inicial, que es {1,2,3,4,5,6,7,8,9}. Si una de las restricciones es ignorada con la asignación inicial de la cuadrícula, la función verify_rows regresará un valor negativo, y el proceso para elegir una cuadrícula inicial comenzará de nuevo. En cada iteración dentro del ciclo while se limpia la cuadrícula para iniciar desde cero y terminar con sólo el número randNum en ella. Después de este paso, podemos terminar con un estado inicial como el siguiente:

Una vez que contamos con el estado inicial de una cuadrícula parcialmente llena, esta puede ser pasada al otro algoritmo, el cual resolverá el sudoku por nosotros. Con un sudoku resuelto, sólo queda limpiar un número aleatorio de celdas en la cuadrícula, con dicho número seleccionado en base a la dificultad elegida por el usuario. La posición de las celdas a eliminar también es elegida aleatoriamente.

	...
	solve()
	var keys_to_del = domains.keys().duplicate()
	keys_to_del.shuffle()
	var n_to_del
	if difficulty == 0: 		# fácil
		 n_to_del = rng.randi_range(15, 25)
	elif difficulty == 1: 	# medio
		 n_to_del = rng.randi_range(30, 45)
	else: 				# difícil
		 n_to_del = rng.randi_range(50, 60)
	keys_to_del.resize(n_to_del)
	while !keys_to_del.empty():
		var key = keys_to_del.pop_back()
		var x = key[0].to_int()
		var y = key[1].to_int()
		clear_cell(Vector2(x, y))

Como ya contamos con el problema modelado como un CSP (problema de satisfacción de restricciones), podemos obtener una lista de llaves del diccionario de dominios para obtener una lista de todas las celdas en la cuadrícula. Para elegir qué celdas borrar de manera aleatoria, barajamos la lista y seleccionamos un número aleatorio para ajustar el tamaño del arreglo. Esto es justo lo que sucede en la sección de la sección con if en la función. El número de llaves a borrar es seleccionado en base a la dificultad elegida, y después se llama a la función clear_cell con cada una de las llaves, la cual únicamente asigna el dominio de la celda al dominio inicial.

El resultado

El resultado es una cuadrícula única y que puede ser resuelta. Este algoritmo es algo sencillo con su acercamiento para generar sudokus y no es perfecto. No se toman medidas para asegurar que el puzzle generado tiene una sola posible solución. Este paso extra puede ser agregado al final para generar cuadrículas aún mejores, pero por el momento lo dejaré tal como está. Cualquiera es libre de tomar este algoritmo como un punto de inicio para un nuevo algoritmo capaz de generar sudokus.