Ruby Sudoku Solver

sample_output.txt

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

sample_output_jruby.txt

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

sudoku_cp.rb

# 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))