sudoku.rb

require 'set'

class Board
  attr_accessor :rows, :columns, :grids, :puzzle, :completed_set

  COL_LOOKUP = {a: 0, b: 1, c: 2, d:3, e: 4, f:5, g:6, h:7, i:8 }
  GRID_LOOKUP = {
    [:a,1] => 1,
    [:a,2] => 1,
    [:a,3] => 1,
    [:b,1] => 1,
    [:b,2] => 1,
    [:b,3] => 1,
    [:c,1] => 1,
    [:c,2] => 1,
    [:c,3] => 1,
    
    [:d,1] => 2,
    [:d,2] => 2,
    [:d,3] => 2,
    [:e,1] => 2,
    [:e,2] => 2,
    [:e,3] => 2,
    [:f,1] => 2,
    [:f,2] => 2,
    [:f,3] => 2,

    [:g,1] => 3,
    [:g,2] => 3,
    [:g,3] => 3,
    [:h,1] => 3,
    [:h,2] => 3,
    [:h,3] => 3,
    [:i,1] => 3,
    [:i,2] => 3,
    [:i,3] => 3,

    [:a,4] => 4,
    [:a,5] => 4,
    [:a,6] => 4,
    [:b,4] => 4,
    [:b,5] => 4,
    [:b,6] => 4,
    [:c,4] => 4,
    [:c,5] => 4,
    [:c,6] => 4,
    
    [:d,4] => 5,
    [:d,5] => 5,
    [:d,6] => 5,
    [:e,4] => 5,
    [:e,5] => 5,
    [:e,6] => 5,
    [:f,4] => 5,
    [:f,5] => 5,
    [:f,6] => 5,

    [:g,4] => 6,
    [:g,5] => 6,
    [:g,6] => 6,
    [:h,4] => 6,
    [:h,5] => 6,
    [:h,6] => 6,
    [:i,4] => 6,
    [:i,5] => 6,
    [:i,6] => 6,

    [:a,7] => 7,
    [:a,8] => 7,
    [:a,9] => 7,
    [:b,7] => 7,
    [:b,8] => 7,
    [:b,9] => 7,
    [:c,7] => 7,
    [:c,8] => 7,
    [:c,9] => 7,
    
    [:d,7] => 8,
    [:d,8] => 8,
    [:d,9] => 8,
    [:e,7] => 8,
    [:e,8] => 8,
    [:e,9] => 8,
    [:f,7] => 8,
    [:f,8] => 8,
    [:f,9] => 8,

    [:g,7] => 9,
    [:g,8] => 9,
    [:g,9] => 9,
    [:h,7] => 9,
    [:h,8] => 9,
    [:h,9] => 9,
    [:i,7] => 9,
    [:i,8] => 9,
    [:i,9] => 9,
  }

  def initialize(init_state = nil)
    @puzzle        = init_state.nil? ? gen_empty_puzzle : init_state
    @rows          = init_rows
    @columns       = init_cols
    @grids         = init_grids
    @completed_set = (1..9).to_set
  end

  def insert_cell(col, row, value)
  return if invalid?(col, row, value)
  rows[row].add(value)
  columns[col].add(value)
  puzzle[COL_LOOKUP[col]][row - 1] = value if puzzle[COL_LOOKUP[col]][row - 1] == 0
  end

  def read_cell(col, row)
  cell = puzzle[COL_LOOKUP[col]][row - 1]
    if cell.nil? || cell.zero?
      'X'
    else
      cell
    end
  end

  def values_in_row(row)
    rows[row]
  end

  def values_in_column(col)
    columns[col]
  end

  def values_in_grid(col, row)
    grids[GRID_LOOKUP[[col, row]]]
  end

  def valid_values_for_cell(col, row)
    (completed_set - (values_in_row(row) + values_in_column(col) + values_in_grid(col, row))).to_a
  end

  def display_puzzle
    puts """    
                COLUMNS A-I
  
                A   B   C   D   E   F   G   H   I

      ROW 1   | #{ read_cell(:a, 1)} | #{read_cell(:b, 1)} | #{ read_cell(:c, 1)} | #{read_cell(:d, 1)} | #{ read_cell(:e, 1)} | #{read_cell(:f, 1)} | #{ read_cell(:g, 1)} | #{read_cell(:h, 1)} | #{ read_cell(:i, 1)} 
              -----------------------------------
      ROW 2   | #{ read_cell(:a, 2)} | #{read_cell(:b, 2)} | #{ read_cell(:c, 2)} | #{read_cell(:d, 2)} | #{ read_cell(:e, 2)} | #{read_cell(:f, 2)} | #{ read_cell(:g, 2)} | #{read_cell(:h, 2)} | #{ read_cell(:i, 2)} 
              -----------------------------------
      ROW 3   | #{ read_cell(:a, 3)} | #{read_cell(:b, 3)} | #{ read_cell(:c, 3)} | #{read_cell(:d, 3)} | #{ read_cell(:e, 3)} | #{read_cell(:f, 3)} | #{ read_cell(:g, 3)} | #{read_cell(:h, 3)} | #{ read_cell(:i, 3)} 
              -----------------------------------
      ROW 4   | #{ read_cell(:a, 4)} | #{read_cell(:b, 4)} | #{ read_cell(:c, 4)} | #{read_cell(:d, 4)} | #{ read_cell(:e, 4)} | #{read_cell(:f, 4)} | #{ read_cell(:g, 4)} | #{read_cell(:h, 4)} | #{ read_cell(:i, 4)}   
              -----------------------------------
      ROW 5   | #{ read_cell(:a, 5)} | #{read_cell(:b, 5)} | #{ read_cell(:c, 5)} | #{read_cell(:d, 5)} | #{ read_cell(:e, 5)} | #{read_cell(:f, 5)} | #{ read_cell(:g, 5)} | #{read_cell(:h, 5)} | #{ read_cell(:i, 5)} 
              -----------------------------------
      ROW 6   | #{ read_cell(:a, 6)} | #{read_cell(:b, 6)} | #{ read_cell(:c, 6)} | #{read_cell(:d, 6)} | #{ read_cell(:e, 6)} | #{read_cell(:f, 6)} | #{ read_cell(:g, 6)} | #{read_cell(:h, 6)} | #{ read_cell(:i, 6)} 
              -----------------------------------
      ROW 7   | #{ read_cell(:a, 7)} | #{read_cell(:b, 7)} | #{ read_cell(:c, 7)} | #{read_cell(:d, 7)} | #{ read_cell(:e, 7)} | #{read_cell(:f, 7)} | #{ read_cell(:g, 7)} | #{read_cell(:h, 7)} | #{ read_cell(:i, 7)} 
              -----------------------------------
      ROW 8   | #{ read_cell(:a, 8)} | #{read_cell(:b, 8)} | #{ read_cell(:c, 8)} | #{read_cell(:d, 8)} | #{ read_cell(:e, 8)} | #{read_cell(:f, 8)} | #{ read_cell(:g, 8)} | #{read_cell(:h, 8)} | #{ read_cell(:i, 8)} 
              -----------------------------------
      ROW 9   | #{ read_cell(:a, 9)} | #{read_cell(:b, 9)} | #{ read_cell(:c, 9)} | #{read_cell(:d, 9)} | #{ read_cell(:e, 9)} | #{read_cell(:f, 9)} | #{ read_cell(:g, 9)} | #{read_cell(:h, 9)} | #{ read_cell(:i, 9)} 
      """
  end

  private

  def init_rows
    {
      1 => Set.new(puzzle.map{ |column|  column[0] }),
      2 => Set.new(puzzle.map{ |column|  column[1] }),
      3 => Set.new(puzzle.map{ |column|  column[2] }),
      4 => Set.new(puzzle.map{ |column|  column[3] }),
      5 => Set.new(puzzle.map{ |column|  column[4] }),
      6 => Set.new(puzzle.map{ |column|  column[5] }),
      7 => Set.new(puzzle.map{ |column|  column[6] }),
      8 => Set.new(puzzle.map{ |column|  column[7] }),
      9 => Set.new(puzzle.map{ |column|  column[8] }),
    }
  end

  def init_cols
    {
      a: Set.new(puzzle[0]),
      b: Set.new(puzzle[1]),
      c: Set.new(puzzle[2]),
      d: Set.new(puzzle[3]),
      e: Set.new(puzzle[4]),
      f: Set.new(puzzle[5]),
      g: Set.new(puzzle[6]),
      h: Set.new(puzzle[7]),
      i: Set.new(puzzle[8]),
    }
  end

  def init_grids
    {
      1 => Set.new([puzzle[0][0..2],[puzzle[1][0..2]],[puzzle[2][0..2]]].flatten),
      2 => Set.new([puzzle[3][0..2],[puzzle[4][0..2]],[puzzle[5][0..2]]].flatten),
      3 => Set.new([puzzle[6][0..2],[puzzle[7][0..2]],[puzzle[8][0..2]]].flatten),
      4 => Set.new([puzzle[0][3..5],[puzzle[1][3..5]],[puzzle[2][3..5]]].flatten),
      5 => Set.new([puzzle[3][3..5],[puzzle[4][3..5]],[puzzle[5][3..5]]].flatten),
      6 => Set.new([puzzle[6][3..5],[puzzle[7][3..5]],[puzzle[8][3..5]]].flatten),
      7 => Set.new([puzzle[0][6..8],[puzzle[1][6..8]],[puzzle[2][6..8]]].flatten),
      8 => Set.new([puzzle[3][6..8],[puzzle[4][6..8]],[puzzle[5][6..8]]].flatten),
      9 => Set.new([puzzle[6][6..8],[puzzle[7][6..8]],[puzzle[8][6..8]]].flatten),
    }
  end
  
  def gen_empty_puzzle
    (1..9).to_a.map{|int| (1..9).to_a.map{|int2| nil}}
  end

  def invalid?(col, row, value)    
    [
      rows[row].member?(value), 
      columns[col].member?(value), 
      grids[GRID_LOOKUP[[col, row]]].member?(value)
    ].include?(true)
  end

end

class Solver
  
  attr_accessor :board
    
   ROW_CHOICES = (1..9).to_a
   COL_CHOICES = (:a..:i).to_a
  
  def initialize(board)
    @board = board
  end

  def availible_numbers(col, row)
    board.valid_values_for_cell(col, row)
  end

  def solve!
    81.times do 
      ROW_CHOICES.each do |row|
        COL_CHOICES.each do |col|
          board.insert_cell(col, row, availible_numbers(col, row).sample)
        end
      end
    end
  end

end


SEED1 = [ 
          [6, 8, 5, 0, 0, 0, 0, 0, 0],
          [3, 1, 9, 0, 0, 0, 0, 0, 0],
          [7, 2, 4, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 2, 1, 8, 0, 0, 0],
          [0, 0, 0, 4, 5, 6, 0, 0, 0],
          [0, 0, 0, 9, 7, 3, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 2, 1, 8],
          [0, 0, 0, 0, 0, 0, 4, 5, 6],
          [0, 0, 0, 0, 0, 0, 9, 7, 3]
        ]

SEED2 = [
          [3, 0, 0, 9, 0, 0, 0, 8, 0],
          [0, 7, 4, 0, 3, 0, 0, 0, 0],
          [0, 8, 0, 0, 6, 5, 1, 0, 0],
          [0, 4, 0, 3, 1, 0, 0, 0, 0],
          [0, 0, 0, 4, 9, 7, 0, 0, 0],
          [7, 0, 9, 2, 0, 0, 0, 0, 3],
          [4, 5, 7, 6, 2, 9, 0, 0, 8],
          [6, 0, 0, 0, 8, 3, 0, 0, 0],
          [0, 0, 0, 1, 0, 0, 0, 0, 6],
        ]

SEED3 = [
          [6, 0, 0, 0, 3, 0, 0, 0, 8],
          [0, 8, 4, 0, 0, 7, 2, 0, 9],
          [0, 0, 2, 5, 0, 0, 0, 0, 7],
          [0, 0, 6, 0, 0, 0, 5, 0, 0],
          [0, 0, 0, 0, 4, 1, 0, 8, 0],
          [0, 0, 1, 0, 7, 0, 0, 0, 6],
          [0, 0, 0, 0, 1, 6, 0, 0, 3],
          [0, 0, 0, 0, 5, 0, 0, 4, 1],
          [0, 6, 3, 4, 0, 2, 8, 0, 0],
        ]

b = Board.new(SEED3)
s = Solver.new(b)
s.board.display_puzzle
s.solve!
s.board.display_puzzle