optimized

sudoku.rb

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, include_self: true)
    rix = (ix / 9) * 9
    if include_self
      @data[rix...rix + 9]
    else
      ((rix ... rix + 9).to_a - [ix]).map { |i| @data[i] }
    end
  end

  # @return [Array] column of cells that contains the specified index
  def column_for(ix, include_self: true)
    cix = ix % 9
    ixs = ((cix .. 80) % 9)
    ixs = ixs.to_a - [ix] unless include_self
    ixs.map { |x| @data[x] }
  end

  # @return [Array] 3x3 box of cells that contains the specified index
  def box_for(ix, include_self: true)
    xix = (ix % 9) / 3
    yix = (ix / 9) / 3
    tl = 27 * yix + 3 * xix
    ixs = BOX_INDICES.map { |x| x + tl }
    ixs -= [ix] unless include_self

    ixs.map { |x| @data[x] }
  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] }
    when ix == 40
      ((0 .. 81) % 10).map { |ix| @data[ix] } +
      ((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
  ALL_POSSIBLLE= (1..9).map { |sh| 1 << sh }.inject(:|)
  private_constant :ALL_POSSIBLLE

  def initialize
    @bitmap = ALL_POSSIBLLE
  end

  # Union of possibilities
  # @return [Candidate] The union of the operands
  def self.union(*operands)
    bitmap = operands.map { |op| op.instance_variable_get(:@bitmap) }.inject(:|)
    new.tap { |obj| obj.instance_variable_set(:@bitmap, bitmap) }
  end

  # Difference between two possibilities
  # @return [Candidate] possibilities from +self+ with possibilities from
  #   +other+ removed
  def -(other)
    other = other.instance_variable_get(:@bitmap)
    bitmap = @bitmap & ~other
    self.class.new.tap { |obj| obj.instance_variable_set(:@bitmap, bitmap) }
  end

  # Iterates the possible numbers
  # @yield each possibilitiy
  # @yieldparam [Integer] ix the possiblity
  # @raise unless block given
  # @example
  #   p = Candidate.new
  #   p.remove_possibility(1)
  #   p.remove_possibility(5)
  #   p.remove_possibility(7)
  #   p.each { |x| puts x }
  #   # >> 2
  #   # >> 3
  #   # >> 4
  #   # >> 6
  #   # >> 8
  #   # >> 9
  def each
    (1..9).each { |ix| yield ix if possible?(ix) }
  end

  # The first integer that's possible
  # @return [Integer|nil] possibility
  def first
    (1..9).find(&method(:possible?))
  end

  # @return [Boolean] nothing is possible?
  def empty?
    @bitmap.zero?
  end

  # Removes the possibility
  # @param ix [Integer] possibility
  def remove_possibility(ix)
    @bitmap &= ~(1 << ix)
  end

  def heuristics
    (1..9).count(&method(:possible?))
  end

  def sole?
    ! @bitmap.zero? && (@bitmap & (@bitmap - 1)).zero?
  end

  def possible?(ix)
    ! (@bitmap & 1 << ix).zero?
  end

  def remove_all
    @bitmap = 0
  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].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|
      %i[row_for column_for box_for].each do |section|
        section = @data.public_send(section, ix, include_self: false)
        others = Candidate.union(* section.map(&:candidates))

        filtered = @data[ix].candidates - others

        unless filtered.empty?
          fill_item(filtered.first, ix)
          return true
        end
      end
    end

    false
  end
end

puzzle = [
  8,   nil, nil, nil, nil, nil, nil, nil, nil,
  nil, nil, 3,   6,   nil, nil, nil, nil, nil,
  nil, 7,   nil, nil, 9,   nil, 2,   nil, nil,
  nil, 5,   nil, nil, nil, 7,   nil, nil, nil,
  nil, nil, nil, nil, 4,   5,   7,   nil, nil,
  nil, nil, nil, 1,   nil, nil, nil, 3,   nil,
  nil, nil, 1,   nil, nil, nil, nil, 6,   8,
  nil, nil, 8,   5,   nil, nil, nil, 1,   nil,
  nil, 9,   nil, nil, nil, nil, 4,   nil, nil
]
puts Sudoku.new(puzzle).solve