Create a gist now

Instantly share code, notes, and snippets.

Sudoku solver refactored from Luddite Geek and based on the Python solution by Peter Norvig.
#!usr/bin/env ruby
# 2011-04-11 jonelf@gmail.com
# Sudoku solver refactored from Luddite Geek http://theludditegeek.com/blog/?page_id=92
# and that in turn is a translation from the Python solution by Peter Norvig
# http://norvig.com/sudoku.html
## Throughout this program we have:
## r is a row, e.g. 'A'
## c is a column, e.g. '3'
## s is a square, e.g. 'A3'
## d is a digit, e.g. '9'
## u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
## grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7...
## values is a dict/hash of possible values, e.g. {'A1':'12349', 'A2':'8', ...}
ROWS = ('A'..'I')
COLS = ('1'..'9')
DIGITS = "123456789"
def cross(rows,cols)
cols.map {|x| rows.map {|y| y + x }}.flatten
end
@squares = cross(ROWS, COLS) # total of 81 squares
# rowset(9) + colset (9) + subgrids (9) - 27 total
nine_squares = ROWS.each_slice(3).map {|r| COLS.each_slice(3).map{|c| cross(r,c)}}.flatten(1)
@unitlist = COLS.map{|c| cross(ROWS,[c])} <<
ROWS.map{|r| cross([r], COLS)} <<
nine_squares
@units = @squares.inject({}) {|h, s| h[s]=@unitlist.select{|arr| arr.include?(s)};h}
# All on the same row, same column and same 1/9 unit except the square itself
@peers = @squares.inject({}) {|h,s| peers=(cross(ROWS,[s[1]]) <<
cross([s[0]],COLS) <<
nine_squares.select{|sq| sq.include?(s)} ).
flatten;
peers.delete(s);
h[s]=peers;
h}
def grid_values(grid)
# Convert grid into a dict of {square: char} with '0' or '.' for empties.
@squares.zip(grid.each_char.grep(/[0-9\.]/))
end
################ Constraint Propagation ################
def assign(values, s, d)
# eliminate all other values (except d) from values[s] and propogate
# return updated values, unless a contradiction is detected (then return false)
other_values = values[s].sub(d,'')
other_values.each_char do |d2|
return false unless eliminate(values, s, d2)
end
values
end
def eliminate(values, s, d)
# Eliminate digit from values list; propogate when # of values/places reduced to <= 2
# Return false if contradiction is detected; else return values
return values unless values[s].include?(d) ## Already eliminated
values[s] = values[s].sub(d,'')
## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
if values[s].size== 0
return false ## Contradiction: removed last value
elsif values[s].size == 1
d2 = values[s]
@peers[s].each do |s2|
return false unless (eliminate(values, s2, d2))
end
end
## (2) If a unit u is reduced to only one place for a value d, then put it there.
sa = [s]
@units[s].each do |u|
dplaces = values[s].include?(d) ? sa & u : []
## Contradiction: no place for this value
return values if dplaces.size == 0
if dplaces.size == 1
return false unless assign(values, dplaces[0], d)
end
end
values
end # def
################ Display Results as 2-D grid ################
def display(values)
#"Display these values as a 2-D grid."
#width = 2 since the "DG" and "36" are hardcoded anyway.
width = 2 #1 + values.max_by {|a| a.size}[1].size
puts line = [['-'*width*3]*3].join('+') # 81 square grid
ROWS.each do |r|
puts line if "DG".include?(r) # 3x3 grid
COLS.each do |c|
print values["#{r}#{c}"].center(width)
print '|' if '36'.include?(c)
end
puts
end
puts line
end
################ Utilities ################
def get_min(d)
# Find best candidate to process next (i.e. entry w least # of possible values) = steps are:
# 1) filter list - only select those with length > 1 (otherwise it's a solved square)
# 2) return key, value and length of shortest entry
min = d.select{|k,v| v.length>1}.
min_by{|h| h[1].length}
return min[0], min[1], min[1].length
end
################ Parse a Grid ################
def parse_grid (grid)
# Convert grid to a list of possible values and parses grid into a values dictionary
# the values hash/dict contains a text string of possible values for each cell
# if cell is completed then the string is 1 char long with the correct/solved value
# the grid is an array containing the initial/current?? value(s) defined in the puzzle
values = {} # define values dictionary
@squares.each do |s|
values[s] = DIGITS
end
grid_values(grid).each do |zg|
# extract cell names and values from zip grid array
s, d = zg
if DIGITS.include?(d)
return false unless assign(values, s, d)
end
end
values
end # parse_grid
################ Search Grid Values ################
def search(values)
# Depth first search and propagation
return false unless values ## Failed earlier
return values unless @squares.any?{|s| values[s].size != 1}
# For harder puzzles there is some more work to do
# Find the unfilled square s with the fewest possibilities
# and continue the search/elimination process
k,v,l = get_min(values)
v.each_char do |d|
r = search(assign(values.clone, k, d))
return r if r
end
return false
end # search def
require 'benchmark'
puts ">>>> Start <<<<"
# define set of test games
puzzles = %w{
003020600900305001001806400008102900700000008006708200002609500800203009005010300
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..
500000009020100070008000300040600000000050000000207010003000800060004020900000005
600302000040000080000000000702600000000000054300000000080150000000080200000000700
}
# .....6....59.....82....8....45........3........6..3.54...325..6..................
Benchmark.bm do |benchmark|
puzzles.each do |puzzle|
benchmark.report do
puts "Puzzle: #{puzzle}"
puts "Solution:"
display(search(parse_grid(puzzle)))
end
puts
end
end
puts ">>> Done <<<"
@jonelf
Owner
jonelf commented Apr 11, 2011

Test run at http://ideone.com/46grY but be aware that the last puzzle times out. It finishes in 8s on my machine, all the others finishes in a couple hundreds of a second.

@attractivechaos

Thanks for the example. Nonetheless, I think solving any puzzle in 8s does not sound right. Peter Norvig's python version solves that in 0.05 second. Another Ruby reimplementation solves the puzzle in a similar amount of time. Here is a Javascript implementation. You may test the speed.

@jonelf
Owner
jonelf commented Jun 17, 2011

Peter Norvig's python version solves that in 0.05 second.

Nice but kind of strange that at http://norvig.com/sudoku.html it says 188.79 seconds.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment