# What's wrong with this recursive function??

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
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

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

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

#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

K

#### knutert te

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

T

#### ts

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_i*3
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

K

#### Kroeger, Simon (ext)

=20
From: Knut erik Teigen
Sent: Thursday, August 03, 2006 12:21 PM
=20
Hello
I've just started learning Ruby, and for a first project, I=20
Welcome!

#!/usr/bin/ruby -w
=20
def solve(i,j,grid)
=20
#termination condition
if j=3D=3D9 #completed one row, start next
j=3D0
i+=3D1
if i=3D=3D9 #then we're done!
return true
end
end
=20
#we don't want to test for given values, so
return solve(i,j+1,grid) if grid[i*9+j] !=3D 0
=20
#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]=3Dvalue
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]=3D0 is missing.
=20
end
=20
#checks if value can be placed in this cell without
#conflicts in rows, columns or boxes
def possible(i,j,value,grid)
=20
#checks row
row =3D i*9
return false if grid[row...row+9].index(value)!=3Dnil
=20
#checks column
col =3D j
for i in 0..8

if grid[i*9+col]=3D=3Dvalue
return false
end
end
=20
#checks box
#integer math to find start of box
i0=3D(i/3).to_i*3
j0=3D(j/3).to_i*3
for i in i0...i0+3
for j in j0...j0+3
if grid[i*9+j]=3D=3Dvalue
return false
end
end
end
=20
return true
=20
end
... snip ...

cheers

Simon

K

#### Kroeger, Simon (ext)

Hi again,

here is a little refined version:

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

#we don't want to test for given values, so
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]=3Dvalue
return true if solve(i, j+1, grid)
end
end
=20
grid[i*9+j]=3D0
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 =3D=3D value}

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

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

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

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

def init_grid(filename)
line.chomp.split.map{|num| num.to_i}
end.flatten
end

filename =3D 'input.txt'

#Initialize simple array
grid =3D 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

K

#### knutert te

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... 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!