What's wrong with this recursive function?

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_i3
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[i]=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

Here’s an input file of a simple puzzle, btw…

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

“K” == Knut erik Teigen [email protected] writes:

very quickly look

K> #checks column
K> col = j
K> for i in 0…8
K> if grid[i*9+col]==value
K> return false
K> end
K> end

K> #checks box
K> #integer math to find start of box

 # 'i' is always == 8 (see the loop 'for')

K> i0=(i/3).to_i3
K> j0=(j/3).to_i
3

 # useless (#to_i) and false

moulon% ruby -e ‘i = 1; p i/3’
0
moulon%

K> for i in i0…i0+3

Guy Decoux

From: Knut erik Teigen
Sent: Thursday, August 03, 2006 12:21 PM

Hello
I’ve just started learning Ruby, and for a first project, I

Welcome!

end
if possible(i,j,value,grid)
  grid[i*9+j]=value
  return true if solve(i,j+1,grid)
end

end

You want to return nil or false here.
Plus something like grid[i*9+j]=0 is missing.

#checks column
col = j
for i in 0…8

this destroys your parameter ‘i’

for j in j0...j0+3

… snip …
cheers

Simon

Hi again,

here is a little refined version:


def solve(i,j,grid)
i, j = i+1, 0 if j == 9
return true if i == 9 #then we’re done!

#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].nonzero?

#recursive part.
#check each value for this cell,
#if value gets set, continue with next cell
(1…9).each do |value|
if possible(i, j, value, grid)
grid[i*9+j]=value
return true if solve(i, j+1, grid)
end
end

grid[i*9+j]=0
return false
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
return false if grid[i*9, 9].any?{|v| v == value}

#checks column
return false if (0…8).any?{|row| grid[row*9+j] == value}

#checks box
#integer math to find start of box
i0, j0=(i/3) * 3, (j/3) * 3

#last value is returned
(i0…i0+3).all? do |i|
grid[i*9+j0, 3].all?{|v| v != value}
end
end

#prints grid to screen
def to_screen(grid)
9.times{|i| puts grid[i*9, 9].join(’ ')}
end

#reads puzzle from textfile
def init_grid(filename)
IO.readlines(filename).map do |line|
line.chomp.split.map{|num| num.to_i}
end.flatten
end

filename = ‘input.txt’

#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

Hope that gives some new ideas…

cheers

Simon

Wow, thanks a lot for the help!
It’s typical, when you get so caught up in the algorithm, you miss
stupid errors like the i parameter…:stuck_out_tongue:

Thanks for the “ruby-fying” of the code, Simon. Right now, I find my own
version a bit more readable, but I guess that’s just because I’ve coded
in Java and C for so long. It’s definitely fun to code in Ruby, though,
so I’ll stick to it:)
Anyways, off to implement this in my OO-version!

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs