# frozen_string_literal: true
require 'set'

checked_puzzles = Set.new
current_puzzles = Set.new

input_puzzle = 3.times.map{gets.split.map(&:to_i)}.flatten
current_puzzles.add(input_puzzle)
count = 0

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

loop do
  next_puzzles = Set.new
  current_puzzles.each do |puzzle|
    if puzzle == goal_puzzle
      puts count
      exit
    end

    zero_point = puzzle.index(0)
    y, x = zero_point.divmod(3)
    if x != 2
      tmp_puzzle = puzzle.dup
      tmp_puzzle[zero_point] = puzzle[zero_point + 1]
      tmp_puzzle[zero_point + 1] = 0
      next_puzzles.add(tmp_puzzle)
    end
    if x != 0
      tmp_puzzle = puzzle.dup
      tmp_puzzle[zero_point] = puzzle[zero_point - 1]
      tmp_puzzle[zero_point - 1] = 0
      next_puzzles.add(tmp_puzzle)
    end
    if y != 2
      tmp_puzzle = puzzle.dup
      tmp_puzzle[zero_point] = puzzle[zero_point + 3]
      tmp_puzzle[zero_point + 3] = 0
      next_puzzles.add(tmp_puzzle)
    end
    if y != 0
      tmp_puzzle = puzzle.dup
      tmp_puzzle[zero_point] = puzzle[zero_point - 3]
      tmp_puzzle[zero_point - 3] = 0
      next_puzzles.add(tmp_puzzle)
    end
  end
  checked_puzzles.merge(current_puzzles)
  current_puzzles = next_puzzles - checked_puzzles
  count += 1
end