sudoku_solver.rb

class Sudoku
  def initialize(board_string)
    @original_string = board_string
    @guess_cache = []
    @board = []
    board_string.split('').each_slice(9) { |row| @board << row.map {
      |num| num.to_i } }
  end

  def solve!
    @board.each_with_index do |row_value, row_index|
      row_value.each_with_index do |cell_value, cell_index|
        if blank?(cell_value) && get_possibilities(row_index, cell_index).length == 1
          row_value[cell_index] = get_possibilities(row_index, cell_index).pop
          solve!
        end
      end
    end
    guess_coords = find_zeros
    until any_zeros? == false
      coord = guess_coords.pop
      @guess_cache = get_possibilities(coord[0], coord[1])
      guess(coord)
    end
  end

  def guess(coord)
    if @guess_cache.length > 0
      @board[coord[0]][coord[1]] = @guess_cache.pop
      solve!
    end
    return @board if any_zeros? == false
    if any_zeros?
      reset
    end
    return if @guess_cache.length == 0
    guess
  end

  def board
    @board.flatten.join('')
  end

  def to_s
    puts "______BOARD______"
    @board.each {|row| puts row.join(' ')}
  end

  def blank?(number)
    number.eql?(0) ? true : false
  end

  def get_horizontal(r_index)
    @board[r_index]
  end

  def get_vertical(c_index)
    @board.map { |row| row[c_index] }
  end

  def get_possibilities(r_index, c_index)
    valid_numbers = (1..9).to_a
    horizontal = valid_numbers - get_horizontal(r_index)
    vertical = valid_numbers - get_vertical(c_index)
    box = valid_numbers - get_box(r_index, c_index)
    horizontal & vertical & box
  end

  def find_zeros
    guess_coordinates = []
    @board.each_with_index do |row_value, row_index|
      row_value.each_with_index do |cell_value, cell_index|
        if cell_value == 0
          guess_coordinates << [row_index, cell_index]
        end
      end
    end
    guess_coordinates
  end

  def any_zeros?
    return true if self.find_zeros.length > 0
    return false if self.find_zeros.length == 0
  end

  def reset
    initialize(@original_string)
  end

  def get_box(r_index, c_index)
    box1 = [@board[0][0], @board[0][1], @board[0][2],
            @board[1][0], @board[1][1], @board[1][2],
            @board[2][0], @board[2][1], @board[2][2]]

    box2 = [@board[0][3], @board[0][4], @board[0][5],
            @board[1][3], @board[1][4], @board[1][5],
            @board[2][3], @board[2][4], @board[2][5]]

    box3 = [@board[0][6], @board[0][7], @board[0][8],
            @board[1][6], @board[1][7], @board[1][8],
            @board[2][6], @board[2][7], @board[2][8]]

    box4 = [@board[3][0], @board[3][1], @board[3][2],
            @board[4][0], @board[4][1], @board[4][2],
            @board[5][0], @board[5][1], @board[5][2]]

    box5 = [@board[3][3], @board[3][4], @board[3][5],
            @board[4][3], @board[4][4], @board[4][5],
            @board[5][3], @board[5][4], @board[5][5]]

    box6 = [@board[3][6], @board[3][7], @board[3][8],
            @board[4][6], @board[4][7], @board[4][8],
            @board[5][6], @board[5][7], @board[5][8]]

    box7 = [@board[6][0], @board[6][1], @board[6][2],
            @board[7][0], @board[7][1], @board[7][2],
            @board[8][0], @board[8][1], @board[8][2]]

    box8 = [@board[6][3], @board[6][4], @board[6][5],
            @board[7][3], @board[7][4], @board[7][5],
            @board[8][3], @board[8][4], @board[8][5]]

    box9 = [@board[6][6], @board[6][7], @board[6][8],
            @board[7][6], @board[7][7], @board[7][8],
            @board[8][6], @board[8][7], @board[8][8]]

    if (0..2).include?(r_index) && (0..2).include?(c_index)
      return box1
    elsif (0..2).include?(r_index) && (3..5).include?(c_index)
      return box2
    elsif (0..2).include?(r_index) && (6..8).include?(c_index)
      return box3
    elsif (3..5).include?(r_index) && (0..2).include?(c_index)
      return box4
    elsif (3..5).include?(r_index) && (3..5).include?(c_index)
      return box5
    elsif (3..5).include?(r_index) && (6..8).include?(c_index)
      return box6
    elsif (6..8).include?(r_index) && (0..2).include?(c_index)
      return box7
    elsif (6..8).include?(r_index) && (3..5).include?(c_index)
      return box8
    elsif (6..8).include?(r_index) && (6..8).include?(c_index)
      return box9
    else
      return nil
    end
  end

end

# Test boards, increasing in difficulty, uncomment one game at a time to test:

# game = Sudoku.new('619030040270061008000047621486302079000014580031009060005720806320106057160400030')
# game = Sudoku.new('310609005500730000000000900000940000000000109000057060008500006000000003019082040')
# game = Sudoku.new('096040001100060004504810390007950043030080000405023018010630059059070830003590007')
# game = Sudoku.new('105802000090076405200400819019007306762083090000061050007600030430020501600308900')
# game = Sudoku.new('005030081902850060600004050007402830349760005008300490150087002090000600026049503')
# game = Sudoku.new('096040001100060004504810390007950043030080000405023018010630059059070830003590007')
# game = Sudoku.new('105802000090076405200400819019007306762083090000061050007600030430020501600308900')
# game = Sudoku.new('005030081902850060600004050007402830349760005008300490150087002090000600026049503')
# game = Sudoku.new('290500007700000400004738012902003064800050070500067200309004005000080700087005109')
# game = Sudoku.new('080020000040500320020309046600090004000640501134050700360004002407230600000700450')
# game = Sudoku.new('608730000200000460000064820080005701900618004031000080860200039050000100100456200')
# game = Sudoku.new('370000001000700005408061090000010000050090460086002030000000000694005203800149500')
# game = Sudoku.new('000689100800000029150000008403000050200005000090240801084700910500000060060410000')
# game = Sudoku.new('030500804504200010008009000790806103000005400050000007800000702000704600610300500')
# game = Sudoku.new('000075400000000008080190000300001060000000034000068170204000603900000020530200000')
# game = Sudoku.new('300000000050703008000028070700000043000000000003904105400300800100040000968000200')
# game = Sudoku.new('302609005500730000000000900000940000000000109000057060008500006000000003019082040')

p "#{game.find_zeros.length} zeros"
game.to_s
game.solve!
game.to_s