K
Knut erik Teigen
Hello
I've just started learning Ruby, and for a first project, I decided to
make a Sudoku solver. I've done this in Java before, and tried a similar
approach with Ruby. First, the program tries to solve the puzzle with
logic. This parts works fine, but when the logic fails, I try to use
brute force instead, using one of the familiar recursive/backtracking
algorithms that's found around the web. The problem is that the function
seems to terminate before completing the first row!
The code is pretty much identical to the Java code, so I guess it's
something about Ruby and variable declaration that I'm missing...
anyways, here's the recursive part of the program, hope you can help! If
you see anything that could be done in a more clever way apart from the
algorithm, please suggest it as well, I'm trying to learn all the nice
stuff in Ruby that makes life easier.
#!/usr/bin/ruby -w
def solve(i,j,grid)
#termination condition
if j==9 #completed one row, start next
j=0
i+=1
if i==9 #then we're done!
return true
end
end
#we don't want to test for given values, so
#jump to next cell
return solve(i,j+1,grid) if grid[i*9+j] != 0
#recursive part.
#check each value for this cell,
#if value gets set, continue with next cell
for value in 1..9
if possible(i,j,value,grid)
grid[i*9+j]=value
return true if solve(i,j+1,grid)
end
end
end
#checks if value can be placed in this cell without
#conflicts in rows, columns or boxes
def possible(i,j,value,grid)
#checks row
row = i*9
return false if grid[row...row+9].index(value)!=nil
#checks column
col = j
for i in 0..8
if grid[i*9+col]==value
return false
end
end
#checks box
#integer math to find start of box
i0=(i/3).to_i*3
j0=(j/3).to_i*3
for i in i0...i0+3
for j in j0...j0+3
if grid[i*9+j]==value
return false
end
end
end
#value not found, so it's a possible choice for this cell
return true
end
#prints grid to screen
def to_screen(grid)
string = ''
for i in 0..8
for j in 0..8
string += ' ' + grid[i*9 + j].to_s
end
puts string
string=''
end
end
#reads puzzle from textfile
def init_grid(filename)
input_file = File.new(filename,'r')
i=0
grid=Array.new
while line = input_file.gets
for num in line.split
grid=num.to_i
i+=1
end
end
return grid
end
filename = ARGV[0]
#Initialize simple array
grid = init_grid(filename)
puts "Problem to solve:"
to_screen(grid)
puts ''
if solve(0,0,grid)
puts "Problem solved!"
to_screen(grid)
else
puts "Couldn't solve problem..."
end
I've just started learning Ruby, and for a first project, I decided to
make a Sudoku solver. I've done this in Java before, and tried a similar
approach with Ruby. First, the program tries to solve the puzzle with
logic. This parts works fine, but when the logic fails, I try to use
brute force instead, using one of the familiar recursive/backtracking
algorithms that's found around the web. The problem is that the function
seems to terminate before completing the first row!
The code is pretty much identical to the Java code, so I guess it's
something about Ruby and variable declaration that I'm missing...
anyways, here's the recursive part of the program, hope you can help! If
you see anything that could be done in a more clever way apart from the
algorithm, please suggest it as well, I'm trying to learn all the nice
stuff in Ruby that makes life easier.
#!/usr/bin/ruby -w
def solve(i,j,grid)
#termination condition
if j==9 #completed one row, start next
j=0
i+=1
if i==9 #then we're done!
return true
end
end
#we don't want to test for given values, so
#jump to next cell
return solve(i,j+1,grid) if grid[i*9+j] != 0
#recursive part.
#check each value for this cell,
#if value gets set, continue with next cell
for value in 1..9
if possible(i,j,value,grid)
grid[i*9+j]=value
return true if solve(i,j+1,grid)
end
end
end
#checks if value can be placed in this cell without
#conflicts in rows, columns or boxes
def possible(i,j,value,grid)
#checks row
row = i*9
return false if grid[row...row+9].index(value)!=nil
#checks column
col = j
for i in 0..8
if grid[i*9+col]==value
return false
end
end
#checks box
#integer math to find start of box
i0=(i/3).to_i*3
j0=(j/3).to_i*3
for i in i0...i0+3
for j in j0...j0+3
if grid[i*9+j]==value
return false
end
end
end
#value not found, so it's a possible choice for this cell
return true
end
#prints grid to screen
def to_screen(grid)
string = ''
for i in 0..8
for j in 0..8
string += ' ' + grid[i*9 + j].to_s
end
puts string
string=''
end
end
#reads puzzle from textfile
def init_grid(filename)
input_file = File.new(filename,'r')
i=0
grid=Array.new
while line = input_file.gets
for num in line.split
grid=num.to_i
i+=1
end
end
return grid
end
filename = ARGV[0]
#Initialize simple array
grid = init_grid(filename)
puts "Problem to solve:"
to_screen(grid)
puts ''
if solve(0,0,grid)
puts "Problem solved!"
to_screen(grid)
else
puts "Couldn't solve problem..."
end
