From: Knut erik Teigen <knutert@...>
Date: 2006-08-03T19:20:34+09:00
Subject: 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_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


-- 
Posted via http://www.ruby-forum.com/.