```Ok, I've updated my version to resort to guessing when it can't deduce
all the values.
It guesses pretty slowly, my worst time was
+-------+-------+-------+
| _ _ 1 | 2 _ _ | _ 6 _ |
| _ _ 9 | _ _ 8 | _ 4 _ |
| _ 5 _ | _ 4 _ | 9 _ _ |
+-------+-------+-------+
| 7 3 _ | _ 8 _ | _ _ _ |
| _ _ 5 | _ 3 _ | 1 _ _ |
| _ _ _ | _ 6 _ | _ 3 4 |
+-------+-------+-------+
| _ _ 3 | _ 2 _ | _ 9 _ |
| _ 2 _ | 8 _ _ | 5 _ _ |
| _ 9 _ | _ _ 1 | 4 _ _ |
+-------+-------+-------+

Only Solveable by Guessing
+-------+-------+-------+
| 8 4 1 | 2 5 9 | 3 6 7 |
| 3 7 9 | 6 1 8 | 2 4 5 |
| 2 5 6 | 7 4 3 | 9 8 1 |
+-------+-------+-------+
| 7 3 4 | 1 8 2 | 6 5 9 |
| 6 8 5 | 9 3 4 | 1 7 2 |
| 9 1 2 | 5 6 7 | 8 3 4 |
+-------+-------+-------+
| 1 6 3 | 4 2 5 | 7 9 8 |
| 4 2 7 | 8 9 6 | 5 1 3 |
| 5 9 8 | 3 7 1 | 4 2 6 |
+-------+-------+-------+

real    0m16.308s
user    0m16.311s
sys     0m0.015s

And it took a while to figure out that this one was unsolvable:
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+

UNSOLVABLE
+-------+-------+-------+
| _ 2 6 | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+

real    0m12.531s
user    0m12.514s
sys     0m0.030s

Here's the code.  (hope the tabs work this time - last time I pasted
directly from SciTE into gmail and lost them.  This time I went
through a plain text editor first...)
---
#!/usr/bin/env ruby

# SudokuSolver.rb

# Solves sudoku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)

def dprint(s)
#    print s
end

end

#Utility function to define the box dimensions inside a grid
@@boxcols = 0
def GetBoxBounds(gridsize)
if (@@boxcols > 0)
[gridsize/@@boxcols, @@boxcols]
else
case gridsize
when 1 then [1,1]
when 2 then [1,2]
when 4 then [2,2]
when 6 then [2,3]
when 8 then [2,4]
when 9 then [3,3]
when 10 then [2,5]
when 12 then [3,4]
when 14 then [2,7]
when 15 then [3,5]
when 16 then [4,4]
else
print "GridSize of #{gridsize} unsupported. Exiting\n"
[0,0]
end
end
end

# a Cell represents a square on the grid.
#  it keeps track of all possible values it could have.
#  it knows its grid location for convenience
class Cell
def initialize(row, col, val=-1, max = 9)
@row = row
@col = col
bounds = GetBoxBounds(max)
@box = col/(bounds)+((row/bounds)*bounds)
@solved = false
if (val.is_a?(Array))
@possible = val.dup #if you don't dup here, you get
big trouble when undoing guesses
elsif ((1..max) === val)
@possible = [val]
else
@possible = (1..max).to_a
end
end

def includes?(n)
@possible.include?(n)
end

def markSolved
@solved = true
end

def set(toValue)
if (found = @possible.include?(toValue))
@possible = [toValue];
end
return found
end

def hasFinalValue
if (@possible.length == 1)
return @possible
end
end

def eliminate(n)
raise BadGuessException if (@possible.length == 0)
@possible.delete(n)
return hasFinalValue && !@solved
end

def override(a)
@possible = a.dup
@solved = false
end

def to_s
(v = hasFinalValue)?" "+v.to_s(32):" _"
end

def show  #for debugging
s = @possible.to_s;
s.length.upto(9) do s << " " end
"(#{row},#{col})["+s+"]"
end

def >(other)
return (@row > other.row || (@row == other.row && @col > other.col))
end
end

class Guess
def initialize(cell )
@row = cell.row
@col = cell.col
@cell = cell
@store = @cell.possible.clone
@index = 0
end
def value
@store[@index]
end
def increment(cellset)
if (@index+1 < @store.size)
@index += 1
@cell=cellset[@row][@col] #because we may be on a cloned board
return true
end
end
def apply
@cell.set(value)
dprint "Applying #{self}\n"
return @cell
end
def to_s
"Guess [#{@row},#{@col}] to be #{@store[@index]} from [#{@store}] "
end
end

class Solver
def initialize(boardlist, size, presolved = false, lev=0)
@level = lev+1
@size = size
become(boardlist, presolved)
end

def become(boardlist, presolved = true)
@boxes =[]
@rows =[]
@cols = []
@queue = [] #a list of cells to check for solutions.
@size.times{ |n|  @boxes[n] = [] ; @rows[n]=[]; @cols[n]=[]    }
r=c=0
boardlist.each do |v|
cell = Cell.new(r,c,v, @size)
@boxes[cell.box] <<@rows[r][c] = @cols[c][r] = cell
@queue << cell
cell.markSolved if (presolved && cell.hasFinalValue)
c+=1
if (c==@size) then c=0;    r=r+=1 end
end
end

def solve
while @queue.size > 0
while (cell = @queue.pop)
eliminateChoices(cell)
end
checkForKnownValues()
end
dprint "Solved to...\n#{self}"
return startGuessing if (unsolved)
return true
end

def unsolved
@size.times do |n|
@boxes[n].each {|c| return c if !c.hasFinalValue}
end
nil
end

#for any resolved cell, eliminate its value from the possible
values of the other cells in the set
def eliminateChoices(cell)
value = cell.hasFinalValue
if (value)
cell.markSolved
eliminateChoiceFromSet(@boxes[cell.box], cell, value)
eliminateChoiceFromSet(@rows[cell.row], cell, value)
eliminateChoiceFromSet(@cols[cell.col], cell, value)
end
end

def eliminateChoiceFromSet(g, exceptThisCell, n)
g.each do |cell|
eliminateValueFromCell(n,cell) if (cell != exceptThisCell)
end
end

def eliminateValueFromCell(value, cell)
if (cell.eliminate(value) && !@queue.include?(cell))
@queue << cell    #if this cell is now resolved, put it on
the queue.
end
end

def checkForKnownValues()
@size.times do |n|
findPairs(@rows[n])
findPairs(@cols[n])
findPairs(@boxes[n])
findUniqueChoices(@rows[n])
findUniqueChoices(@cols[n])
findUniqueChoices(@boxes[n])
end
end

def findUniqueChoices(set)
1.upto(@size) do |n| #check for every possible value
lastCell = nil
set.each do |c|  #in every cell in the set
if (c.includes?(n))
if (c.hasFinalValue || lastCell)  #found a 2nd instance
lastCell = nil
break
end
lastCell = c;
end
end
#if true, there is only one cell in the set with that
if (lastCell && !lastCell.hasFinalValue)
lastCell.set(n)
@queue << lastCell
end
end
end

#find any pair of cells in a set with the same 2 possibilities
# - these two can be removed from any other cell in the same set
def findPairs(set)
0.upto(@size-1) do |n|
n.upto(@size-1) do |m|
if (n != m && set[n].possible.size == 2 &&
set[n].possible == set[m].possible)
eliminateExcept(set, [m,n], set[n].possible)
end
end
end
end

#for every cell in a set except those in the skiplist, eliminate the values
def eliminateExcept(set, skipList, values)
@size.times do |n|
if (!skipList.include?(n))
values.each {|v| eliminateValueFromCell(v, set[n])}
end
end
end

def startGuessing
myguess = nil
while (c = unsolved)
begin
myclone = Solver.new(boardlist,@size, true,@level)
myguess = myclone.guess(myguess)
if !myguess
dprint "did not find a guess\n"
return false
end
dprint myclone
if (myclone.solve)
print "Only Solveable by Guessing\n" if @level == 1
become(myclone.boardlist)
return true
elsif @level > 1
dprint "unwinding #{@level}\n"
return false
end
end
end
end

def guess(oldguess)
if (oldguess && oldguess.increment(@rows))
@queue << oldguess.apply
return oldguess
else
mincell = nil
mincount = @size+1
@size.times do |r|
@size.times do |c|
cell = @rows[r][c]
if (!cell.hasFinalValue && cell.possible.size <
mincount && (!oldguess || cell > oldguess.cell))
mincell = cell
mincount = cell.possible.size
end
end
end
if mincell
g = Guess.new(mincell)
@queue << g.apply
return g
end
end
return nil
end

#formating (vertical line every cbreak)
def showBorder(cbreak)
s = "+"
1.upto(@size) do |n|
s << "--"
s<< "-+" if ((n)%cbreak == 0)
end
s <<"\n"
end

def boardlist
a = []
@rows.each do |row|
row.each do |cell|
v = cell.hasFinalValue
if (v)
e = v
else
#~ e = cell.possible.clone  #if you don't clone
here you get a mess!
#~ e.freeze;
e = cell.possible
end
a<<e
end
end
a
end

def to_s
r=c=0
cbreak,rbreak = GetBoxBounds(@size)
s = showBorder(cbreak)
@rows.each do |row|
r+=1
s << "|"
row.each do |cell|
c+=1
s << cell.to_s
if (c==cbreak) then s << " |";c=0; end
end
s<<"\n"
if (r==rbreak) then s << showBorder(cbreak); r=0; end
end
s<<"\n"
s
end
end

#parses text file containing board.  The only significant characters
are _, 0-9, A-Z.
# if bounded by +---+---+---+, uses the + char to determine the layout
of the boxes
#there must be an equal number of significant chars in each line, and
the same number of many rows.
def ParseBoard(file)
row = 0
col = 0
boxes = 0
boardlist = [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?0..?9
boardlist << c.to_i - ?0
col+=1
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=1
when ?a..?z
boardlist << c.to_i - ?a + 10
col+=1
when ?_
boardlist << -1
col+=1
when ?+
boxes+=1 if row == 0
end
end
if (col > 0)  then
row+=1
break if (row == col)
end
col=0
end
@@boxcols = boxes-1
return boardlist,row
end

if __FILE__ == \$0
boardlist, size = ParseBoard(ARGF)
sol = Solver.new(boardlist, size)

print sol
begin
print "UNSOLVABLE\n" if (!sol.solve())
print "Malformed Puzzle\n"
end

print sol

end

--

On 8/22/05, James Edward Gray II <james / grayproductions.net> wrote:
> On Aug 22, 2005, at 9:08 PM, Adam Shelly wrote:
>
> > Hi. This is my first attempt at a ruby quiz, and my first post to
> > ruby-talk.
>
> Welcome to the Ruby community and thanks for the quiz submission!
>
> I'm not sure what happened to your tabs.  Did you just paste the code
> right into a message?
>
> James Edward Gray II
>
>

```