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