blog_post_snippets_01_dominopeg_puzzle_solver.md

def _init_pieces
  pieces = []
  BasePieces.each do |base_piece|
    Flips.each do |flip|
      Orientations.each do |orientation|
        pieces << Piece.new(base_piece, flip, orientation)
      end
    end
  end
  pieces.uniq { |piece| [piece.transpose, piece.horizontal?] }
end

BasePieces = [
  {id: "0", spots: [0, 1]},
  {id: "1", spots: [0, 2]},
  {id: "2", spots: [0, 7]},
  {id: "3", spots: [0, 8]},
  {id: "4", spots: [0, 9]},
  {id: "5", spots: [1, 8]},
  {id: "6", spots: [0, 1, 2]},
  {id: "7", spots: [0, 1, 7]},
  {id: "8", spots: [0, 1, 8]},
  {id: "9", spots: [0, 1, 9]},
  {id: "A", spots: [0, 2, 7]},
  {id: "B", spots: [0, 2, 8]},
]

Flips = [false, true]

Orientations = [0, 90, 180, 270]

def piece_positions
  horizontal? ? [0, 1] : [0, 6]
end

def transpose
  return @transpose if @transpose
  spots = base_piece[:spots]
  spots = spots.map { |spot| FlipMap[spot] } if flip
  @transpose = spots.map { |spot| OrientationMaps[orientation][spot] }.sort
end

FlipMap = {0=>7, 1=>8, 2=>9, 7=>0, 8=>1, 9=>2}

OrientationMaps = {
  0 => {0=>0, 1=>1, 2=>2, 7=>7, 8=>8, 9=>9},
  90 => {0=>1, 1=>8, 2=>15, 7=>0, 8=>7, 9=>14},
  180 => {0=>9, 1=>8, 2=>7, 7=>2, 8=>1, 9=>0},
  270 => {0=>14, 1=>7, 2=>0, 7=>15, 8=>8, 9=>1},
}

module Solver
  def self.solve(board, pieces)
    if pieces.any?
      pieces.each do |piece|
        if board.accepts?(piece)
          new_pieces = remove(pieces, piece)
          new_board = Board.from_existing_board(board)
          new_board.apply(piece)
          solution = solve(new_board, new_pieces)
          return solution if solution
        end
      end
    else
      return board
    end
    nil
  end

  def self.remove(pieces, piece_to_remove)
    pieces.reject do |piece|
      piece.base_piece[:id] == piece_to_remove.base_piece[:id]
    end
  end
end

def accepts?(piece)
  first_piece_spot = _first_empty_piece_spot
  piece_positions = _piece_positions(first_piece_spot, piece)

  if piece_positions[0] % PIECE_WIDTH + piece.piece_width > PIECE_WIDTH
    return false
  end

  piece_positions.each do |piece_position|
    return false if piece_position >= PIECE_WIDTH * PIECE_HEIGHT
    return false unless piece_board[piece_position].nil?
  end

  first_circle_spot = _piece_spot_to_circle_spot(first_piece_spot)
  _circle_positions(first_circle_spot, piece).each do |spot|
    return false unless board[spot].nil?
  end

  true
end

def main
  pieces = _init_pieces
  board = Board.new([0, 7, 14, 21, 28])
  solution = Solver.solve(board, pieces)
  puts solution
end

main if __FILE__ == $PROGRAM_NAME

 def initialize(constraints=nil)
    @board = Array.new(WIDTH*HEIGHT)
    @piece_board = Array.new(PIECE_WIDTH*PIECE_HEIGHT)
    constraints.each { |constraint| board[constraint] = "O" } if constraints
  end