sudoku.rb

require 'ostruct'

# http://en.wikipedia.org/wiki/Sudoku
wiki =
"53  7    
6  195   
 98    6 
8   6   3
4  8 3  1
7   2   6
 6    28 
   419  5
    8  79"

# http://www.websudoku.com/?level=2&set_id=3350218628
medium = 
" 4   7 3 
  85  1  
 15 3  9 
5   7 21 
  6   8  
 81 6   9
 2  4 57 
  7  29  
 5 7   8 "

# http://www.websudoku.com/?level=4&set_id=470872047
evil = 
"  53 694 
 3 1    6
       3 
7  9     
 1  3  2 
     2  7
 6       
8    7 5 
 436 81  "

raw = evil # swap to wiki or medium to try those

class Object
   def deep_copy
     Marshal.load( Marshal.dump( self ) )
   end
end

class Board < Array
  def blanks
    blanks = []
    each_with_index do |row, y|
      row.each_with_index do |cell, x|
        if cell.zero?
          blanks << [x, y]
        end
      end
    end
    blanks
  end

  def set(x, y, value)
    self[y][x] = value
  end
  
  def report
    map { |row| row.map { |c| c.zero? ? " " : c }.join(" ") }.join("\n") + "\n" + "FINISHED!!!"    
  end
end

# Would be nice to have coords in the BrainCell
class BrainCell < Array
  def narrow(x, y, board, grids)
    row = board[y]
    col = board.map { |r| r[x] }
    reject! { |n| row.include?(n) || col.include?(n) }

    grid = grids.get(x, y)
    reject! { |n| grid.last.include?(n) }    
  end
  
  def solved?
    size == 1    
  end
  
  def solved_value
    raise "Not solved: #{self.join(", ")}" unless solved?
    first
  end
end

class ConflictingSolverException < Exception; end

class Solvers < Array
  def check_for_conflicts(grids)
    each do |s1|
      grid1 = grids.get(s1.x, s1.y)

      each do |s2|
        next if s1.x == s2.x && s1.y == s2.y

        if s1.x == s2.x && s1.value == s2.value
          raise ConflictingSolverException
        end
        if s1.y == s2.y && s1.value == s2.value
          raise ConflictingSolverException
        end

        grid2 = grids.get(s2.x, s2.y)
        if grid1 == grid2 && s1.value == s2.value
          raise ConflictingSolverException
        end
      end
    end
  end
  
  def solve(board)
    each do |s|
      board.set(s.x, s.y, s.value)
    end    
  end
end

class EmptyBrainCellException < Exception; end

class Brain < Array
  def initialize
    9.times { |i| self[i] = (1..9).map { BrainCell.new([*1..9]) } }    
  end
  
  def narrow(blanks, board, grids)
    blanks.each do |x, y|
      brain_cell = self[y][x]
      brain_cell.narrow(x, y, board, grids)
      if brain_cell.empty?
        raise EmptyBrainCellException
      end      
    end
  end
  
  def solvers(blanks)
    solvers = Solvers.new
    blanks.each do |x, y|
      brain_cell = self[y][x]
      if brain_cell.solved?
        solvers << OpenStruct.new(:x => x, :y => y, :value => brain_cell.solved_value)
      end
    end
    solvers
  end
  
  def guess(board, blanks, options = { :concurrent => true })
    brain_cells = sorted_cells_with_coords_from(blanks)
    brain_cells.each do |brain_cell, coords|
      brain_cell.size.times do |i|
        board[coords.last][coords.first] = brain_cell[i]
        unless $done          
          if options[:concurrent]
            Thread.new do
              think(board, self)
            end
          else
            think(board, self)
          end
        end
      end
      board[coords.last][coords.first] = 0    
    end
    
  end
  
private
  
  def sorted_cells_with_coords_from(blanks)
    blanks.map { |x, y|
      [self[y][x], [x, y]] 
    }.sort_by { |brain_cell, coords|
      brain_cell.size
    }
  end
end

class Grids
  SETUP = [[0..2, 0..2, []],[3..5, 0..2, []], [6..8, 0..2, []], [0..2, 3..5, []],[3..5, 3..5, []], [6..8, 3..5, []], [0..2, 6..8, []],[3..5, 6..8, []], [6..8, 6..8, []]]

  def initialize(board)
    @grids = SETUP.deep_copy
    # Figure out which numbers are in which grids
    board.each_with_index do |row, y|
      row.each_with_index do |cell, x|
        @grids.each do |grid|
          if !cell.zero? && grid[0].include?(x) && grid[1].include?(y)
            grid.last << cell
          end
        end
      end
    end
  end
  
  def get(x, y)
    @grids.detect { |g| g[0].include?(x) && g[1].include?(y) }    
  end
end

# Main thinking method

def think(board, brain)
  board = board.deep_copy
  brain = brain.deep_copy
  grids = Grids.new(board)

  blanks = board.blanks
  if blanks.empty?
    $done = true
    puts board.report
    exit
  end

  begin
    brain.narrow(blanks, board, grids)
  rescue EmptyBrainCellException
    return
  end

  solvers = brain.solvers(blanks)
  
  if solvers.empty?    
    brain.guess(board, blanks)

  else
    begin
      solvers.check_for_conflicts(grids)
      solvers.solve(board)
    rescue ConflictingSolverException
      return
    end
  end
  
  think(board, brain)
end

# Kick it off!

board = Board.new(raw.map { |l| l.chomp.split(//).map { |s| s.to_i } })
fail("Bad board") unless board.size == 9 && board[4].size == 9

# Setup the brain
brain = Brain.new
fail("Bad brain: rows=#{brain.size}, cols=#{brain[7].size}") unless brain.size == 9 && brain[7].size == 9 && brain[3][1].size == 9

$done = false

think(board, brain)