A solver for the dominopeg wood puzzle

dominopeg_puzzle_solver.rb

#!/usr/bin/env ruby

# Solves [dominopeg puzzle](http://www.puzzlemist.com/dominopeg.html)

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]

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},
}

class Piece
  PIECE_WIDTH   = 2
  PIECE_HEIGHT  = 1
  CIRCLE_WIDTH  = 3
  CIRCLE_HEIGHT = 2

  attr_accessor :base_piece, :flip, :orientation

  def initialize(base_piece, flip, orientation)
    @base_piece = base_piece
    @flip = flip
    @orientation = orientation
  end

  def horizontal?
    orientation == 0 || orientation == 180
  end

  def piece_width
    horizontal? ? PIECE_WIDTH : PIECE_HEIGHT
  end

  def piece_height
    horizontal? ? PIECE_HEIGHT : PIECE_WIDTH
  end

  def circle_width
    horizontal? ? CIRCLE_WIDTH : CIRCLE_HEIGHT
  end

  def circle_height
    horizontal? ? CIRCLE_HEIGHT : CIRCLE_WIDTH
  end

  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

  def to_s
    base_width_transpose = _base_transpose

    piece_array = (0...circle_height).map do |y|
      (0...circle_width).map do |x|
        spot = y * circle_width + x
        base_width_transpose.include?(spot) ? base_piece[:id] : "U"
      end
    end

    piece_row = Array.new(circle_width, " ").join("+")
    piece_array.map { |row| row.join(" ") }.join("\n#{piece_row}\n") + "\n\n"
  end

  def _base_transpose
    transpose.map do |spot|
      spot % Board::WIDTH + spot / Board::WIDTH * circle_width
    end
  end
end

class Board
  WIDTH = 7
  HEIGHT = 5
  PIECE_WIDTH = 6
  PIECE_HEIGHT = 4

  attr_accessor :board, :piece_board

  def self.from_existing_board(board)
    new_board = Board.new
    new_board.board = board.board.dup
    new_board.piece_board = board.piece_board.dup
    new_board
  end

  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

  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 apply(piece)
    first_piece_spot = _first_empty_piece_spot
    _piece_positions(first_piece_spot, piece).each do |piece_position|
      piece_board[piece_position] = piece.base_piece[:id]
    end

    first_circle_spot = _piece_spot_to_circle_spot(first_piece_spot)
    _circle_positions(first_circle_spot, piece).each do |spot|
      board[spot] = piece.base_piece[:id]
    end
    @first_empty_piece_spot = nil
  end

  def _first_empty_piece_spot
    @first_empty_piece_spot ||= piece_board.index { |spot| !spot }
  end

  def _piece_spot_to_circle_spot(piece_spot)
    piece_spot + piece_spot / PIECE_WIDTH
  end

  def _piece_positions(first_piece_spot, piece)
    piece.piece_positions.map do |piece_spot|
      first_piece_spot + piece_spot
    end
  end

  def _circle_positions(first_circle_spot, piece)
    piece.transpose.map do |spot|
      first_circle_spot + spot
    end
  end

  def to_s
    circle_arrays = (0...HEIGHT).map do |y|
      (0...WIDTH).map do |x|
        spot = y * WIDTH + x
        board[spot] || " "
      end
    end

    piece_arrays = (0..PIECE_HEIGHT).map do |y|
      (0...PIECE_WIDTH).map do |x|
        spot = y * PIECE_WIDTH + x
        piece_board[spot] || " "
      end
    end

    full_array = circle_arrays.zip(piece_arrays).flatten(1).compact

    string = ""
    full_array.each_with_index do |row, index|
      if index.even?
        string << "#{row.join(" ")}"
      else
        string << " #{row.join(" ")} "
      end
      string << "\n"
    end

    string << "\n\n"
  end
end

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 main
  pieces = _init_pieces
  board = Board.new([0, 7, 14, 21, 28])
  solution = Solver.solve(board, pieces)
  puts solution
end

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

main if __FILE__ == $PROGRAM_NAME