Sudoku solver refactored from Luddite Geek and based on the Python solution by Peter Norvig.

gistfile1.rb

#!usr/bin/env ruby
# 2011-04-11 [email protected]

# 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][email protected]{|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 <<<"

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.

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.

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.