Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
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

This comment has been minimized.

Copy link

attractivechaos commented Jun 17, 2011

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

This comment has been minimized.

Copy link
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