Sudoku solver

board.rb

class Board < Array
  
  def initialize(board_string)
    super
  end

  def boxes
    triplets = self.flatten.each_slice(3).to_a
    temp = triplets.each_slice(3).to_a
    almost_there = temp.transpose
    some_more_slicing = almost_there.flatten.each_slice(9).to_a

    some_more_slicing.each_slice(3).to_a
  end

  def peers(indices)
    all_values = []
    if self[indices.row][indices.column] == 0
      all_values << self[indices.row]
      columns = self.transpose
      all_values << columns[indices.column]
      all_values << boxes[indices.column/3][indices.row/3]
    else
      return all_values
    end
    all_values.flatten!
    all_values.reject! do |num|
      num == 0
    end

  end

end

solver.rb

require_relative 'board.rb'
require 'pry'
require 'benchmark'
require_relative 'utils.rb'




class Impossible < StandardError
end

class Sudoku
  include SudokuUtils
  
  def initialize(board_string)
    @grid = Board.new(string_to_array(board_string))
    @rollbacks = 0
    
    raise ArgumentError unless board_string.length == 81
  end


  def solve!(grid = @grid)
    show(grid)
    return grid if solved?(grid)
    grid = copy(grid)
    
    # Iterate over all possible values and start solving starting with
    # the easiest cells (see how all_possible_values works)
    
    all_possible_values(grid).each do |indices, values|

        # If only one possible value for the cell, put it in there
        
        grid[indices.row][indices.column] = values[0] if values.length == 1
 
        # If we've reached a dead end, throw an error up the stack
        
        raise Impossible if values.empty?
        
        # If more than one possible value for the cell, start guessing.
        # This method also catches the errors from dead ends and rescues
        # them by trying a new value.
        
        values.each do |value|
          grid[indices.row][indices.column] = value
          begin
            return solve!(grid)
          rescue Impossible
            @rollbacks += 1
            next
          end
        end
 
        # If the guessing didn't lead to a solution, one of the earlier guesses
        # must've been wrong. This unwinds the stack further up.

        raise Impossible
    end
  end


end
 

board_string ="302609005300730000000000900000940000000000109000057060008500006000000003019082040"
game = Sudoku.new(board_string)
game.solve!



# p game.grid

utils.rb

BOARD = <<-STRING.chomp
     0   1   2   3   4   5   6   7   8  
   +-----------------------------------+
 0 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 1 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 2 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|     
 3 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 4 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 5 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 6 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 7 | * | * | * | * | * | * | * | * | * |
   |---|---|---|---|---|---|---|---|---|
 8 | * | * | * | * | * | * | * | * | * |
   +-----------------------------------+

STRING



module SudokuUtils

  # returns a Hash containing all possible values for each empty cell on the board
  # in order. The first value in this hash will always be the indices and possible
  # values of the cell which has the least possible values to choose from.
  # eg {[1,2] => [3,6,8] .......}
  
  def all_possible_values(grid)
    all_possible_values = {}

    grid.each_with_index do | row, row_index|
        row.each_with_index do |cell, col_index|
          next unless cell == 0
          cell_possible_values = []
           1.upto(9) do |num|
             unless grid.peers(row_index, col_index).include?(num)
               cell_possible_values << num
             end
            end
          all_possible_values[Indices.new(row_index, col_index)] = cell_possible_values
        end
    end
    Hash[all_possible_values.sort_by {|key, value| value.count}]
  end



  def string_to_array(board_string)
    board_string.split(//).map {|n| n.to_i}.each_slice(9).to_a
  end



  def show(grid)
    puts "\e[H\e[2J"
    temp_board = BOARD.dup
    grid.flatten.each do |num|
      temp_board.sub!('*', num.to_s)
    end
    puts temp_board
    puts "Rollbacks: #{@rollbacks}"
  end

  
  def copy(grid)
    copy = []
    grid.each do |row|
      row.each do |cell|
        copy << cell
      end
    end
  Board.new(copy.each_slice(9).to_a)
  end
  


  def solved?(grid)
    !grid.flatten.include?(0)
  end
end

class Indices < Struct.new(:row, :column)
end