From: "Kroeger, Simon (ext)" <simon.kroeger.ext@...>
Date: 2006-08-03T22:18:52+09:00
Subject: Re: What's wrong with this recursive function??


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