Crea Sudokus con Ruby

En pocos pasos podemos generar sudokus con ruby, estos serían generados automaticamente.

Este proyecto consta de dos archivos:

sudoku.rb Es la base del código y el encargado de generar los sudokus.

ranarray.rb Contiene las rutinas de aletoriedad.

Vamos a partir de la base que deseamos puzzles de tamaño 9×9.

Paso 1: Generar la solución

Nuestra primera tarea será crear la solución del puzzle. El código para generar la solución se encuentra aquí abajo y esta compuesto por tres funciones:

* available_values – calcula una lista de valores válidos para una determinada posición.
* get_least_valid encuentra las posiciones que poseen más dificultades.
* solve_puzzle recursivamente llena el puzzle, usando get_least_valid y comenzando cuando puzzles sin solución son detectadoss.

El código contiene una clase SudokuGrid con un array de 9×9 llamado @grid. El rango de valores utilizados es de 0 a 9, donde 0 significa que esa posición esta vacía. Hay varias rutinas y algunas de ellas tienen una pequeña explicación en el propio código.

# Dar una posición parcial comprobando una lista de entradas
# posicion (i,j)
def available_values(i,j)
valid_list=Array.new(9)
9.times do |ii|
val=@grid[i][ii]
if val!=0
valid_list[val-1]=1
end
val=@grid[ii][j]
if val!=0
valid_list[val-1]=1
end
end
block=SudokuGrid.get_block_indices(i,j)
3.times do |ii|
3.times do |jj|
val=@grid[3*block[0]+ii][3*block[1]+jj]
if val!=0
valid_list[val-1]=1
end
end
end
result=Array.new
9.times do |i|
if valid_list[i]!=1
result+=[i+1]
end
end
result
end

# Calcular el numero de posibles entradas
# devolver la posicion con la mayores entradas disponibles si el
# puzzle esta lleno, este devuelve (-1,-1). Si hay alguna posicion en 0
# entonces el puzzle estará sin resolver.
def get_least_valid
least_valid_indices=[-1,-1]
least_valid_array=Array.new(10)
9.times do |i|
9.times do |j|
if @grid[i][j]==0
vals=available_values(i,j)
if vals.length least_valid_indices=[i,j]
least_valid_array=vals
end
end
end
end
least_valid_indices
end

# Dar una solución parcial , encontrar una solucion usando aproximaciones
# que vayan rellenandolo
def solve_puzzle(idx)
if idx.length<2
return false
end
vals=available_values(idx[0],idx[1])
result=false
begin
if vals.length==0
@grid[idx[0]][idx[1]]=0
return false
end
index=(rand * vals.length).floor
the_val= vals[index]
@grid[idx[0]][idx[1]]=the_val
vals-=[the_val]
next_indices=get_least_valid
if next_indices[0]==-1
return true
end
result=solve_puzzle(next_indices)
end while result==false
return true
end

Ejecutando este código obtendríamos algo como esto:

>> sd=SudokuGrid.new
>> sd.solve_puzzle([0,0])
>> sd.print_self

3 7 8 6 1 2 5 4 9
1 9 4 3 8 5 6 7 2
6 2 5 9 7 4 3 1 8
7 4 1 8 2 6 9 5 3
2 8 3 1 5 9 4 6 7
5 6 9 7 4 3 8 2 1
8 5 6 2 3 1 7 9 4
9 3 2 4 6 7 1 8 5
4 1 7 5 9 8 2 3 6

Perfecto, ya podemos generar rapidamente una solución válida. Suponemos que son puzzles válidos porque verificarlos es una ardua tarea.

Paso 2: Confeccionar el puzzle

La segunda parte de la creación del puzzle es eliminar algunos elementos para que se pueda jugar con el. Hay dos problemas al eliminar elementos. El primero es que prentendemos eliminar elementos asegurandonos de que este continuará teniendo una única solución. Segundo que podamos eliminando teniendo en cuenta el nivel de dificultad del puzzle para poder tener diferentes niveles como (fácil, medio, dificil, etc)
¿Cómo podemos eliminar elementos asegurandonos una única solución?

Bien esto lo haríamos eliminando elementos de manera progresiva y contando el numero de soluciones validas. Si hay más de una, el elemento es remplzazado por otro, nosotros utilizaremos dos funciones principalmente para este paso:

* num_solutions – cuenta el numero de soluciones dadas por un puzzle parcialmente resuelto. Para asegurarnos de que solo hay una solucion programamos un trozo de código que nos permite saber cuando se detecta que el puzzle da mas de una solución.

* prune_puzzle esta función irá eliminando secuencialmente todos los elemendos que no introducen multiples soluciones.

Este es el código:

# Dado un trozo de puzzle correcto,determina cuantas soluciones tiene
# y detecta cuando más de una solución es detectada.
def num_solutions(idx,short_circuit)
vals=available_values(idx[0],idx[1])
if vals.length==0
return 0
end
solutions=0
for the_val in vals
@grid[idx[0]][idx[1]]=the_val
next_indices=get_least_valid
if next_indices[0]==-1
solutions+=1
else
solutions+=num_solutions(next_indices,short_circuit)
end
if short_circuit && solutions>1
@grid[idx[0]][idx[1]]=0
return solutions
end
end
@grid[idx[0]][idx[1]]=0
return solutions
end

# Dada un porción de puzzle elimina entradas aleatorias
# mientras estas no provoquen que el puzzle posea más de
# una solución.
def prune_puzzle
positions=Array.new
9.times do |i|
9.times do |j|
positions+=[[i,j]]
end
end
ns=1
for pos in positions.randomize
i=pos[0]
j=pos[1]
if @grid[i][j]!=0
val=@grid[i][j]
@grid[i][j]=0
ns=num_solutions([i,j],true)
if ns>1
@grid[i][j]=val
end
end
end
end

Esta es una posible respuesta del compilador al código dado:

>> sd.prune_puzzle
>> sd.print_self

3 7 8 2 5 9

6 2 5 7 3

2 3 5 9 7
5 1
8 3 1

4 7 8 2

Con esto generamos un puzzle en unos 5 a 10 segundos. Se nos plantea el problema de la dificultad, realmente no se como valorar el nivel de dificultad de un sudoku por eso dejemos este tema para los expertos…

Fuente del artículo