New Topic/Question
Reply
The algorithm is very basic:
- The solve function goes over every element from left to right, top to bottom.
- If it finds an element not filled in, it will make a list of all possible candidates ((1..9) but not present in row/column/block).
- Then it will call itself recursively with that element filled in for all possible elements.
- When there are no new indexes we have found a solution and add it to the list of solution.
Or shorter a depth first recursive search strategy.
If you just want the algorithm that finds 1 solution, you can instead of solutions.add(matrix) just do pp matrix and exit.
require 'pp'
def solve(matrix, x, y, solutions)
def nextIndex(x,y) #moves to the next index in 2d array
x += 1
if x > 8 then
y += 1
x = 0
end
if y > 8 then
raise StopIteration
end
return x,y
end
begin
while (matrix[x][y] != 0) do
x,y = nextIndex(x,y)
end
candidates = (1..9).to_a #initial
candidates = candidates - matrix[x] #prune
candidates = candidates - matrix.transpose[y] #prune
blockX = (x / 3).floor
blockY = (y / 3).floor
for i in (blockX*3..blockX*3+2)
for j in (blockY*3..blockY*3+2)
candidates.delete(matrix[i][j]) #prune
end
end
newX, newY = nextIndex(x,y)
candidates.each {|candidate|
newMatrix = Marshal.load(Marshal.dump(matrix)); #deep clone
newMatrix[x][y] = candidate
solve(newMatrix, newX, newY, solutions)
}
rescue StopIteration
solutions.push(matrix)
end
end
input = []
9.times do
line = gets.chomp
input.push(line.split(",", 9).map{|x| x.to_i})
end
solutions = []
solve(input, 0, 0, solutions)
solutions.each { |x|
pp x
}
This post has been edited by Karel-Lodewijk: 30 June 2011 - 07:09 PM
MultiQuote
| 