------art_125_11136010.1124762925385
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hi. This is my first attempt at a ruby quiz, and my first post to ruby-talk. 
I've been messing with ruby for about a year. I actually wrote a version of 
this solver with a fxwindows gui a while ago. The quiz was a good excuse to 
clean it up and refactor it to handle text input. 

It takes grids of almost arbitrary sizes upto 16 (and could be extended 
more). It doesn't do any guessing, so it never solves some of the posted 
programs. On the other hand, the official sudoku program from
www.soduku.com<http://www.soduku.com>tells me that those are not valid
puzzles, so I don't feel so bad. Anyway,
here it is:

#!/usr/bin/env ruby


# SodukuSolver.rb
# Solves soduku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)

#Utility function to define the inner sets of a grid
def GetGroupBounds(gridsize)
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 [5,2]
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

# 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, :group, :possible
def initialize(row, col, val=-1, max = 9)
@row = row
@col = col
bounds = GetGroupBounds(max)
@group = col/(bounds[0])+((row/bounds[1])*bounds[1])
@solved = false
case val
when 1..max
@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)
@possible.delete(n)
return hasFinalValue && !@solved
end

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

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


class Solver
def initialize(boardlist, size)
@groups =[]
@rows =[]
@cols = [] 
@queue = [] #a list of cells to check for solutions.
@size = size
0.upto(@size-1) { |n| @groups[n] = [] ; @rows[n]=[]; @cols[n]=[] }
r=c=0
boardlist.each do |v|
cell = Cell.new(r,c,v, size)
@groups[cell.group] <<@rows[r][c] = @cols[c][r] = cell
@queue << cell
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
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
eliminateChoiceFromGroup(@groups[cell.group], cell, value)
eliminateChoiceFromGroup(@rows[cell.row], cell, value)
eliminateChoiceFromGroup(@cols[cell.col], cell, value)
end
end

def eliminateChoiceFromGroup(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()
0.upto(@size-1) do |n|
findPairs(@rows[n])
findPairs(@cols[n])
findPairs(@groups[n])
findUniqueChoices(@rows[n])
findUniqueChoices(@cols[n])
findUniqueChoices(@groups[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)
0.upto(@size-1) do |i| 
if (!skipList.include?(i)) 
values.each {|v| eliminateValueFromCell(v, set[i])} 
end
end
end

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


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

#parses text file containing board. The only significant characters are _, 
0-9, A-Z.
#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
boardlist = [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=1
when ?0..?9
boardlist << c.to_i - ?0
col+=1
when ?_
boardlist << -1
col+=1
end
end
if (col > 0) then 
row+=1 
if (row == col) then break end
end
col=0
end
return boardlist,row
end

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

sol.show
sol.solve()
sol.show

end

--
-Adam Shelly

------art_125_11136010.1124762925385--