# What's wrong with this recursive function?

**URL:** <https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076>\
**Category:** Ruby\
**Created:** [August 3, 2006, 12:20pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076 "2006-08-03T12:20:14Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 3, 2006, 12:20pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/1 "2006-08-03T12:20:14Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 3, 2006, 12:22pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/2 "2006-08-03T12:22:51Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 3, 2006, 2:23pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/3 "2006-08-03T14:23:42Z")

</div>

> > > > > “K” == Knut erik Teigen [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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\_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

---

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 3, 2006, 2:45pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/4 "2006-08-03T14:45:52Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 3, 2006, 3:21pm UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/5 "2006-08-03T15:21:57Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![knutert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a4c791/32.png) [@knutert](https://www.ruby-forum.com/u/knutert)\
**Post date:** [August 4, 2006, 10:24am UTC](https://www.ruby-forum.com/t/whats-wrong-with-this-recursive-function/101076/6 "2006-08-04T10:24:38Z")

</div>

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!