[QUIZ] Sodoku Solver (#43)

[Dominik Bathon]

Here is my solution.

It uses logic to deduce numbers for open cells which is enough for most =20
easy and intermediate sudokus (this is quite fast, usually <100ms), but i=
t =20
can also guess and backtrack to solve the hard ones and those with =20
multiple solutions.

The SudokuSolver class can solve sudokus for all valid square board sizes=
=20
(1x1, 4x4, 9x9, 16x16, ...), but the "if $0 =3D=3D __FILE__"-part only ha=
ndles =20
9x9 puzzles.

Dominik


The code:

class SudokuSolver

# sudoku is an array of arrays, containing the rows, which contain t=
he
# cells (all non valid entries are interpreted as open)
def initialize(sudoku)
# determine @n / @sqrt_n
@n =3D sudoku.size
@sqrt_n =3D Math.sqrt(@n).to_i
raise "wrong sudoku size" unless @sqrt_n * @sqrt_n =3D=3D @n

# populate internal representation
@arr =3D sudoku.collect { |row|
# ensure correct width for all rows
(0...@n).collect { |i|
# fixed cell or all values possible for open cell
((1..@n) =3D=3D=3D row) ? [row] : (1..@n).to_a
}
}

# initialize fix arrays
# they will contain all fixed cells for all rows, cols and boxes
@rfix=3DArray.new(@n) { [] }
@cfix=3DArray.new(@n) { [] }
@bfix=3DArray.new(@n) { [] }
@n.times { |r| @n.times { |c| update_fix(r, c) } }

# check for non-unique numbers
[@rfix, @cfix, @bfix].each { |fix| fix.each { |x|
unless x.size =3D=3D x.uniq.size
raise "non-unique numbers in row, col or box"
end
} }
end

# returns the internal representation as array of arrays
def to_a
@arr.collect { |row| row.collect { |x|
(x.size =3D=3D 1) ? x[0] : nil
} }
end

# returns a simple string representation
def to_s
fw =3D @n.to_s.size
to_a.collect { |row| row.collect { |x|
(x ? x.to_s : "_").rjust(fw)
}.join " " }.join "\n"
end

# returns whether the puzzle is solved
def finished?
@arr.each { |row| row.each { |x| return false if x.size > 1 } }
true
end

# for each cell remove the possibilities, that are already used in t=
he
# cell's row, col or box
# return if successful
def reduce
success =3D false
@n.times { |r| @n.times { |c|
if (sz =3D @arr[r][c].size) > 1
@arr[r][c] =3D @arr[r][c] -
(@rfix[r] | @cfix[c] | @bfix[rc2box(r, c)])
raise "impossible to solve" if @arr[r][c].empty?
# have we been successful
if @arr[r][c].size < sz
success =3D true
update_fix(r, c)
end
end
} }
success
end

# find open cells with unique elements in their row, col or box
# return if successful
# reduce must return false when this method is called (if the =20
possibilities
# aren't reduced, bad things may happen...)
def deduce
success =3D false
[:col_each, :row_each, :box_each].each { |meth|
@n.times { |i|
u =3D uniqs_in(meth, i)
unless u.empty?
send(meth, i) { |x|
if x.size > 1 && ((u2 =3D u & x).size =3D=3D 1)
success =3D true
u2
else
nil
end
}
# change only one row/col/box at a time
return success if success
end
}
}
success
end

# tries to solve the sudoku with reduce and deduce
# returns one of :impossible, :solved, :unknown
def solve
begin
until finished?
progress =3D false
while reduce
progress =3D true
end
progress =3D true if deduce
return :unknown unless progress
end
:solved
rescue
:impossible
end
end

# solves the sudoku using solve and if that fails, it tries to guess
# returns one of :impossible, :solved, :multiple_solutions
def backtrack_solve
if (res =3D solve) =3D=3D :unknown
# find first open cell
r, c =3D 0, 0
@rfix.each_with_index { |rf, r|
break if rf.size < @n
}
@arr[r].each_with_index { |x, c|
break if x.size > 1
}
partial =3D to_a
solutions =3D []
# try all possibilities for the open cell
@arr[r][c].each { |guess|
partial[r][c] =3D guess
rsolver =3D SudokuSolver.new(partial)
case rsolver.backtrack_solve
when :multiple_solutions
initialize(rsolver.to_a)
return :multiple_solutions
when :solved
solutions << rsolver
end
}
if solutions.empty?
return :impossible
else
initialize(solutions[0].to_a)
return solutions.size > 1 ? :multiple_solutions : :solve=
d
end
end
res
end

private

# returns the box index of row r and col c
def rc2box(r, c)
(r - (r % @sqrt_n)) + (c / @sqrt_n)
end

# if row r, col c contains a fixed cell, it is added to the fixed =20
arrays
def update_fix(r, c)
if @arr[r][c].size =3D=3D 1
@rfix[r] << @arr[r][c][0]
@cfix[c] << @arr[r][c][0]
@bfix[rc2box(r, c)] << @arr[r][c][0]
end
end

# yields each cell of row r and assigns the result of the yield unle=
ss =20
it
# is nil
def row_each(r)
@n.times { |c|
if (res =3D yield(@arr[r][c]))
@arr[r][c] =3D res
update_fix(r, c)
end
}
end
# yields each cell of col c and assigns the result of the yield unle=
ss =20
it
# is nil
def col_each(c)
@n.times { |r|
if (res =3D yield(@arr[r][c]))
@arr[r][c] =3D res
update_fix(r, c)
end
}
end
# yields each cell of box b and assigns the result of the yield unle=
ss =20
it
# is nil
def box_each(b)
off_r, off_c =3D (b - (b % @sqrt_n)), (b % @sqrt_n) * @sqrt_n
@n.times { |i|
r, c =3D off_r + (i / @sqrt_n), off_c + (i % @sqrt_n)
if (res =3D yield(@arr[r][c]))
@arr[r][c] =3D res
update_fix(r, c)
end
}
end

# find unique numbers in possibility lists of a row, col or box
# each_meth must be :row_each, :col_each or :box_each
def uniqs_in(each_meth, index)
h =3D Hash.new(0)
send(each_meth, index) { |x|
x.each { |n| h[n] +=3D 1 } if x.size > 1
nil # we didn't change anything
}
h.select { |k, v| v =3D=3D 1 }.collect { |k, v| k }
end

end

if $0 =3D=3D __FILE__
# read a sudoku from stdin
sudoku =3D []
while sudoku.size < 9
row =3D gets.scan(/\d|_/).map { |s| s.to_i }
sudoku << row if row.size =3D=3D 9
end
# solve
begin
solver =3D SudokuSolver.new(sudoku)
puts "Input:", solver
case solver.backtrack_solve
when :solved
puts "Solution:"
when :multiple_solutions
puts "There are multiple solutions!", "One solution:"
else
puts "Impossible:"
end
puts solver
rescue =3D> e
puts "Error: #{e.message}"
end
end

 

[Dominik Bathon]

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

But it is solvable:

Input:
_ 2 _ _ _ _ _ _ _
_ _ _ 6 _ _ _ _ 3
_ 7 4 _ 8 _ _ _ _
_ _ _ _ _ 3 _ _ 2
_ 8 _ _ 4 _ _ 1 _
6 _ _ 5 _ _ _ _ _
_ _ _ _ 1 _ 7 8 _
5 _ _ _ _ 9 _ _ _
_ _ _ _ _ _ _ 4 _
Solution:
1 2 6 4 3 7 9 5 8
8 9 5 6 2 1 4 7 3
3 7 4 9 8 5 1 2 6
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 3 9 4
2 6 9 3 1 4 7 8 5
5 4 8 7 6 9 2 3 1
7 3 1 8 5 2 6 4 9

 

[Adam Shelly]

But it is solvable:
=20

Since everyone pointed this out, I worked on my guessing code more.
Now I get
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+

Only Solveable by Guessing
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
real=090m0.203s
user=090m0.218s
sys=090m0.015s

And my previous slowest one went from 16.3s down to 0.37s
The newest slowest is
+-------+-------+-------+
| 7 _ _ | _ _ _ | _ 1 9 |
| 4 6 _ | 1 9 _ | _ _ _ |
| _ _ _ | 6 8 2 | 7 _ 4 |
+-------+-------+-------+
| _ 9 _ | _ _ _ | _ _ 7 |
| _ _ _ | 3 _ _ | 4 _ 5 |
| _ _ 6 | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ _ | _ _ _ |
| 2 _ _ | _ 7 4 | _ _ _ |
| _ _ _ | 2 _ _ | 3 _ _ |
+-------+-------+-------+

Only Solveable by Guessing
+-------+-------+-------+
| 7 8 2 | 4 5 3 | 6 1 9 |
| 4 6 5 | 1 9 7 | 8 2 3 |
| 3 1 9 | 6 8 2 | 7 5 4 |
+-------+-------+-------+
| 5 9 3 | 8 4 1 | 2 6 7 |
| 1 2 7 | 3 6 9 | 4 8 5 |
| 8 4 6 | 7 2 5 | 9 3 1 |
+-------+-------+-------+
| 6 7 1 | 9 3 8 | 5 4 2 |
| 2 3 8 | 5 7 4 | 1 9 6 |
| 9 5 4 | 2 1 6 | 3 7 8 |
+-------+-------+-------+
real=090m2.844s
user=090m2.858s
sys=090m0.015s

Should I post my third version, or is everyone sick of looking at my
code by now?

-Adam

 

[James Edward Gray II]

Should I post my third version, or is everyone sick of looking at my
code by now?

Please do. I can only talk about in the summary what I see.

James Edward Gray II

 

[Simon Kröger]

Should I post my third version, or is everyone sick of looking at my
code by now?

-Adam

You have been busy, hmm?

I also did some refactoring:

user system total real
solving nr 1 0.062000 0.000000 0.062000 ( 0.093000)
+-------+-------+-------+
| 1 4 6 | 9 2 8 | 3 7 5 |
| 5 9 3 | 6 1 7 | 8 4 2 |
| 8 7 2 | 4 3 5 | 9 1 6 |
+-------+-------+-------+
| 7 2 1 | 3 5 9 | 6 8 4 |
| 9 6 8 | 2 7 4 | 5 3 1 |
| 4 3 5 | 1 8 6 | 2 9 7 |
+-------+-------+-------+
| 2 5 7 | 8 9 1 | 4 6 3 |
| 3 8 4 | 7 6 2 | 1 5 9 |
| 6 1 9 | 5 4 3 | 7 2 8 |
+-------+-------+-------+
...
solving nr 30 1.235000 0.015000 1.250000 ( 1.281000)
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
...
solving nr 55 0.625000 0.016000 0.641000 ( 0.672000)
+-------+-------+-------+
| 9 3 5 | 1 7 2 | 8 6 4 |
| 2 1 6 | 9 8 4 | 7 5 3 |
| 4 7 8 | 6 5 3 | 2 9 1 |
+-------+-------+-------+
| 3 6 4 | 8 1 9 | 5 7 2 |
| 7 8 2 | 3 4 5 | 9 1 6 |
| 1 5 9 | 2 6 7 | 4 3 8 |
+-------+-------+-------+
| 8 9 3 | 7 2 6 | 1 4 5 |
| 5 2 7 | 4 3 1 | 6 8 9 |
| 6 4 1 | 5 9 8 | 3 2 7 |
+-------+-------+-------+
total 36.205000 0.172000 36.377000 ( 38.749000)
average 0.658273 0.003127 0.661400 ( 0.704527)

So it seems like your version is even faster than this, i would
like to see it.

here is mine (i'm especialy delighted on what can be done in 90
lines of code):

-------------------------------------------------------------------
require 'Set'
require 'Benchmark'

col = Array.new(9) {|o| Array.new(9){|i| o + i*9}}
row = Array.new(9) {|o| Array.new(9){|i| o*9 + i}}
box = Array.new(9) {|o| Array.new(9){|i|
(o / 3) * 27 + (o % 3) * 3 + ((i % 3) + (i / 3) * 9)}}

# this contains the 3 'neighbourhoods' (row/col/box)
# of each of the 81 cells
NEIGHBOURHOODS = Array.new(81) {|o|
[row[o / 9], col[o % 9], box[(o / 27) * 3 + (o % 9) / 3]]}

COMBINEDNEIGHBOURS = Array.new(81) {|o|
NEIGHBOURHOODS[o].flatten.uniq! - [o]}

class Board
attr_reader :cells, ossibilities

#initializes the cells and possibilities
def initialize c
@possibilities = Array.new(81) {(1..9).to_set}
@cells = Array.new(81, nil)
81.times{|i|set_cell(i, c) if c}
end

def initialize_copy(b)
@cells, p = b.cells.clone, b.possibilities
@possibilities = Array.new(81) {|i|Set.new(p)}
end

def to_s
"+-------+-------+-------+\n| " +
Array.new(3) do |br|
Array.new(3) do |r|
Array.new(3) do |bc|
Array.new(3) do |c|
cells[br*27 + r * 9 + bc * 3 + c] || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end

#recursively sets cell 'c' to 'v' and all trivial dependend cells
def set_cell c, v
cells[c], possibilities[c] = v, Set[v]
COMBINEDNEIGHBOURS[c].each{|i|possibilities.delete(v)}

COMBINEDNEIGHBOURS[c].each{|i|
set_cell(i, possibilities.min) if !cells &&
possibilities.size == 1}

return self
end

#solves with logic and brute force if neccessary',
#returns nil if unsolvable
def solve!
c = i = changed = 0
while i = ((i+1)..(changed+81)).find{|x|!cells[x % 81]}
NEIGHBOURHOODS[c = i % 81].each do |neighbours|
pn = neighbours.inject(possibilities[c].clone){|r, j|
(j != c) ? r.subtract(possibilities[j]) : r}
set_cell(changed = i = c, pn.min) && break if pn.size == 1
end
end

return self if cells.all?
return nil if possibilities.any?{|p| p.empty?}

p, i = possibilities.zip((0..80).to_a).select{|a, b|a.size > 1}.
min{|a, b|a[0].size <=> b[0].size}
p.each{|j| b=clone.set_cell(i, j).solve! and return b}
return nil
end
end

# main
count, $stdout.sync, total = 0, true, Benchmark::Tms.new
Benchmark.bm(15, "total", "average") do |bm|
loop do
cells = []
while !ARGF.eof? && (cells.size < 81) do
ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i.nonzero?}
end
break if ARGF.eof?
board = nil
total += bm.report("solving nr #{count+=1}") do
board = Board.new(cells).solve!
end
puts board ? board.to_s : "UNSOLVEABLE!" + "\n\n"
end
[total, total / count]
end
------------------------------------------------------------------

 

[Adam Shelly]

Adam Shelly wrote:
=20

Ok, here's my latest. My big speedup was figuring out that if I make
a bad guess, I just eliminate that possibility and re-solve. See the
startGuessing method..

It now solves #30 in 0.194s, and #55 in 0.124 ( I'm not sure which
puzzle you called #1)

here is mine (i'm especialy delighted on what can be done in 90
lines of code):

Mine definitely feels wordy to me at 370 lines:

#!/usr/bin/env ruby

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

def dprint(s)
print s if $DEBUG
end

class BadGuessException < Exception
end

#Utility function to define the box dimensions inside a grid
@@boxcols =3D 0 =20
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=20
print "GridSize of #{gridsize} unsupported. Exiting\n"
[0,0] =20
end
end
end
=20
# 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, :box, ossible
def initialize(row, col, val=3D-1, max =3D 9)
@row =3D row
@col =3D col
bounds =3D GetBoxBounds(max)
@box =3D col/(bounds[0])+((row/bounds[1])*bounds[1])
@processed =3D false
if (val.is_a?(Array))
@possible =3D val.dup=20
#if you don't dup here, you get big trouble
# when undoing guesses
elsif ((1..max) =3D=3D=3D val)
@possible =3D [val]
else
@possible =3D (1..max).to_a
end
end

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

def mark
@processed =3D true
end
=20
def set(toValue)
@possible =3D [toValue] if found =3D @possible.include?(toValue)
found
end
=20
def hasFinalValue
return @possible[0] if (@possible.length =3D=3D 1)
end
=20
def eliminate(n)
raise BadGuessException if (@possible.length =3D=3D 0)=20
@possible.delete(n)
hasFinalValue && !@processed
end
=20
def override(a)
@possible =3D a.dup
@processed =3D false
end
=20
def to_s
if $DEBUG
s =3D @possible.to_s;
s.length.upto(9) do s << " " end
"["+s+"]"
else
(v =3D hasFinalValue)?" "+v.to_s(32):" _"
end
end
def >(other)
return (@row > other.row || (@row =3D=3D other.row && @col > other.=
col))
end
end=20

class Guess
def initialize(cell )
@row,@col =3D cell.row,cell.col
@store =3D cell.possible.clone
@index =3D 0
end
def value
@store[@index]
end
def remove(cellset)
cell=3Dcellset[@row][@col]
cell.eliminate(value)
cell
end
def to_s
"Guess [#{@row},#{@col}] to be #{@store[@index]} from [#{@store}] "
end
end
=20

class Solver
def initialize(boardlist, size, presolved =3D false, lev=3D0)
@level =3D lev+1
@size =3D size
become(boardlist, presolved)
end
#helper for init and cloning
def become(boardlist, presolved =3D true)
@boxes =3D[]
@rows =3D[]
@cols =3D [] =20
@queue =3D [] #a list of cells to check for solutions.
@size.times{ |n| @boxes[n] =3D [] ; @rows[n]=3D[]; @cols[n]=3D[] =
}
r=3Dc=3D0
boardlist.each do |v|
cell =3D Cell.new(r,c,v, @size)
@boxes[cell.box] <<@rows[r][c] =3D @cols[c][r] =3D cell
@queue << cell
cell.mark if (presolved && cell.hasFinalValue)
c+=3D1
if (c=3D=3D@size) then c=3D0; r=3Dr+=3D1 end
end
end

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

def solve
while @queue.size > 0
while (cell =3D @queue.pop)
eliminateChoices(cell)=20
end
checkForKnownValues()
end
dprint "Solved to...\n#{self}"
return unsolved ? startGuessing : true
end
=20
#for any resolved cell, eliminate its value from the possible values=20
#of the other cells in the set
def eliminateChoices(cell)
if (value =3D cell.hasFinalValue)
cell.mark
[@boxes[cell.box],@rows[cell.row],@cols[cell.col]].each do |set=
|
eliminateChoiceFromSet(set, cell, value)
end
end
end
=20
def eliminateChoiceFromSet(g, exceptCell, n)
g.each {|cell| eliminateValueFromCell(n,cell) if cell !=3D exceptCe=
ll }
end
=20
def eliminateValueFromCell(value, cell)
@queue << cell if cell.eliminate(value) && [email protected]?(cell)
end
=20
def checkForKnownValues()
@size.times do |n|
[@rows[n],@cols[n],@boxes[n]].each do |set|
findPairs(set)
findUniqueChoices(set)
end
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) =20
#found a 2nd instance, no good=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,=20
#so let it be the 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+1).upto(@size-1) do |m|
if (set[n].possible.size =3D=3D 2 && set[n].possible =3D=3D
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 va=
lues
def eliminateExcept(set, skipList, values)
@size.times do |n| =20
if (!skipList.include?(n))=20
values.each {|v| eliminateValueFromCell(v, set[n])} =20
end
end
end
=20
def startGuessing
print "Only Solveable by Guessing\n" if @level =3D=3D 1
while (c =3D unsolved)=20
myclone =3D Solver.new(boardlist,@size, true,@level)
myguess =3D myclone.guess
return false if !myguess
dprint myclone
begin
if (myclone.solve)
become(myclone.boardlist)
return true
else=20
return false
end
rescue BadGuessException=20
#this is the big speedup - remove the bad guess=20
#from the possibilities, and re-solve
@queue << myguess.remove(@rows)=20
dprint "#{@level} Bad Guess\n #{self}"
return solve =20
end
end
end
=20
def guess
2.upto(@size) do |mincount|
@rows.each do |row|=20
row.each do |cell|
if cell.possible.size =3D=3D mincount
g =3D Guess.new(cell)
cell.set(g.value)
@queue << cell
return g
end
end
end
end
dprint "did not find a guess\n"
return nil
end

#formating (vertical line every cbreak)
def showBorder(cbreak)
s =3D "+"
1.upto(@size) do |n|
s << "--"
s<< "-+" if ((n)%cbreak =3D=3D 0)
end
s <<"\n"
end
=20
def to_s
r=3Dc=3D0
cbreak,rbreak =3D GetBoxBounds(@size)
s =3D showBorder(cbreak)
@rows.each do |row|=20
#r+=3D1
s << "|"
row.each do |cell|=20
c+=3D1
s << cell.to_s
if (c=3D=3Dcbreak) then s << " |";c=3D0; end
end
s<<"\n"
if (r+=3D1)=3D=3Drbreak then s << showBorder(cbreak); r=3D0; en=
d
end
s<<"\n"
s
end

def boardlist
a =3D []
@rows.each do |row|=20
row.each do |cell|=20
v =3D cell.hasFinalValue
a<< ( v ? v : cell.possible )
end
end
a
end
=20
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 rows.
def ParseBoard(file)
row =3D 0
col =3D 0
boxes =3D 0
boardlist =3D [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?0..?9
boardlist << c.to_i - ?0
col+=3D1
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=3D1
when ?a..?z
boardlist << c.to_i - ?a + 10
col+=3D1
when ?_
boardlist << -1
col+=3D1
when ?+
boxes+=3D1 if row =3D=3D 0
end
end
if (col > 0) then=20
row+=3D1=20
break if (row =3D=3D col)=20
end
col=3D0
end
@@boxcols =3D boxes-1
return boardlist,row
end

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

print sol
begin
print "UNSOLVABLE\n" if (!sol.solve())=20
rescue BadGuessException
print "Malformed Puzzle\n"
end
print sol
end
=20
--Adam

 

[Adam Shelly]

I should be doing real work, but.....

I found a big speedup for the worst cases. I was looking at the debug
output for puzzle 50.
+-------+-------+-------+
| 7 _ _ | _ _ _ | _ 1 9 |
| 4 6 _ | 1 9 _ | _ _ _ |
| _ _ _ | 6 8 2 | 7 _ 4 |
+-------+-------+-------+
| _ 9 _ | _ _ _ | _ _ 7 |
| _ _ _ | 3 _ _ | 4 _ 5 |
| _ _ 6 | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ _ | _ _ _ |
| 2 _ _ | _ 7 4 | _ _ _ |
| _ _ _ | 2 _ _ | 3 _ _ |
+-------+-------+-------+

I noticed that it spent a lot of time making wrong guesses and only
filling in the upper left corner.
So I made the guesser start with the center box instead. It went from
104 guesses to 36.

before:
$> for i in *.sdk; do time ruby SodukuSolver.rb $i ; done >btime 2>&1=20
$> ruby parsetime.rb btime
min max total ave
0.032 2.604 14.299 0.259


after:
min max total ave
0.031 0.938 12.667 0.230

And it was a simple change:
in Cell.initialize, replace
@box =3D col/(bounds[0])+((row/bounds[1])*bounds[1])
with
@box =3D (col/(bounds[0])+((row/bounds[1])*bounds[1])+max/2)%max
to make the box in the center have 0 index.

and replace the function Solver.guess so that it iterates over the
boxes instead of the rows:
def guess
=09=092.upto(@size) do |min|
[email protected] do |set|=20
=09=09=09=09set.each do |cell|
=09=09=09=09=09if cell.possible.size =3D=3D min
=09=09=09=09=09=09g =3D Guess.new(cell)
=09=09=09=09=09=09cell.set(g.value)
=09=09=09=09=09=09@queue << cell
=09=09=09=09=09=09dprint g
=09=09=09=09=09=09return g
=09=09=09=09=09end
=09=09=09=09end
=09=09=09end
=09=09end
=09=09dprint "did not find a guess\n"
return nil
end


Ok, I'm done now.
-Adam

 

[David Brady]

Should I post my third version, or is everyone sick of looking at my
code by now?

He posts an 8000% speed increase and he wants to know if we want to see
his code....

-dB

 

[David Brady]

--------------050804080601090803070903
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

My solution is 347 lines; I'll attach it below because I hate your mail
gateway.

You can view my complete solution on the web, however. My code, unit
tests, and board data are at
http://www.xmission.com/~dbrady/ruby/sodoku/sodoku.tgz . All of the
files in that archive are also at that url, so you can grab any of the
files directly by replacing sodoku.tgz with any of: sodoku.rb,
test_sodoku.rb, dbrady_solutions.txt, board1.txt, board2.txt,
board3.txt, board4.txt, board5.txt, board6.txt.

My strategy was to build an array of the possible moves for every row,
every column and every 3x3 block, then take their intersection. I
believe some other authors have already posted this concept; I'm only
posting because I appear to be the only person to do it using array
subtraction. I find the intersection that has the fewest options
available to it, and iterate over those choices, using recursion to
solve the rest of the board. Using a set probably would have been
better, but I didn't know about Ruby sets until after I finished my
code. So my solution is a very elegant way of wielding a stone axe.

My poor, unaccelerated laptop clocks in under 2s in most cases, and
rejects Karl von Lauderman's unsolvable puzzle in 200ms. The really
difficult one takes 33-38 seconds, depending on whether my mp3 player is
going.

One developmental note. Ruby continues to be an exceedingly pleasant
language to work and design in. I wrote a complete solver with loads of
unit tests, and I was pleased to discover that it could even solve
Karl's unsolvable puzzle. Nifty! As I was double-checking everything,
I realized that I had completely overlooked the requirement to have all
the cells in a *block* be unique! (I have never heard of Sodoku before
today.) I thought about it for a moment, then realized that all I
needed to do was add Sodoku#possible_block_values to the class, and make
sure that possible_values intersected that with the results from the
row/column query. I plugged in the extra code, and discovered that my
code became *faster* on account of rejecting more possibilities sooner.

I added another board, that seemed interesting to me to solve:

+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+

Also notably absent in my code is any kind of a custom Exception for bad
boards. They're not idiomatic for me so I used them very sparingly.

Anyway, without further ado, my solution is attached.

Cheers,

-dB
--
David Brady
(e-mail address removed)
I'm feeling really surreal today... OR AM I?


--------------050804080601090803070903
Content-Type: text/plain;
name="sodoku.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="sodoku.rb"

#!/usr/bin/env ruby

# sodoku.rb - Sodoku puzzle solver. Ruby Quiz #43.

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

# dbrady 2005-08-23: How my solver works: I try to find the fastest
# path to the solution by considering all of the possible solutions
# for each unsolved cell in the puzzle and working on the smallest
# set. For example, the top-left cell (0,0), in the sample above,
# only has two possible solutions: 3 and 9. All other digits are
# already present elsewhere in row 0 or column 0. No cells on the
# board have a single solution, so 2 is the shortest list. Many cells
# on this board have 2 solutions, for arbitrariness we'll take the
# first one we found.
#
# Now I consider all the possible solutions for that board. I create
# a new board object, set that cell to a possible value, and recurse
# into that board, asking it to solve itself.
#
# Sodoku#solution returns either a solved Sodoku object, or nil. If
# the top-level Sodoku board object returns nil, the puzzle is
# unsolvable.

# ----------------------------------------------------------------------
# A Note on Array Subtraction
# ----------------------------------------------------------------------
# This is published in the documentation for Array, but nobody ever
# reads that stuff (that's why nobody ever writes any). I discovered
# this by fiddling with it in irb. Array#- performs a difference
# operation. Every element in the lhs that appears in the rhs is
# removed.
#
# [2,3,4,5] - [4,5,6] => [2,3]
# [2,3,3,3,3,4] - [3] => [2,4] # EVERY element!
#
# I use this differencing op to obtain array intersection thusly:
#
# intersection = a - (a-b)
#
# You can immediately see how this is useful, given the nature of the
# puzzle.
#
# Anyway, if you see foo - [0], that's me clearing out all the
# unsolved cells from a list of cells.


# ======================================================================
# class Sodoku -
# ======================================================================
# class Sodoku - representation of a Sodoku puzzle. A Sodoku puzzle
# is a 9x9 grid, each containing numbers 1-9 such that every column
# and every row contains the complete set (1..9). Stated conversely,
# no column or row contains the same number twice.
#
# Given a partially completed Sodoku puzzle, the class can find a
# solution if any exists.
#
# A Sodoku puzzle displays itself (using #to_s) akin to this sample:
#
# +-------+-------+-------+
# | _ 6 _ | 1 _ 4 | _ 5 _ |
# | _ _ 8 | 3 _ 5 | 6 _ _ |
# | 2 _ _ | _ _ _ | _ _ 1 |
# +-------+-------+-------+
# | 8 _ _ | 4 _ 7 | _ _ 6 |
# | _ _ 6 | _ _ _ | 3 _ _ |
# | 7 _ _ | 9 _ 1 | _ _ 4 |
# +-------+-------+-------+
# | 5 _ _ | _ _ _ | _ _ 2 |
# | _ _ 7 | 2 _ 6 | 9 _ _ |
# | _ 4 _ | 5 _ 8 | _ 7 _ |
# +-------+-------+-------+
#
# The board rows and columns are numbered 0-8.
class Sodoku
attr_accessor :board

# initialize - ctor. Takes 1 arg, which is either a string
# containing the representation of the puzzle, or another Sodoku
# object, in which case we make a copy of its @board member.
def initialize(str = nil)
@board = []
9.times do |y|
@board[y] = [0,0,0,0,0,0,0,0,0]
end
self.load(str) if str.class == String
if str.respond_to? :board
self.copy_board(str)
end
end

# returns true if this board has no duplicates in any row or column.
def valid?
valid = true
return false unless @board.length == 9
@board.each do |row|
return false unless row.length == 9
row.each do |cell|
return false unless cell.class == Fixnum && cell<=9 && cell>=0
end
return false unless (row - [0]).uniq.length == (row - [0]).length
end
@board.transpose.each do |row|
return false unless (row - [0]).uniq.length == (row - [0]).length
end
3.times do |by|
3.times do |bx|
block = []
3.times do |y|
3.times do |x|
block.push @board[by*3+y][bx*3+x]
end
end
return false unless (block - [0]).uniq.length == (block - [0]).length
end
end
true
end

# returns true if any cell of this board has no solutions.
def unsolvable?
9.times do |y|
9.times do |x|
next unless @board[y][x].zero?
return true if self.possible_values(x,y).nil?
end
end
false
end

# find_pinch - returns an array of two Fixnums containing the (x,y)
# of the unsolved cell with the fewest possible solutions. If
# multiple cells tie for shortest solution, only one is returned.
# If board is solved, returns nil.
def find_pinch
pinch = nil
pinch_xy = nil
9.times do |y|
9.times do |x|
next unless @board[y][x].zero?
values = self.possible_values(x,y)
if pinch.nil? || pinch.length > values.length
pinch = values
pinch_xy = [x,y]
end
end
end
pinch_xy
end

# returns array of possible values at (x,y). If the cell is solved,
# the array will contain only the one element.
def possible_values(x,y)
pv = self.possible_row_values(y) - (self.possible_row_values(y) - self.possible_col_values(x))
pv -= (pv - self.possible_block_values(x,y))
return nil if pv.length.zero?
pv
end

# returns array of still-available values for this row. If the row
# is solved, returns empty array
def possible_row_values(y)
[1,2,3,4,5,6,7,8,9] - @board[y]
end

# returns array of still-available values for this col. If the col
# is solved, returns empty array
def possible_col_values(x)
vv = [1,2,3,4,5,6,7,8,9]
9.times do |row|
vv -= [@board[row][x]]
end
vv
end

# returns array of still-available values for the block that
# contains this cell. If the block is solved, returns empty array.
def possible_block_values(x,y)
vv = [1,2,3,4,5,6,7,8,9]
block_x = x/3
block_y = y/3
3.times do |y|
3.times do |x|
vv -= [@board[y+block_y*3][x+block_x*3]]
end
end
vv
end

# sets the value of cell (x,y) to val.
def set(x,y,val)
@board[y][x] = val
end

# Loads the @board array from a string matching the example above.
def load(str)
line_num = 0
str.each_line do |line|
line.gsub! '+', ''
line.gsub! '-', ''
line.gsub! '|', ''
line.gsub! ' ', ' '
line.gsub! '_', '0'
line.strip!
if line.length > 0
l = line.split
fail "Line length was #{l.length}" unless l.length == 9
@board[line_num] = l.collect {|x| x.to_i}
line_num += 1
end
end

fail "Board is not valid." unless self.valid?
end

# Returns the board as a string.
def to_s
s = ''
bar = "+-------+-------+-------+\n"
s += bar
9.times do |y|
s += sprintf("| %d %d %d | %d %d %d | %d %d %d |\n",
@board[y][0], @board[y][1], @board[y][2],
@board[y][3], @board[y][4], @board[y][5],
@board[y][6], @board[y][7], @board[y][8], @board[y][9] );
s += bar if y % 3 == 2
end
s.gsub! '0', '_'
s
end

# Returns true if board is solved.
def solved?
# trivially reject us if we're invalid.
return false unless self.valid?

# every row must contain (1..9)
@board.each do |row|
return false unless row.sort == [1,2,3,4,5,6,7,8,9]
end
# every col must contain (1..9)
@board.transpose.each do |col|
return false unless col.sort == [1,2,3,4,5,6,7,8,9]
end
# every block must containt (1..9)
3.times do |by|
3.times do |bx|
block = []
3.times do |y|
3.times do |x|
block.push @board[by*3+y][bx*3+x]
end
end
return false unless block.sort == [1,2,3,4,5,6,7,8,9]
end
end
end

# When you choose a trial value for a cell, sometimes other cells
# will end up with only a single solution. settle solves those
# cells. Settling a cell may cause other cells to become
# settleable, so settle repeats until the board "settles"
# completely.
#
# If all but one cell in a block are now settled, we could settle
# that block, but testing for this is too expensive.
def settle
settled = false
until settled
settled = true
9.times do |y|
9.times do |x|
if @board[y][x].zero?
pv = self.possible_values(x,y)
if !pv.nil? && pv.length == 1
# danger - if pv.nil?, we have invalidated the board.
# This may well be possible.
settled = false
self.set(x,y,pv[0])
end
end
end
end
end
end

# Returns an array depiction of the integer contents of @board (used
# primarily for debugging)
def board_array
s = ''
@board.each do |row|
s += " [" + row.join(', ') + "],\n"
end
s = '[' + s[1..-3] + ']'
end

# Returns first found solution, or nil if board is not solvable.
def solution
return self if self.solved?
return nil if self.unsolvable?

pinch = self.find_pinch
return nil if pinch.nil?
values = self.possible_values(pinch[0], pinch[1])

values.each do |value|
b = Sodoku.new
b.copy_board(self)
b.set(pinch[0], pinch[1], value)
b.settle
if b.valid? && b.solved?
return b
end

# not solved; recurse.
solution = b.solution
if !solution.nil? && solution.valid?
return solution
end
end
nil
end

def copy_board(other)
@board = []
other.board.each do |row|
@board.push( row.dup )
end
end

end

if $0 == __FILE__
# Read in board from STDIN, attempt solve and display output.
b = Sodoku.new(ARGF.readlines().join())
puts b
solution = b.solution
if !solution.nil?
puts "Solution:"
puts solution
else
puts "*** This board has no solution."
end
end

--------------050804080601090803070903--

 

[Gavin Kistner]

# Loads the @board array from a string matching the example above.
def load(str)
line_num = 0
str.each_line do |line|
line.gsub! '+', ''
line.gsub! '-', ''
line.gsub! '|', ''
line.gsub! ' ', ' '
line.gsub! '_', '0'
line.strip!
if line.length > 0
l = line.split
fail "Line length was #{l.length}" unless l.length == 9
@board[line_num] = l.collect {|x| x.to_i}
line_num += 1
end
end

fail "Board is not valid." unless self.valid?
end

How about just:
numbers = str.scan( /[\d_]/ ).collect{ |char| char.to_i }
and then check to see if you got 81 numbers or not (and split them up
into chunks of nine if you so desire).

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

 

[James Edward Gray II]

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

Or:
line.delete!("+-| ")

James Edward Gray II

 

[Gavin Kistner]

--Apple-Mail-1-555781126
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
format=flowed

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

Or:
line.delete!("+-| ")

Oooh, I didn't know/forgot about that method. Nice
--Apple-Mail-1-555781126--

 

[Mohit Muthanna]

My strategy was to build an array of the possible moves for every row,

every column and every 3x3 block, then take their intersection. I
believe some other authors have already posted this concept; I'm only
posting because I appear to be the only person to do it using array
subtraction. I find the intersection that has the fewest options
available to it, and iterate over those choices, using recursion to
solve the rest of the board. =20

Ahem... Mine used array subtraction too. Sorry.

--- SNIP (class Options) ----

def calculate_options_at( row, col )
(=20
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
board.row( row ) -=20
board.col( col ) -=20
board.region(=20
board.get_region_num( row, col )=20
)
)
end

--- SNIP -----

I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.

Also, there's less idiomatic Ruby here than there could / should be.
After re-reading this code I realize that some of these methods can be
reduced to one-liners.

Here it is (Download at http://muthanna.com/ruby-sudoku.tar.gz).

#!/usr/bin/env ruby

=3Dbegin rdoc
The Ruby Sudoku Solver

Mohit Muthanna Cheppudira <[email protected]>

Sudoku, Japanese, sometimes spelled Su Doku,=20
is a placement puzzle, also known as Number Place in the=20
United States. The aim of the puzzle is to enter a numeral=20
from 1 through 9 in each cell of a grid, most frequently a=20
9=D79 grid made up of 3=D73 subgrids (called "regions"), starting=20
with various numerals given in some cells (the "givens"). Each=20
row, column and region must contain only one instance of each=20
numeral.

To Learn more about Sudoku, visit the great Wikipedia.

This implementation of the Sudoku solver uses an educated brute
force approach. By educated brute-force, I mean the solver:

* Narrows down options available in the empty places
* Fills in cells that have only one option
* For cells that have more than one option:
* Try each one, then recurse (Narrow down, fill-in, etc.).

This file consists of five classes:

* Line: Represents a set of 9 cells. This could be a Row, a
Column, or a Region.

* Options: Represents a set of valid options for a cell. This is=20
meant to be used as a workspace or scratch-pad for the Solver.

* Board: Represents the 9x9 Sudoku board. Has helper methods
to access cells, rows, columns and regions.

* Csv: Utility class used to load boards from CSV files.

* Solver: Our educated brute-force solver.
=3Dend

module Sudoku


=3Dbegin rdoc

A Sudoku Line is basically an array that is
1-indexed. A Line could be a complete row, column or region.

=3Dend

class Line < Array

=3Dbegin rdoc
This class variable represents the set of digits that
are valid in a Sudoku cell.
=3Dend

@@valid_digits =3D [1, 2, 3, 4, 5, 6, 7, 8, 9]=20

=3Dbegin rdoc
We overload the [] operator so that the cells are
indexed from 1 till 9, instead of 0 till 8.
=3Dend

def []( num )
at( num - 1 )
end

=3Dbegin rdoc
The to_s method is called by other methods that
need a string representation of the class. E.g., puts()
=20
In this case, the code:

line =3D Line.new << 0 << 1 << 4 << 5
puts line
=20
Displays:
=20
0, 1, 4, 5
=3Dend

def to_s
self.join( ", " )
end

=3Dbegin
This method returns a list of missing digits
in the line.
=3Dend

def missing_digits
return @@valid_digits - self
end

=3Dbegin
Check if the Line or Region is
valid, i.e., has unique digits between
1 and 9, and has no zeros.

This method is used by the Solver to determine
if the solution is correct.
=3Dend

def valid?
digits =3D Array.new

# Navigate each cell:
(1..9).each do |value|

# Invalid if any zeros.
return false if self[value] =3D=3D 0=20

# Invalid if duplicate.
if digits[self[value]] =3D=3D true=20
return false
else=20
# First occurrence. Log it.
digits[self[value]] =3D true
end
end

# Valid Line.
return true
end
end

=3Dbegin rdoc
This class defines a basic 9 x 9 Sudoku
board. The board is subdivided into smaller
3 x 3 regions. These regions are numbered
from 1 to 9 as so: Top to Bottom, Left to Right.

e.g., Top Left is Region 1
The region beneath 1 (row 4, col 1) is 2
Top Middle is Region 4.

You get the picture.
=3Dend

class Board
def initialize( board =3D nil )
if board =3D=3D nil
reset
else
# Our copy constructor. In ruby all variables are
# references to classes. Copies have to be=20
# explicit.=20
reset
board.each {|row, col, val| self[row,col] =3D val}
end
end

=3Dbegin rdoc
Our board is represented by a two-dimensional 9x9 array.
=3Dend

def reset
@board =3D Array.new( 9 ) { Array.new( 9, 0 ) }
end

=3Dbegin rdoc
Cells in this board can be referenced with this method. Uses row, col; not =
x, y.
A bit retarded, but works.
=3Dend

def []( row, col )
return @board[col-1][row-1]
end

def []=3D( row, col, val )
return (@board[col-1][row-1] =3D val)
end

=3Dbegin
Draw up a simple ASCII Sudoku board.
=3Dend

def to_s
string =3D " 1 2 3 4 5 6 7 8 9\n"
string +=3D " +--------------------------\n"
filled_in =3D 0

(1..9).each do |r|=20
row( r ).each { |cell| filled_in +=3D 1 unless cell =3D=3D 0 }
string +=3D r.to_s + " | " + row( r ).to_s + "\n"
end

return string + "Filled: #{filled_in} / 81\n"
end

def row( row_num )
r =3D Line.new
(1..9).each { |c| r << self[ row_num, c ] }

return r
end

def col( col_num )
return Line.new( @board[ col_num - 1] )
end

=3Dbegin
Return a region (class Line) of cells determined
by a region number. The regions are numbered incrementally
top to bottom, left to right. So the cell at row 2, column
2 is at region 1; 5, 5 is region 5; 7, 4 is region 8.
=3Dend
def region( region_num )
region =3D Line.new

start_row =3D ((( (region_num - 1) % 3 )) * 3) + 1
start_col =3D (((region_num - 1) / 3) * 3) + 1

(start_row..start_row + 2).each do |row|
(start_col..start_col + 2).each do |col|
region << self[row, col]
end
end

return region
end

=3Dbegin
Return a region number given a row and column.
=3Dend
def get_region_num( row, col )
region_row =3D ( (row - 1) / 3 ) + 1
region_col =3D ( (col - 1) / 3 ) + 1

region_num =3D region_row + ( 3 * (region_col - 1))
end

=3Dbegin
Used to iterate through each cell on the board.
=3Dend
def each
(1..9).each do |row|
(1..9).each do |col|
yield row, col, self[row, col]
end
end
end

=3Dbegin rdoc
Go through each row, column and region to=20
determine if the board is valid.
=3Dend

def valid?
(1..9).each do |line|
return false if (
!row( line ).valid? ||
!col( line ).valid? ||
!region( line ).valid?=20
)
end

return true
end

end

=3Dbegin
This class loads a Sudoku board from a CSV file, A sample
board would look like this:

# Sample Board

0,0,0,0,2,3,4,0,0
0,6,3,0,9,8,0,0,0
4,0,0,5,0,0,0,0,0
0,2,5,0,8,0,0,7,3
0,1,0,0,0,0,0,5,0
6,4,0,0,5,0,1,9,0
0,0,0,0,0,5,0,0,8
0,0,0,9,7,0,3,6,0
0,0,6,8,3,0,0,0,0

Blank lines and lines beginning with hashes (#) are
ignored.

You can also save to CSV files by generating a=20
string via the to_s method.
=3Dend

class Csv
def initialize( board =3D nil )
if board =3D=3D nil
@board =3D Board.new
else
@board =3D board
end
end

def load( file_name )
File.open( file_name, "r" ) do |file|
row =3D 1

while line =3D file.gets

# Strip out all comments and
# blank lines.
line.chomp!
next if line =3D~ /^\s*#/
next if line =3D~ /^\s*$/

col =3D 1
line.split(",").each do |value|
@board[row, col] =3D value.to_i
col +=3D 1
end

row +=3D 1
end
end

@board
end

=3Dbegin rdoc
Generate a CSV string representing the board.
=3Dend
def to_s
string =3D ""

(1..9).each do |r|=20
string +=3D @board.row( r ).to_s + "\n"
end

return string=20
end
end

=3Dbegin
This class is represents a set of options for Sudoku cells. It's
simply a three dimensional array.
=3Dend

class Options
def initialize
@options =3D Array.new( 9 ) { Array.new( 9 ) { Array.new } }
end

def []( row, col )
return @options[col-1][row-1]
end
=20
def []=3D( row, col, val )
return (@options[col-1][row-1] =3D val)
end

def to_s
string =3D ""

(1..9).each do |row|
(1..9).each do |col|
string +=3D self[row, col].join(",") + ":"
end
string +=3D "\n"
end

string
end=20
end

=3Dbegin
Our Edumicated Brute-Force Sudoku Solver.
=3Dend

class Solver
=20
attr_accessor :board, ptions

def initialize( board=3Dnil )
if board
@board =3D board
else=20
@board =3D Board.new
end =20
=20
@options =3D Options.new
end

=3Dbegin rdoc
This method returns a list of digits that are valid inside
a specific cell. It works by subtracting the set of cells
in the specific row, column and region from a full-line, i.e,
[1, 2, 3, 4, 5, 6, 7, 8, 9].
=3Dend

def calculate_options_at( row, col )
(=20
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
board.row( row ) -=20
board.col( col ) -=20
board.region(=20
board.get_region_num( row, col )=20
)
)
end

=3Dbegin rdoc
This method navigates through each cell in the board,
calculating a set of options for the cell. For cells
that have just one available option:

* Set the cell with the available option.
* Recalculate options.

If no options could be calculated, we hit a dead-end; return
false.
=3Dend

def calculate_options
again =3D true
have_options =3D false

while again
again =3D false
self.options =3D Options.new

# Navigate each cell...
board.each do |row, col, value|

# If the cell is empty...
if value =3D=3D 0
=20
# Set the options for the cell
options[ row, col ] +=3D calculate_options_at( row, col )
end

# How many options do we have?
number_of_options =3D options[row, col].length

# We had atleast one option; set return code.
have_options =3D true if number_of_options > 0

# Only one option here, reflect it on the
# board.
if number_of_options =3D=3D 1
board[row, col] =3D options[row, col][0]
again =3D true
end
end
end

have_options
end

=3Dbegin rdoc
Our solve algorithm.=20
=3Dend
def brute_force

# First narrow the board down.
calculate_options

# Navigate each cell
board.each do |row, col, value|

# If we see and empty cell:
if value =3D=3D 0

# Navigate each option
options[row, col].each do |an_option|

# Save the state of the board, this is
# necessary because calculate_options()
# mangles the board.
old_board =3D Board.new( board )
=20
# Try this option
board[row, col] =3D an_option

# Recurse
return true if brute_force
=20
# No solution. Revert to saved board
# and try the next option.
@board =3D old_board
end

break
end

end

# Did we solve it?
return true if board.valid?=20
false
end

def solve
brute_force
end
end

=3Dbegin rdoc
Example code using this library. Reads a Sudoku-board file=20
from the command-line and solves it.
=3Dend

def Sudoku.main
puts "Ruby Sudoku Solver - 12 Aug 2005"
puts "Mohit Muthanna Cheppudira <[email protected]>"
puts

unless ARGV[0]
puts "Usage: #{$0} filename"
exit
end

# Load the board directly into the Solver.
solver =3D Solver.new( Csv.new().load( ARGV[0] ))

# Display the unsolved board.
puts "Problem:"
puts solver.board
=20
if solver.solve
puts "\nSolution:"
else
puts "\nNo Solution. Best match:"
end

# Display the final board.
puts solver.board
end

Sudoku.main

end

 

[David Brady]

Oooh, I didn't know/forgot about that method. Nice

These are all new to me. I learned Ruby by skimming the manual for the
syntax needed to express my C++ thinking in Ruby.

When I discovered gsub! took a regex, I went back and reread some of the
String documentation. I was going to use

line.squeeze ' '

But line.delete is more clear. I'll probably still use gsub! before it,
because to my thinking the proper behavior is to throw away all
characters that aren't digits. Dono... we're into "proper parsing of
invalid input" at this point. I only squeeze the whitespace because I
was using split() to break up the input. That may be unecessary (split
/\s+/) or avoidable (remove all whitespace, iterate over chars).

James, I'll edit the code, because these are nice changes. I hate to
spam the list, but I'm assuming that reposting is the preferred way to
update code for the Quiz, since you simply reference the web archive of
the post directly?

-dB

 

[David Brady]

Ahem... Mine used array subtraction too. Sorry.

Doh! I apologize for the oversight.

Well, at least I'm not the only stone-axe ninja here.

I am doing these quizzes as much to learn Ruby as anything else... I
especially like your use of rdoc. I need to pick that up next.

-dB

 

[James Edward Gray II]

James, I'll edit the code, because these are nice changes. I hate
to spam the list, but I'm assuming that reposting is the preferred
way to update code for the Quiz, since you simply reference the web
archive of the post directly?

Sure, feel free to repost. However, I've already edited that method
in the summary.

James Edward Gray II

 

[David Brady]

I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.

Our algorithms are essentially similar. One optimization I made is that
instead of attempting to solve the first empty cell seen, I skim over
all of the empty cells and find the one with the fewest possible
solutions. The value of this optimization appears to be a wash; most
boards I clock under your time by 20-50%, but on the "hard board" you
clock a 20s against my "more efficient" 37s. Wild. Something about
that puzzle forces any solver to grind deep and hard, and your not
taking extra time to think about the next move pays off handsomely.

Your calculate_options method seems to do what my settle method does,
finding unsolved cells with only one option. One question I had while
reading your code, what happens if your loop finds a cell with options,
then finds a cell to settle, and settling it causes the other cell to no
longer have options (but to be settled)? have_options is never reset.
The only valid case this can happen is if calculate_options solves the
puzzle, so you could probably test for it outside the method.

Hmm, you don't use the return value, so I guess the point is moot.

Also, I just noticed that the unit tests I uploaded yesterday were
broken, because I renamed the settle() method. (It used to be called
'flatten', but that has some existing semantics from Array#flatten.
Since they are not similar, I changed the name due to POLS.)

-dB
P.S. James, I made the changes to initialize; they are uploaded now.
For the list's benefit, here is the new load method:

# ----------------------------------------------------------------------
def load(str)
line_num = 0
str.each_line do |line|
line.gsub!('_','0')
line.delete!('+|-')
line.strip!
if line.length > 0
l = line.split /\s+/
fail "Line length was #{l.length}. line: #{line}" unless
l.length == 9
@board[line_num] = l.collect {|x| x.to_i}
line_num += 1
end
end

fail "Board is not valid." unless self.valid?
end
# ----------------------------------------------------------------------

 

[Mohit Muthanna]

solutions. The value of this optimization appears to be a wash; most

boards I clock under your time by 20-50%, but on the "hard board" you
clock a 20s against my "more efficient" 37s. Wild. Something about
that puzzle forces any solver to grind deep and hard, and your not
taking extra time to think about the next move pays off handsomely.

Interesting... thanks...

Your calculate_options method seems to do what my settle method does,
finding unsolved cells with only one option. One question I had while
reading your code, what happens if your loop finds a cell with options,
then finds a cell to settle, and settling it causes the other cell to no
longer have options (but to be settled)? have_options is never reset.

I initially wanted to use have_options within brute_force, basically
to tell me that the current iteration is a dead end. But then I found
an easier way out, and left it at that.

--=20
Mohit Muthanna [mohit (at) muthanna (uhuh) com]
"There are 10 types of people. Those who understand binary, and those
who don't."

 

[Dennis Ranke]

Here is my solution, it takes it's input in a file using

sudoku.rb [input file]

It solves the puzzles using some logic rules and brute force where needed.
As a small bonus it can also generate a puzzle by starting it with

sudoku.rb gen

The generator works by first letting the solver solve the empty puzzle
(and thereby generating a random solution) and then, again starting from
the emtpy puzzle, adding values from the solution to the puzzle until it
is solvable using logic alone.

---

class Cell
attr_reader :sets, :value, :mask

LOG2 = Math.log(2)

def initialize(mask)
self.mask = mask
@sets = []
end

def add_set(s)
@sets << s
end

def mask=(m)
@mask = m
@value = (Math.log(@mask) / LOG2).round + 1 if @mask & (@mask-1) == 0
end

def apply_mask(v)
return false if @mask & v == @mask
throw :failed if @mask & v == 0
self.mask = @mask & v
end

def choices
mask = @mask
c = []
while mask != 0
b = mask & ~(mask-1)
c << b
mask &= ~b
end
c
end
end

class Set
def initialize(cells)
@cells = cells
@open = cells.inject(0) {|m, c| m |= c.mask }
end

def simple_masking
mask = 0
@cells.delete_if do |c|
if v = c.value
b = 1 << (v-1)
throw :failed if @open & b == 0
@open ^= b
mask |= b
true
else
false
end
end
return false if mask == 0

@cells.each {|c| c.apply_mask(~mask) }
return true
end

def place_numbers
active = false
9.times do |n|
mask = 1 << n
next unless @open & mask != 0
cells = @cells.select {|c| c.mask & mask != 0}
if cells.size == 1
cells.first.apply_mask(mask)
active = true
end
next if cells.size <= 1
sets = cells.inject([]) {|a, c| a += c.sets}
sets.uniq!
sets.delete(self)
sets.each {|s| active |= s.mask_if_contains(cells, ~mask)}
end
active
end

def mask_if_contains(cells, mask)
my_cells = @cells.dup
cells.each do |c|
return false unless my_cells.delete(c)
end
active = false
my_cells.each {|c| active |= c.apply_mask(mask)}
active
end

def finished?
@cells.empty?
end
end

class Puzzle
attr_accessor :guessing_used

def initialize(board)
@board = board.map {|c| Cell.new(c) }

@sets = []
9.times do |i|
@sets << Set.new(@board[i*9, 9])

column = (0...9).map {|y| @board[y*9 + i]}
@sets << Set.new(column)

x = i % 3
y = i / 3
block = @board[x*3 + y*27, 3] + @board[x*3 + y*27 + 9, 3] +
@board [x*3 + y*27 + 18, 3]
@sets << Set.new(block)
end

@guessing_used = false
end

def solve
self.copy.solve!
end

protected

def solve!(try_brute_force = true)
catch :failed do
while run
# puts "\n---\n\n"
# puts self
end

return self if finished?

return false unless try_brute_force

best_cells = nil
best_choices_count = 10
@board.each do |c|
choices = c.choices
if choices.size > 1 && choices.size <= best_choices_count
best_cells = [] if choices.size < best_choices_count
best_cells << c
best_choices_count = choices.size
end
end

cell = best_cells[rand(best_cells.size)]
choices = cell.choices
until choices.empty?
c = choices.delete_at(rand(choices.size))
cell.mask = c
if solution = self.copy.solve!
solution.guessing_used = true
return solution
end
end
end

return nil
end

def run
active = false
@sets.each {|s| active |= s.simple_masking }
return true if active
@sets.each {|s| active |= s.place_numbers}
active
end

def copy
Puzzle.new(to_a)
end

public

def to_s
lines = (0...9).map do |y|
line = @board[y*9, 9].map do |c|
if v = c.value
v.to_s
else
'.'
end
end
(0...3).map {|i| line[i*3, 3].join}.join('|')
end
(0...3).map {|i| lines[i*3, 3].join("\n")}.join("\n---+---+---\n")
end

def finished?
@sets.all? {|c| c.finished? }
end

def to_a
@board.map {|c| c.mask}
end

def self.from_string(string)
board = string.scan(/[\.1-9]/)
raise unless board.size == 81
board = board.map do |c|
c == '.' ? 511 : 1 << (c.to_i - 1)
end
self.new(board)
end

def create_puzzle
solution = solve!.to_a

cells = (0...81).to_a
board = [511] * 81
loop do
cell = cells[rand(cells.size)]
board[cell] = solution[cell]
puzzle = Puzzle.new(board)
if puzzle.solve!(false)
return Puzzle.new(board)
else
b = puzzle.to_a
81.times do |i|
if b & (b - 1) == 0
cells.delete(i)
end
end
end
end
end

def self.create
self.new([511] * 81).create_puzzle
end
end

if ARGV[0] == 'gen'
puzzle = Puzzle.create
puts puzzle
exit
end

puzzle = File.read(ARGV[0]).gsub(/[+\-|\s]/, '').gsub(/\D/, '.')

puzzle = Puzzle.from_string(puzzle)

puts puzzle

start_time = Time.now
if solution = puzzle.solve
if solution.guessing_used
puts "\nSolved using guessing\n\n"
else
puts "\nSolved\n\n"
end
puts solution
else
puts "\nfailed to solve puzzle\n\n"
end
printf "%f seconds\n\n", Time.now - start_time

 

[Josef 'Jupp' SCHUGT]

Hi!

aargh. What happened to my tabs?

Vanished. Well-known problem in ASCII-artist communities.

Follows best current practice to prepare a Ruby program before
including it in the text of an e-mail. Valid for all e-mail programs
running in Emacsen:

1. mark whole program
2. issue 'M-x untabify'
3. mark whole program again
4. issue 'M-x comment-region'

This leaves the program readable while at the same time keeping the
whitespace intact.

Using 'M-x comment-region' makes sure that the whitespace is no
leading one. Some MUAs are known to remove *any* leading whitespace -
not just spaces!

For making the program runnable again 'M-x uncomment-region' is
suficient.

irb(main):001:0> algorithm.port(user.mua) == exercise(message.reader)
true

(^_^)

Josef 'Jupp' SCHUGT