```Ok, I've seen a couple other solutions posted. Here is my code. I threw
this together pretty quick.

I start out by populating the board matrix with either the given value
or an array of possibilities. We then go through each row, column and
box eliminating possibilities from the unknown squares. If there is
ever only one possibility for a square we set that square to the now
known value. Next we go through each row, column and box to find
instances where a square has multiple possibilities, but for that set
one of these possibilities is the only one. So if a square has
possibilities of 2 and 7, but no other square in the same row can be 2
then this square must be 2 and not 7. We alternate between this process
and eliminating until we either find a solution or we have gone through
a loop without finding anything to change.

I'm not convinced that this fully solves ever puzzle. I'd be interested
in a proof though. (ie if a given sudoku board has only one possible
solution then this algorithm will find it) The next logical step would
be to brute force the rest of the puzzle looking for solutions. A Depth
First Search would work.

In any case. This was a good help for me learning ruby. I was
especially happy to find the set operators for arrays. That made my
day.

-----Horndude77

#!/usr/bin/env ruby

class Sudoku
def initialize(boardstring)
@board = Array.new(9)
9.times { |i| @board[i] = Array.new(9) }
flattened = boardstring.delete("-+|\n").split
index = 0
@unknown = []

# set up actual array
9.times do |i|
9.times do |j|
if(flattened[index] == '_') then
@board[i][j] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
@unknown << [i,j]
else
@board[i][j] = flattened[index].to_i
end
index += 1
end
end

#set up what each row, col, and box contains
@rows = Array.new(9)
@cols = Array.new(9)
@boxes = Array.new(9)
9.times { |i| @rows[i] = numsInRow(i) }
9.times { |j| @cols[j] = numsInCol(j) }
3.times { |i| 3.times { |j| @boxes[i+3*j] = numsInBox(3*i,3*j) } }
end

def numsInRow(row)
toreturn = []
9.times do |j|
if(@board[row][j].kind_of? Fixnum) then
toreturn << @board[row][j]
end
end
end

def numsInCol(col)
toreturn = []
9.times do |i|
if(@board[i][col].kind_of? Fixnum) then
toreturn << @board[i][col]
end
end
end

def numsInBox(boxrow, boxcol)
toreturn = []
x = boxrow - boxrow%3
y = boxcol - boxcol%3
3.times do |i|
3.times do |j|
if(@board[x+i][y+j].kind_of? Fixnum) then
toreturn << @board[x+i][y+j]
end
end
end
end

def to_s
s = ""
9.times do |i|
if(i%3 == 0) then
s += "+-------+-------+-------+\n"
end
9.times do |j|
if(j%3 == 0) then
s += "| "
end
if(@board[i][j].kind_of? Array) then
s += "_ "
else
s += "#{@board[i][j]} "
end
end
s += "|\n"
end
s += "+-------+-------+-------+\n"
return s
end

# Looks in row, column and box to eliminate impossible values
def eliminate(i,j)
changed = false
if(@board[i][j].kind_of? Array) then
combined = @rows[i] | @cols[j] | @boxes[(i/3)+(j-j%3)]
if( (@board[i][j] & combined).length > 0) then
changed = true
@board[i][j] -= combined
end

if(@board[i][j].length == 1) then
foundsolution(i,j,@board[i][j][0])
end
end
return changed
end

def foundsolution(x,y,val)
@board[x][y] = val
@rows[x] << @board[x][y]
@cols[y] << @board[x][y]
@boxes[(x/3)+(y-y%3)] << @board[x][y]
@unknown.delete([x,y])
end

def eliminateall
changed = true
while(changed)
changed = false
@unknown.each do |u|
if(eliminate(u[0],u[1])) then changed = true end
end
end
return changed
end

#these check functions look for squares that have multiple
# possibilities except the set itself only has one.
def checkrow(i)
changed = false
set = Hash.new
9.times do |j|
if (@board[i][j].kind_of? Array) then
@board[i][j].each do |e|
if(set[e]) then
set[e] << j
else
set[e] = [j]
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(i,v[0],k)
changed = true
end
end
return changed
end

def checkcol(j)
changed = false
set = Hash.new
9.times do |i|
if (@board[i][j].kind_of? Array) then
@board[i][j].each do |e|
if(set[e]) then
set[e] << i
else
set[e] = [i]
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(v[0],j,k)
changed = true
end
end
return changed
end

def checkbox(n)
x = 3*(n%3)
y = 3*(n/3)
changed = false
set = Hash.new
3.times do |i|
3.times do |j|
if (@board[x+i][y+j].kind_of? Array) then
@board[x+i][y+j].each do |e|
if(set[e]) then
set[e] << [x+i,y+j]
else
set[e] = [ [x+i,y+j] ]
end
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(v[0][0], v[0][1], k)
changed = true
end
end
return changed
end

def checkallrows
changed = false
9.times do |i|
if(checkrow(i)) then changed = true end
end
return changed
end

def checkallcols
changed = false
9.times do |j|
if(checkcol(j)) then changed = true end
end
return changed
end

def checkallboxes
changed = false
9.times do |n|
if(checkbox(n)) then changed = true end
end
return changed
end

def solve
#is there a better way to do this? it seems messy
# and redundant.
changed = true
while(changed && @unknown.length>0)
changed = false
changed = eliminateall ? true : changed
changed = checkallrows ? true : changed
changed = eliminateall ? true : changed
changed = checkallcols ? true : changed
changed = eliminateall ? true : changed
changed = checkallboxes ? true : changed
end
puts self
if(@unknown.length>0)
puts "I can't solve this one"
end
end
end