{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\n\u003cp\u003e\n The goal of the 8 puzzle problem is to complete pieces on $3 \\times 3$ cells where one of the cells is empty space. \n\u003c/p\u003e\n\n\u003cp\u003e\n In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.\n\u003c/p\u003e\n\n\u003cpre\u003e1 3 0\n4 2 5\n7 8 6\n\u003c/pre\u003e\n\n\u003cp\u003e\n You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).\n\u003c/p\u003e\n\n\n\u003cpre\u003e1 2 3\n4 5 6\n7 8 0\n\u003c/pre\u003e\n\n\u003cp\u003e\n Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\n The $3 \\times 3$ integers denoting the pieces or space are given.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\n Print the fewest steps in a line.\n\u003c/p\u003e\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\n\u003cul\u003e\n\u003cli\u003eThere is a solution.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eSample Input \u003c/h2\u003e\n\u003cpre\u003e1 3 0\n4 2 5\n7 8 6\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Output\u003c/h2\u003e\n\u003cpre\u003e4\n\u003c/pre\u003e\n"}}]}