def calc_number(puzzle)
  nums = puzzle.dup
  puzzle.each_with_index do |x, i_x|
    puzzle[i_x..-1].each_with_index do |y, i_y|
      nums[i_x + i_y] -= 1 if y > x
    end
  end

  number = 0
  nums.each_with_index do |x, i_x|
    factorial = (nums.size - 1 - i_x).downto(1).inject(:*)
    number += factorial * x if factorial != nil
  end
  return number
end

def find_zero(puzzle)
  return puzzle.index(0)
end

SWAP_CHOICE = [[1, 3],    [0, 2, 4],    [1, 5], 
               [0, 4, 6], [1, 3, 5, 7], [2, 4, 8],
               [3, 7],    [4, 6, 8],    [5, 7]]

GOAL_STATE = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# main
init_state = []
3.times do 
  init_state.concat(gets.chomp.split.map(&:to_i))
end

states = Array.new(9.downto(1).inject(:*), false)
states[calc_number(init_state)] = true
queue = [[init_state, 0]]

while queue.size > 0 do
  state = queue.shift
  break if state[0] == GOAL_STATE
  zero_position = find_zero(state[0])
  swap_positions = SWAP_CHOICE[zero_position]

  swap_positions.each do |swap_position|
    new_state = [state[0].dup, state[1]]
    new_state[0][zero_position], new_state[0][swap_position] = 
      new_state[0][swap_position], new_state[0][zero_position]
    new_number = calc_number(new_state[0])
    next if states[new_number] == true
    new_state[1] += 1
    queue << new_state
    states[new_number] = true
  end
end

p state[1]