A* search for 8 puzzles

eight_puzzle_solver.rb

# finds path to board solution
def a_star_search(board)
  tree = []
  leaves = []
  solution = [1, 2, 3, 4, 5, 6, 7, 8, 9]

  leaf = build_leaf(board, {board: nil, branch: []})

  i = 0
  while i < 10000 && leaf[:board] != solution
    i += 1
    tree << leaf[:board]
    new_buds = neighbor_boards(leaf[:board])
    new_buds.each do |bud|
      leaves << build_leaf(bud, leaf) unless tree.include? bud
    end
    leaf = pop_cheapest_leaf(leaves)

    p "iterations = #{i}"
    p "depth = #{leaf[:branch].length}"
    p "manhattan distance = #{leaf[:m_distance]}"
    p "board = #{leaf[:board]}"

    return leaf if leaf[:board] == solution
  end
end

# underestimates depth of solution using current board state
def manhattan_distance(board)
  manhattan_distance = 0
  board.each_with_index do |x, i|
    next if x == 9 # this skips the blank square.
    array_steps = ((i + 1) - x).abs
    puzzle_steps = (array_steps / 3) + (array_steps % 3)
    manhattan_distance += puzzle_steps
  end
  return manhattan_distance
end

# returns possible moves based on position on board
def legal_moves(index)
  legal_moves = []
  legal_moves << index - 1 if index % 3 != 0  #left
  legal_moves << index + 1 if index % 3 != 2  #right
  legal_moves << index + 3 if index + 3 < 9   #up
  legal_moves << index - 3 if index - 3 > -1  #down
  return legal_moves
end

# returns boards with possible moves made
def neighbor_boards(board)
  blank_tile_index = board.index(9)
  return legal_moves(blank_tile_index).map do |legal_move|
    ret_arr = board.clone
    ret_arr[blank_tile_index] = board[legal_move]
    ret_arr[legal_move] = 9
    ret_arr
  end
end

# creates node with board and distance estimates from last
def build_leaf(board, prev_board)
  template = {board: nil, branch: [], m_distance: nil}
  template[:board] = board
  template[:branch] += prev_board[:branch]
  template[:branch] << board
  template[:m_distance] = manhattan_distance(board) + prev_board[:branch].length
  return template
end

# returns node with shortest estimated path to solution
def pop_cheapest_leaf(leaves)
  cheapest_leaf = nil
  cheapest_index = nil
  leaves.each_with_index do |leaf, i|
    if cheapest_leaf.nil? || leaf[:m_distance] < cheapest_leaf[:m_distance]
      cheapest_leaf = leaf
      cheapest_index = i
    end
  end
  leaves.delete_at(cheapest_index)
  return cheapest_leaf
end