sudoku.rb

require 'set'
require 'forwardable'

# Board is a 9x9 standard sudoku board. This class does not care about what is
# stored in each cell of the board, it merely provides indexing and enumeration
# methods including accessing rows, columns, or 3x3 sudoku boxes.
class Board
  extend Forwardable

  # @param data [Array] flat array of 81 initial cell values
  def initialize(data)
    @data = data
  end

  def_delegator :@data, :[]
  def_delegator :@data, :[]=
  def_delegator :@data, :any?
  def_delegator :@data, :all?

  BOX_INDICES = [0, 1, 2, 9, 10, 11, 18, 19, 20].freeze
  private_constant :BOX_INDICES

  # @yield [row] the rows of the board
  # @return [Enumerator] enumerator if block is not given
  def rows(&block)
    return to_enum __method__ unless block_given?

    @data.each_slice(9, &block)
  end

  # Assuming that board cells respond to blank? and heuristics it yields blank
  # cells and their indices in increasing order of their heuristics.
  #
  # @yieldparam [Cell] cell
  # @yieldparam [Integer] index
  def heuristical_each(&block)
    @data
      .each_with_index
      .select { |e, _| e.blank? }
      .sort_by { |e, _| e.heuristics }
      .each(&block)
  end

  # Assuming that board cells respond to filled? it yields all filled cells and
  # their indices.
  #
  # @yieldparam [Cell] cell
  # @yieldparam [Integer] index
  # @return [Enumerator] enumerator unless block_given?
  def each_non_empty(&block)
    return to_enum __method__ unless block_given?

    @data.each_with_index.select { |e, _| e.filled? }.each(&block)
  end

  # Assuming that board cells respond to blank? it yields all blank cells and
  # their indices.
  #
  # @yieldparam [Cell] cell
  # @yieldparam [Integer] index
  # @return [Enumerator] enumerator unless block_given?
  def each_empty(&block)
    return to_enum __method__ unless block_given?

    @data.each_with_index.select { |e, _| e.blank? }.each(&block)
  end

  # @return [Array] row of cells that contains the specified index
  def row_for(ix)
    rix = (ix / 9) * 9
    @data[rix...rix + 9]
  end

  # @return [Array] column of cells that contains the specified index
  def column_for(ix)
    cix = ix % 9
    cix.step(by: 9, to: 80).map { |x| @data[x] }
  end

  # @return [Array] 3x3 box of cells that contains the specified index
  def box_for(ix)
    xix = (ix % 9) / 3
    yix = (ix / 9) / 3
    tl = 27 * yix + 3 * xix

    BOX_INDICES.map { |x| @data[x + tl] }
  end

  def diag_for(ix)
    case
    when ix % 10 == 0
      ((0 .. 81) % 10).map { |ix| @data[ix] }
    when ix % 8 == 0 && 0 < ix && ix < 79
      ((8 .. 79) % 8).map { |ix| @data[ix] }
    end
  end

  # deep copy of the board, calling dup on each cell.
  def dup
    self.class.new(@data.map(&:dup))
  end
end

# A class that can track multiple possibilities of numbers from 1 to 9.
class Candidate
  extend Forwardable

  def initialize
    @possibilities = Set.new(1..9)
  end

  def_delegator :@possibilities, :each
  def_delegator :@possibilities, :first
  def_delegator :@possibilities, :empty?
  def_delegator :@possibilities, :delete, :remove_possibility
  def_delegator :@possibilities, :count, :heuristics
  def_delegator :@possibilities, :one?, :sole?
  def_delegator :@possibilities, :include?, :possible?

  # Removes all possibilities
  def remove_all
    @possibilities.subtract(@possibilities)
  end

  # @see Object#dup
  def dup
    other = self.class.new
    other.instance_variable_set(:@possibilities, @possibilities.dup)
    other
  end
end

# A cell of the sudoku board contains a {Candidate} to track what's possible in
# the cell, and an item that can be nil to track the number in the cell.
class Cell
  extend Forwardable

  def initialize(elem = nil)
    @candidates = Candidate.new
    self << elem
  end

  def_delegator :@candidates, :heuristics
  def_delegator :@candidates, :possible?
  attr_reader :elem
  attr_reader :candidates

  # writes elem in the cell and removes all possibilities if the elem is non-nil
  #
  # @param elem [Integer] the elem to write
  def <<(elem)
    @elem = elem
    @candidates.remove_all unless elem.nil?
  end

  # @return [Bool] is the contained elem nil?
  def blank?
    @elem.nil?
  end

  # @return [Bool] is the contained elem non-nil?
  def filled?
    ! @elem.nil?
  end

  # @return [Bool] cell is blank, but there are no candidates
  def contradictory?
    @elem.nil? && @candidates.empty?
  end

  # @return [String] useful to print boards
  def to_s
    @elem.nil? ? '_' : @elem.to_s
  end

  # {Object#dup} with deep copy of the candidates in a new cell
  def dup
    other = Cell.new(elem)
    other.instance_variable_set(:@candidates, @candidates.dup)
    other
  end
end

# Iterative deepening functionality
#
# If you have a recursive search algorithm, this module can transform that
# algorithm to use iterative deepening if certain conditions are met.
#
# {IterativeDeepening::guard_by_depth} transforms a depth first search into a
# search that limits its maximum depth.
#
# {IterativeDeepening::iteratively_deepen} transforms a method that starts a
# depth first search so that the search is tried with increasing maximum depth
# allowed. The deepening process continues until the search is successful.
# Any recursive calls to the method during the search should prepend a false to
# the list of arguments.
#
# The search should respond with nil in case of failing to find a satisfying
# result, otherwise the search should return the result object.
#
# This module defines 2 class methods that can be called from the including
# class on the search method that needs to be transformed.
module IterativeDeepening
  # class methods
  module ClassMethods
    # transforms a depth first search into a search that limits its maximum
    # depth
    def guard_by_depth(method)
      mod = Module.new do
        define_method(method) do |*args, &block|
          return if @probe_depth >= @depth_limit

          @probe_depth += 1
          result = super(*args, &block)
          @probe_depth -= 1
          result
        end
      end

      prepend(mod)
    end

    # transforms a method that starts a depth first search so that the search
    # is tried with increasing maximum depth allowed. The deepening process
    # continues until the search is successful.
    #
    # Any recursive calls to the method during the search should prepend a
    # true to the list of arguments.
    def iteratively_deepen(method)
      mod = Module.new do
        define_method(method) do |recurse = false, *args, &block|
          reset_depth unless recurse

          loop do
            result = super(*args, &block)
            return result if ! result.nil? || recurse

            report "limit : #@depth_limit"
            @depth_limit += 1
          end
        end
      end

      prepend(mod)
    end
  end

  # puts a string with the indentation of the current depth of search
  def report(*args)
    puts ' ' * (3 * @probe_depth) << args.join
  end

  private

  def self.included(klass)
    klass.extend(ClassMethods)
  end

  def reset_depth
    @probe_depth = 0
    @depth_limit = 1
  end
end

# Sudoku solver
class Sudoku
  include IterativeDeepening

  # @param data [Array] flat array of numbers
  def initialize(data)
    @data = Board.new(data.map { |e| Cell.new(e) })
    update_candidates
  end

  # tries to fill everything that can be filled by looking at the currently
  # known constraints, and if the board is still not complete it calls probe to
  # guess a cell.

  # @return [Sudoku] solved puzzle
  def solve
    fill_obvious
    if reject?
      report 'return early from solve'
      return
    end
    return self if accept?

    probe
  end

  iteratively_deepen :solve

  # for printing the puzzle
  def to_s
    @data.rows.map { |row| row.join(' ') }.join("\n")
  end

  private

  def update_candidates
    @data.each_non_empty do |cell, ix|
      update_candidates_for(ix, with: cell.elem)
    end
  end

  def update_candidates_for(ix, with:)
    %i[row_for column_for box_for diag_for].each do |section|
      @data.public_send(section, ix)&.each do |cell|
        cell.candidates.remove_possibility(with)
      end
    end
  end

  # probe tries to fill empty cells in the order of their heuristics, calling
  # solve after inserting each new number. If the solution fails it has to
  # restore the state to the original from before inserting the candidate
  # number

  def probe
    @data.heuristical_each do |cell, ix|
      candidates = cell.candidates.dup
      candidates.each do |candidate|
        try_candidate(candidate, ix) do
          report "probing candidate #{candidate} at ix #{ix}"
          solve(true)
          return self if accept?

          report "failed (ix: #{ix})"
        end
      end
    end

    nil
  end

  guard_by_depth :probe

  def try_candidate(candidate, ix)
    @data = @data.dup.tap do
      fill_item(candidate, ix)
      yield
    end
  end

  def accept?
    @data.all?(&:filled?)
  end

  def reject?
    @data.any?(&:contradictory?)
  end

  def fill_item(elem, ix)
    @data[ix] << elem
    update_candidates_for(ix, with: elem)
  end

  def fill_obvious
    loop do
      next if fill_single_candidate
      next if fill_only_possible

      return
    end
  end

  def fill_single_candidate
    @data.each_empty do |cell, ix|
      if cell.candidates.sole?
        fill_item(cell.candidates.first, ix)
        return true
      end
    end
    false
  end

  def fill_only_possible
    @data.each_empty do |cell, ix|
      cell.candidates.each do |candidate|
        hit = %i[row_for column_for box_for diag_for].any? do |section|
          section = @data.public_send(section, ix)
          section && section.count do |sub_cell|
            sub_cell.possible? candidate
          end == 1
        end

        if hit
          fill_item(candidate, ix)
          return true
        end
      end
    end

    false
  end
end