Kroeger, Simon (ext)
8/3/2006 1:19:00 PM
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