From: Adam Shelly <adam.shelly@...>
Date: 2005-08-23T11:08:48+09:00
Subject: Re: [QUIZ] Sodoku Solver (#43)

------=_Part_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=
.=20
I've been messing with ruby for about a year. I actually wrote a version of=
=20
this solver with a fxwindows gui a while ago. The quiz was a good excuse to=
=20
clean it up and refactor it to handle text input.=20

It takes grids of almost arbitrary sizes upto 16 (and could be extended=20
more). It doesn't do any guessing, so it never solves some of the posted=20
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=20
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=20
attr_reader :row, :col, :group, :possible
def initialize(row, col, val=3D-1, max =3D 9)
@row =3D row
@col =3D col
bounds =3D GetGroupBounds(max)
@group =3D col/(bounds[0])+((row/bounds[1])*bounds[1])
@solved =3D false
case val
when 1..max
@possible =3D [val]
else
@possible =3D (1..max).to_a
end
end

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

def markSolved
@solved =3D true
end

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

def hasFinalValue
if (@possible.length =3D=3D 1)
return @possible[0]
end
end

def eliminate(n)
@possible.delete(n)
return hasFinalValue && !@solved
end

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

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


class Solver
def initialize(boardlist, size)
@groups =3D[]
@rows =3D[]
@cols =3D []=20
@queue =3D [] #a list of cells to check for solutions.
@size =3D size
0.upto(@size-1) { |n| @groups[n] =3D [] ; @rows[n]=3D[]; @cols[n]=3D[] }
r=3Dc=3D0
boardlist.each do |v|
cell =3D Cell.new(r,c,v, size)
@groups[cell.group] <<@rows[r][c] =3D @cols[c][r] =3D cell
@queue << cell
c+=3D1
if (c=3D=3Dsize) then c=3D0; r=3Dr+=3D1 end
end
end

def solve
while @queue.size > 0
while (cell =3D @queue.pop)
eliminateChoices(cell)=20
end
checkForKnownValues()
end
end

#for any resolved cell, eliminate its value from the possible values of the=
=20
other cells in the set
def eliminateChoices(cell)
value =3D 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|=20
eliminateValueFromCell(n,cell) if (cell !=3D 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 =3D nil
set.each do |c| #in every cell in the set
if (c.includes?(n))
if (c.hasFinalValue || lastCell) #found a 2nd instance=20
lastCell =3D nil
break
end
lastCell =3D c;
end=20
end=20
#if true, there is only one cell in the set with that value, so be the=20
answer
if (lastCell && !lastCell.hasFinalValue)=20
lastCell.set(n)
@queue << lastCell
end
end
end=20

#find any pair of cells in a set with the same 2 possibilities=20
# - 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 !=3D m && set[n].possible.size =3D=3D 2 && set[n].possible =3D=3D=20
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|=20
if (!skipList.include?(i))=20
values.each {|v| eliminateValueFromCell(v, set[i])}=20
end
end
end

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


def show
r=3Dc=3D0
cbreak,rbreak =3D GetGroupBounds(@size)
s =3D showBorder(cbreak)
@rows.each do |row|=20
r+=3D1
s << "|"
row.each do |cell|=20
c+=3D1
s << cell.show
if (c=3D=3Dcbreak) then s << " |";c=3D0; end
end
s<<"\n"
if (r=3D=3Drbreak) then s << showBorder(cbreak); r=3D0; end
end
s<<"\n"
print s
end
end

#parses text file containing board. The only significant characters are _,=
=20
0-9, A-Z.
#there must be an equal number of significant chars in each line, and the=
=20
same number of many rows.
def ParseBoard(file)
row =3D 0
col =3D 0
boardlist =3D [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=3D1
when ?0..?9
boardlist << c.to_i - ?0
col+=3D1
when ?_
boardlist << -1
col+=3D1
end
end
if (col > 0) then=20
row+=3D1=20
if (row =3D=3D col) then break end
end
col=3D0
end
return boardlist,row
end

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

sol.show
sol.solve()
sol.show

end

--
-Adam Shelly

------=_Part_125_11136010.1124762925385--