K

#### Knut erik Teigen

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