class FifteenPuzzleSolver::Board

Attributes

height[R]
width[R]

Public Class Methods

new(blocks, width, height) click to toggle source
# File lib/fifteen_puzzle_solver/board.rb, line 6
def initialize(blocks, width, height)
  @blocks = blocks
  @width = width
  @height = height
end

Public Instance Methods

at_position(x, y) click to toggle source

Get element value at position

# File lib/fifteen_puzzle_solver/board.rb, line 18
def at_position(x, y)
  index = get_index(x, y)
  return nil if index < 0

  @blocks[index]
end
difference() click to toggle source

Return difference between blocks and valid system

# File lib/fifteen_puzzle_solver/board.rb, line 98
def difference
  difference = 0
  valid_system = [*1...(@width * @height)]
  @blocks.each_with_index do |block, index|
    next if block == 0
    difference += 1 unless block == valid_system[index]
  end
  difference
end
display() click to toggle source

Display board in output

# File lib/fifteen_puzzle_solver/board.rb, line 72
def display
  output = ""
  @width.times do |y|
    @height.times do |x|
      output << at_position(x, y).to_s.center(5)
    end
    output << "\n"
  end
  output
end
get_position(value) click to toggle source

Get element position with specified value

# File lib/fifteen_puzzle_solver/board.rb, line 26
def get_position(value)
  {
    x: @blocks.index(value) % @width,
    y: @blocks.index(value) / @height,
  }
end
invalid_blocks_distance() click to toggle source

Return invalid blocks distance

# File lib/fifteen_puzzle_solver/board.rb, line 84
def invalid_blocks_distance
  distance = 0

  iterator = 1
  @blocks.each do |block|
    if block != iterator && block != 0
      distance += distance(block)
    end
    iterator += 1
  end
  distance
end
move(direction) click to toggle source

Move zero-value element

# File lib/fifteen_puzzle_solver/board.rb, line 34
def move(direction)
  delta = direction_delta(direction)
  move_element(delta[:dx], delta[:dy])
end
neighbors(parent, order) click to toggle source

Return neighbors for board element

# File lib/fifteen_puzzle_solver/board.rb, line 53
def neighbors(parent, order)
  unless !!(/^[udlr]+$/is =~ order)
    raise Exception.new("Invalid order (only up, down, left or right)")
  end

  neighbors = []
  position = get_position(0)
  order.each_char do |direction|
    delta = direction_delta(direction)
    if can_move?(position[:x], position[:y], delta[:dx], delta[:dy])
      board = FifteenPuzzleSolver::Board.new(@blocks.dup, @width, @height)
      board.move(direction)
      neighbors << FifteenPuzzleSolver::Node.new(parent, board, direction)
    end
  end
  neighbors
end
state() click to toggle source

Get unique identifier

# File lib/fifteen_puzzle_solver/board.rb, line 13
def state
  @blocks.join
end
valid?() click to toggle source

Check if the board is valid

# File lib/fifteen_puzzle_solver/board.rb, line 40
def valid?
  return false unless @blocks.last == 0

  iterator = 1
  @blocks.each do |block|
    return false if block != iterator && block != 0

    iterator += 1
  end
  true
end

Private Instance Methods

can_move?(x, y, dx, dy) click to toggle source

Check range exceeding

# File lib/fifteen_puzzle_solver/board.rb, line 137
def can_move?(x, y, dx, dy)
  x + dx >= 0 && y + dy >= 0 && x + dx < @width && y + dy < @height
end
direction_delta(direction) click to toggle source

Translate direction to delta

# File lib/fifteen_puzzle_solver/board.rb, line 116
def direction_delta(direction)
  case direction
  when "u", "U", "up"
    return { dx: 0, dy: -1 }
  when "d", "D", "down"
    return { dx: 0, dy: 1 }
  when "l", "L", "left"
    return { dx: -1, dy: 0 }
  when "r", "R", "right"
    return { dx: 1, dy: 0 }
  else
    raise Exception.new("Invalid direction (only up, down, left or right)")
  end
end
distance(value) click to toggle source

Return distance between two blocks

# File lib/fifteen_puzzle_solver/board.rb, line 163
def distance(value)
  block1 = get_position(value)
  block2 = valid_position_for(value)
  (block1[:x] - block2[:x]).abs + (block1[:y] - block2[:y]).abs
end
get_index(x, y) click to toggle source

Get index by position

# File lib/fifteen_puzzle_solver/board.rb, line 132
def get_index(x, y)
  @height * y + x
end
move_element(dx, dy) click to toggle source

Move element by x and y difference

# File lib/fifteen_puzzle_solver/board.rb, line 142
def move_element(dx, dy)
  position = get_position(0)
  element_index = get_index(position[:x] + dx, position[:y] + dy)

  if element_index >= 0 && can_move?(position[:x], position[:y], dx, dy)
    zero_index = get_index(position[:x], position[:y])
    @blocks[zero_index], @blocks[element_index] = @blocks[element_index], @blocks[zero_index]
  end
end
update_state() click to toggle source

Update state

# File lib/fifteen_puzzle_solver/board.rb, line 111
def update_state
  @state = @blocks.join
end
valid_position_for(value) click to toggle source

Return valid position for value

# File lib/fifteen_puzzle_solver/board.rb, line 153
def valid_position_for(value)
  return { x: @width - 1, y: @height - 1 } if value == 0

  {
    x: (value - 1) % @width,
    y: (value - 1) / @height,
  }
end