Skip to content

Instantly share code, notes, and snippets.

@pdsouza29
Created June 8, 2011 04:47
Show Gist options
  • Save pdsouza29/1013790 to your computer and use it in GitHub Desktop.
Save pdsouza29/1013790 to your computer and use it in GitHub Desktop.
Ruby Sudoku Solver
new-host-3:sudoku chaoticryld$ ruby sudoku_cp.rb
Running benchmarks...
0.698 secs to solve 50 easy puzzles (avg: 0.014 secs (71 Hz))
3.498 secs to solve 95 hard puzzles (avg: 0.037 secs (27 Hz))
0.176 secs to solve 11 hardest puzzles (avg: 0.016 secs (62 Hz))
ORIGINAL PUZZLE:
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
SOLUTION:
4 1 7 |3 6 9 |8 2 5
6 3 2 |1 5 8 |9 4 7
9 5 8 |7 2 4 |3 1 6
------+------+------
8 2 5 |4 3 7 |1 6 9
7 9 1 |5 8 6 |4 3 2
3 4 6 |9 1 2 |7 5 8
------+------+------
2 8 9 |6 4 3 |5 7 1
5 7 3 |2 9 1 |6 8 4
1 6 4 |8 7 5 |2 9 3
new-host-3:sudoku chaoticryld$ jruby --1.9 sudoku_cp.rb
Running benchmarks...
1.304 secs to solve 50 easy puzzles (avg: 0.026 secs (38 Hz))
2.698 secs to solve 95 hard puzzles (avg: 0.028 secs (35 Hz))
0.121 secs to solve 11 hardest puzzles (avg: 0.011 secs (90 Hz))
ORIGINAL PUZZLE:
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
SOLUTION:
4 1 7 |3 6 9 |8 2 5
6 3 2 |1 5 8 |9 4 7
9 5 8 |7 2 4 |3 1 6
------+------+------
8 2 5 |4 3 7 |1 6 9
7 9 1 |5 8 6 |4 3 2
3 4 6 |9 1 2 |7 5 8
------+------+------
2 8 9 |6 4 3 |5 7 1
5 7 3 |2 9 1 |6 8 4
1 6 4 |8 7 5 |2 9 3
# Preetam D'Souza
# 6.4.2011
# sudoku_cp.rb
$SIZE = 9
$COLORS = (1..$SIZE).to_a
$neighbors = Array.new($SIZE*$SIZE){[]} # num -> neighbors
$units = Array.new($SIZE*$SIZE){[[],[],[]]} # num -> [ROW, COL, SQUARE]
def display(grid)
sp = [['-'*6]*3]*"+"
grid.each_slice(9).each_with_index do |slice, index|
slice.each_slice(3).each_with_index do |s, i|
print s.inject {|z, n| [z, " ", n].join }
print " |" unless i==2
end
puts [2,5].include?(index) ? "\n"+sp : ""
end
end
def build_neighbors
### Build adjacency list based on row, col, and square constraints ###
(0...$SIZE).each do |r|
(0...$SIZE).each do |c|
v = $SIZE*r + c # node ID in [0, $SIZE*$SIZE)
f = -> x { $neighbors[x] << v unless (x == v || $neighbors[x].include?(v)) }
($SIZE*r...$SIZE*(r+1)).each {|x| f.call x; $units[v][0] << x } #ROWS
(0...$SIZE).map {|i| i*$SIZE+c}.each { |x| f.call x; $units[v][1] << x } #COLS
lr, lc = (r/3)*3, (c/3)*3
(0...3).each do |i|
(0...3).each { |j| f.call lr*$SIZE+lc+j+9*i; $units[v][2] << lr*$SIZE+lc+j+9*i } # SQUARES
end
end
end
end
def assign(choices, node, color)
erased = choices[node] - [color]
erased.each { |x| return false unless eliminate(choices, node, x) }
end
def eliminate(choices, node, color)
return choices unless choices[node].include?(color)
choices[node].delete(color)
return false if choices[node].empty?
if choices[node].size == 1 # only one color left -> eliminate it from neighbors
$neighbors[node].each do |n|
return false unless eliminate(choices, n, choices[node][0])
end
end
$units[node].each do |u|
slots = []
u.each { |x| slots << x if choices[x].include?(color) }
return false if slots.empty? # no place for this color
if slots.size == 1 # only one place for this color -> assign it
return false unless assign(choices, slots[0], color)
end
end
choices
end
def check(choices, neighbors)
choices.each_with_index do |c, i|
neighbors[i].each { |n| return false if choices[n] == c }
end
choices
end
def search(nodes, choices, neighbors, depth)
return check(choices.flatten, neighbors) if depth == $SIZE*$SIZE # SOLVED
n = nodes.min_by { |i| choices[i].size } # node with fewest color choices
choices[n].each do |c|
new_choices = choices.map { |x| x*1 } # deep copy hack
next unless assign(new_choices, n, c)
if potential = search(nodes - [n], new_choices, neighbors, depth+1)
return potential
end
end
false
end
def solve(grid)
choices = Array.new($SIZE*$SIZE){$COLORS.clone} # num -> available colors
### Assign given cells and propagate constraints ###
grid.each_with_index { |c, i| assign(choices, i, c.to_i) unless c =~ /[0.]/ }
### Search for a solution ###
search((0...$SIZE*$SIZE).to_a, choices, $neighbors, 0)
end
def test(file, name=file, sep="\n")
grids = IO.read(file).chomp.split(sep)
grids.map! { |x| x.chomp.split("").select {|c| c =~ /[0-9.]/ } }
t1 = Time.now
grids.each { |x| solve(x) }
elapsed = Time.now - t1
puts "%.5s secs to solve %d %s puzzles (avg: %.3f secs (%d Hz))" % [elapsed, grids.size, name,
elapsed/grids.size, grids.size/elapsed]
end
build_neighbors
puts "\nRunning benchmarks..."
test("easy50.txt", 'easy', '========')
test("top95.txt", 'hard')
test("hardest.txt", 'hardest')
grids = IO.readlines("top95.txt")
s = grids[0].chomp.split ""
puts "\nORIGINAL PUZZLE:"
display(s)
puts "\nSOLUTION:"
display(solve(s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment