This is a ruby application that solves the
sudoku puzzle.
module Sudoku
# see http://en.wikipedia.org/wiki/Sudoku for a description of the puzzle
Puzzle = [ # region column 1 region column 2 region column 3
[ [ [0,0,0],[0,5,0],[0,0,6] ], [ [1,0,0],[0,9,0],[7,0,0] ], [ [7,4,0], [0,3,2], [9,0,0] ] ], # top 3 regions
[ [ [4,0,0],[0,2,0],[0,0,0] ], [ [8,0,0],[0,0,0],[0,0,9] ], [ [0,0,0], [0,1,0], [0,0,5] ] ], # middle 3 regions
[ [ [0,0,4],[7,3,0],[0,6,5] ], [ [0,0,7],[0,2,0],[0,0,4] ], [ [3,0,0], [0,6,0], [0,0,0] ] ] # bottom 3 regions
]
All_values = [1,2,3,4,5,6,7,8,9] # for computing the complement of 'cantbe' list
class Cell
attr :row
attr :col
attr :cantbe
attr :value
attr :value_at_level
attr :canbe
def initialize(row, col, value)
@row = row
@col = col
@value = value
@value_at_level = 0
@cantbe = []
end
def cantbe=(a)
@cantbe = a
set_canbe()
end
def value=(v)
@value = v
set_canbe()
end
def value_at_iteration(v, n)
@value = v
@value_at_level = n
set_canbe()
end
private
def set_canbe()
if @value == 0
@canbe = All_values - @cantbe # '-' means 'set difference'
else
@canbe = []
end
end
end
class Cells < Array
def initialize()
super
self[0..80] = [nil] * 81 # 9x9 mapped to a flat array so we can do .each
end
def prepare() # initialize the cantbe lists
self.each { |c| update_cantbe(c.row, c.col) }
end
def cell(r,c) # cell accessor
at(r * 9 + c)
end
def cells_in_row(row) # all cells in a row
ret = []
(0..8).each { |i| ret << cell(row, i) }
ret
end
def cells_in_col(col) # all cells in a column
ret = []
(0..8).each { |i| ret << cell(i, col) }
ret
end
def cells_in_region(row, col) # all cells in a 'region'
rowmod = (row.divmod(3)[0]) * 3
rowmax = rowmod + 2
colmod = (col.divmod(3)[0]) * 3
colmax = colmod + 2
ret = []
(rowmod..rowmax).each do |arow|
(colmod..colmax).each { |acol| ret << cell(arow, acol) }
end
ret
end
def try_value(row, col, v)
# see if a proposed value conflicts with the constraints
return false if cells_in_row(row).select { |c| c.value == v}.size > 0
return false if cells_in_col(col).select { |c| c.value == v}.size > 0
return false if cells_in_region(row,col).select { |c| c.value == v}.size > 0
return true
end
def update_cantbe(row,col) # update the cantbe list for a cell
t = cell(row, col) # make union of row,column,region values
t.cantbe = (cells_in_row(row).collect { |c| c.value } |
cells_in_col(col).collect { |c| c.value } |
cells_in_region(row, col).collect { |c| c.value }).delete_if { |v| v == 0 }
t.cantbe.size
end
def view() # display the grid on stdout
(0..8).each do |i|
puts cells_in_row(i).collect { |c| c.value }.join(' ')
end
end
end
class Solver
attr :cells
attr :fails
attr :weighted_fails
attr :tries
def initialize(a) # load the puzzle matrix
# expect a nested array structured like Puzzle
# Note : there are probably way easier representations.
@cells = Cells.new()
@fails = 0
@tries = 0
@weighted_fails = 0
bigrow = 0 # bigrow is region row = 0 .. 2
a.each do |rr|
bigcol = 0 # bigcol is region column = 0 .. 2
rr.each do |rc|
mainrow = bigrow * 3 # mainrow is matrix row = 0 .. 8
rc.each do |regrow|
maincol = bigcol * 3 # maincol is matrix column = 0 .. 8
regrow.each do |n|
c = Cell.new(mainrow, maincol, n)
@cells[mainrow * 9 + maincol] = c
maincol += 1
end
mainrow += 1
end
bigcol += 1
end
bigrow += 1
end
@cells.prepare()
end
def clear_iteration(iteration) # undo the values that were set at an iteration
@cells.select { |c| c.value_at_level == iteration }.each do |c|
c.value = 0
@cells.cells_in_row(c.row).each { |c2| @cells.update_cantbe(c2.row, c2.col) }
@cells.cells_in_col(c.col).each { |c2| @cells.update_cantbe(c2.row, c2.col) }
@cells.cells_in_region(c.row, c.col).each { |c2| @cells.update_cantbe(c2.row, c2.col) }
end
end
def select_cell_to_try() # return the cell with the shortest 'canbe' list
return @cells.select {|c| c.value == 0}.min { |c1,c2| c1.canbe.size <=> c2.canbe.size}
end
def solve(iteration, &block) # solve the puzzle
block.call(iteration, 1)
toTry = select_cell_to_try() # select a candidate cell
return true if toTry.nil? # all cells have values, so succeed
toTry.canbe.each do |v| # propose each 'canbe' value in turn
@tries += 1 # keep statistics
if @cells.try_value(toTry.row, toTry.col, v) # value works for this cell,
toTry.value_at_iteration(v, iteration) # so assign the value
if solve(iteration + 1,&block) # and see if it works for other cells
return true # it worked! we are done!
else
clear_iteration(iteration) # dang - reset the value
end
else
@fails += 1 # it didn't work. keep more statistics
end
end
@weighted_fails += iteration # keep mysterious useless statistics
block.call(iteration, -1)
return false # none of these values worked
end
end
end
if $0 == __FILE__
include Sudoku
p = Solver.new(Puzzle)
p.cells.view()
result = p.solve(1) do |iteration, way|
if way > 0
$stdout.write(iteration.modulo(10) != 0 ? "." : "|")
else
$stdout.write("\b \b")
end
$stdout.flush()
end
puts ""
if result
puts "Solved puzzle"
p.cells.view()
else
puts "Failed to solve puzzle"
end
puts "Statistics : tries = #{p.tries} fails = #{p.fails} weighted_fails = #{p.weighted_fails}"
end
If you run it from the command-line you will see the following:
C:\bin\eclipse\workspace\sudoku>sudoku.rb
0 0 0 1 0 0 7 4 0
0 5 0 0 9 0 0 3 2
0 0 6 7 0 0 9 0 0
4 0 0 8 0 0 0 0 0
0 2 0 0 0 0 0 1 0
0 0 0 0 0 9 0 0 5
0 0 4 0 0 7 3 0 0
7 3 0 0 2 0 0 6 0
0 6 5 0 0 4 0 0 0
.........|.........|.........|.........|.........|......
Solved puzzle
3 9 2 1 8 5 7 4 6
8 5 7 4 9 6 1 3 2
1 4 6 7 3 2 9 5 8
4 7 9 8 5 1 6 2 3
5 2 8 6 7 3 4 1 9
6 1 3 2 4 9 8 7 5
2 8 4 5 6 7 3 9 1
7 3 1 9 2 8 5 6 4
9 6 5 3 1 4 2 8 7
Statistics : tries = 3611 fails = 1194 weighted_fails = 59325
It takes about 20 seconds on an athlon 3000.
Books RSS
