Fast and compact Sudoku solver. I wrote it after seeing the example in "The Ruby Programming Book" to find out how much simpler and cleaner it could be made. I have improved it sligthly later and added a generator just for fun.

sudoku.rb

# Compact Sudoku solver and generator
#
# Written by Patrik Rak in 2009 to test the power of Ruby

class Sudoku

  # Dimensions.
  B = 3
  N = B * B
  SIZE = N * N
  
  # Tables mapping position index to row, column and block indices, respectively.
  RINDEX = []
  CINDEX = []
  BINDEX = []

  for i in 0...SIZE
    row = i / N
    col = i % N
    RINDEX[ i ] = row
    CINDEX[ i ] = col
    BINDEX[ i ] = row / B * B + col / B
  end
  
  # Array mapping each possible square value to corresponding bit mask.
  BITS = ( 0 .. N ).map{ |n| 1 << ( n - 1 ) }

  # Table of arrays of remaining choices for each combination of set bits already taken.
  CHOICES = ( 0 ... ( 1 << N ) ).map do |i|
    ( 1 .. N ).select{ |n| ( i & BITS[ n ] ) == 0 }.freeze
  end
  
  # Create new puzzle, optionally filling it according to given array of digits.
  def initialize( a = nil )
    clear
    init( a ) if a
  end
  
  # Turn dup and clone copy into a deep copy.
  def initialize_copy( other )
    @a = @a.dup
    @c = @c.dup
    @r = @r.dup
    @b = @b.dup
  end
  
  # Properly freeze the object.
  def freeze
    [ @a, @c, @r, @b ].each{ |x| x.freeze }
    super
  end
  
  # Clear the puzzle board entirely.
  def clear
    @a = Array.new( SIZE, 0 )
    @c = Array.new( N, 0 )
    @r = Array.new( N, 0 )
    @b = Array.new( N, 0 )
    self
  end
  
  # Initialize empty puzzle from given array of digits.
  def init( a )
    a = a.to_a
    fail( ArgumentError, "invalid array size" ) unless a.size == SIZE
    a.each_with_index do |n,i|
      set( i, n )
    end
    self
  end
  
  # Turn the puzzle into an array of digits.
  def to_a
    @a.dup
  end
  
  # Create printable representation of the puzzle.
  def to_s
    @a.each_slice( N ).map{ |x| "#{x.join}\n" }.join
  end
  
  # Compute position index for given row and column.
  def index( row, col )
    fail( ArgumentError, "invalid position [#{row},#{col}]" ) unless [ row, col ].all?{ |x| x.between?( 0, N - 1 ) }
    ( row * N ) + col
  end
  
  # Get value of given puzzle square.
  def []( row, col )
    get( index( row, col ) )
  end
  
  # Set value of given puzzle square.
  def []=( row, col, n )
    set( index( row, col ), n )
  end
  
  # Get value of square at given position.
  def get( i )
    @a[ i ] or fail( ArgumentError, "invalid index #{i}" )
  end
  
  # Set value of square at given position.
  def set( i, n )
    n = n.to_i
    o = get( i )
    return self if o == n
    fail( ArgumentError, "invalid value #{n}" ) unless n == 0 or choices( i ).include?( n )
    delete( i, o ) if o > 0
    insert( i, n ) if n > 0
    self
  end
  
  private
  
  # Set value of square at given position, no checks applied.
  def insert( i, n )
    mask = BITS[ n ]
    @a[ i ] = n
    @c[ CINDEX[ i ] ] |= mask
    @r[ RINDEX[ i ] ] |= mask
    @b[ BINDEX[ i ] ] |= mask
  end
  
  # Remove given value from square at given position, no checks applied.
  def delete( i, n )
    mask = ~BITS[ n ]
    @a[ i ] = 0
    @c[ CINDEX[ i ] ] &= mask
    @r[ RINDEX[ i ] ] &= mask
    @b[ BINDEX[ i ] ] &= mask
  end
  
  public
  
  # Get array of all valid remaining choices for square at given position.
  def choices( i )
    CHOICES[ @c[ CINDEX[ i ] ] | @r[ RINDEX[ i ] ] | @b[ BINDEX[ i ] ] ]
  end

  # Get the sum of degrees of freedom for square at given position.
  def degrees( i )
    [ @c[ CINDEX[ i ] ], @r[ RINDEX[ i ] ], @b[ BINDEX[ i ] ] ].map{ |x| CHOICES[ x ].count }.sum
  end

  # Suggest where and which values should we try to put next to solve the puzzle.
  # Returns nil index if the puzzle is already solved, and eventually empty choices if there is no solution.
  def scan
    best_count = best_degree = SIZE
    for i in 0...SIZE
      next if @a[ i ] > 0
      c = choices( i )

      count = c.size
      next if count > best_count

      degree = degrees( i )
      next if count == best_count && degree >= best_degree

      best_count = count
      best_degree = degree
      best_index = i
      best_choices = c

      break if best_count <= 1
    end
    [ best_index, best_choices ]
  end
  
  # Yield all solutions of the puzzle to given block. Beware, modifies self during the process.
  def solve( &block )
    index, choices = scan
    
    unless index
      yield dup
      return
    end

    for n in choices
      insert( index, n )
      solve( &block )
      delete( index, n )
    end
  end
  
  # Get enumerator of all solutions of the puzzle.
  def solutions
    dup.enum_for( :solve )
  end
  
  # Get solution of the puzzle, or nil if there is none.
  def solution
    solutions.first
  end
  
  # Test if the puzzle has a unique solution.
  def proper?
    solutions.first( 2 ).size == 1
  end
  
  # Randomly fill the diagonal blocks of an empty puzzle.
  def seed
    for b in 0...B
      for r in 0...B
        for c in 0...B
          row = b * B + r
          col = b * B + c
          i = index( row, col )
          set( i, choices( i ).sample )
        end
      end
    end
    self
  end
  
  # Get sequence for random walk across the entire puzzle.
  def random_sequence
    ( 0...SIZE ).to_a.shuffle
  end
  
  # Randomly clear as many squares of the puzzle as possible without making it unsolvable.
  def reduce!
    for i in random_sequence
      set( i, 0 ) if choices( i ).empty?
    end
    for i in random_sequence
      n = get( i )
      next if n == 0
      delete( i, n )
      insert( i, n ) unless proper?
    end
    self
  end
  
  # Return new reduced puzzle as with reduce! while keeping self intact.
  def reduce
    dup.reduce!
  end
  
  # Create new puzzle from given string of digits.
  def self.load( s )
    new( s.to_s.scan( /\d/ ) )
  end
  
  # Generate brand new puzzle.
  def self.generate
    new.seed.solution.reduce!
  end
  
end

# Demonstrate the functionality if this file is run directly.

if $0 == __FILE__

  s = <<-EOT
  000070940
  070090005
  300005070
  087400100
  463000000
  000007080
  800700000
  700000028
  050268000
  EOT

  s = Sudoku.load( s )

  puts s
  puts
  puts s.solution
  puts

  s = <<-EOT.tr( '-', '0' )
  --------1
  -------23
  --4--5---
  ---1-----
  ----3-6--
  --7---58-
  ----67---
  -1---4---
  52-------
  EOT

  s = Sudoku.load( s )

  puts s
  puts
  puts s.solution
  puts

  s = Sudoku.generate

  puts s
  puts
  puts s.solution

end

# EOF #