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
# author: Adam Shelly

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

def dprint(s)
#    print s
end

class BadGuessException < Exception
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 
    attr_reader :row, :col, :box, :possible
    def initialize(row, col, val=-1, max = 9)
        @row = row
        @col = col
        bounds = GetBoxBounds(max)
        @box = col/(bounds[0])+((row/bounds[1])*bounds[1])
        @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[0]
        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
    attr_reader :cell, :index
    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
value, so be the answer
            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
            rescue BadGuessException 
                dprint "#{@level} Bad Guess\n"
            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()) 
    rescue BadGuessException
        print "Malformed Puzzle\n"
    end
    
    print sol
    
end



--
-Adam

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
> 
>