提示: 欢迎访问OurACM平台。
Problem 1662 Nine again

Accept: 45    Submit: 165
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei likes playing games. He has created a new game recently.
The game is derived from the very famous game “eight puzzle”. It has nine blocks in the 3 * 3 matrix (three rows and three columns). The intial state is shown above.
There are two kinds of movement for oaiei to change the state:
  • a right rotation shifts one position to the right bottom block circularly.
  • a left rotation shifts one position to the left botton block circularly.
Now your task is to write a program, given a state, if the given state is solvable, you should find a way to set it to the intial state using the minimum possible number of moves; if the puzzle is unsolvable, you should output “No solution”.

Input

There are multiple test cases. For each test, there are three lines that describe a puzzle state. Each line consists of three integers, separated by a space. The nine integers are 1-9 respectively.

Output

For each test, if the given state is solvable,you should output an integer N, indicating the minimum number of moves required to set the puzzle to its initial state, if the puzzle is unsolvable, you should output “No solution”.

Sample Input

3 1 6 7 8 9 4 5 2 1 4 3 2 5 6 7 8 9 5 6 3 2 9 4 7 8 1

Sample Output

No solution 1 3

Source

FOJ月赛-2008年10月

Submit  Back  Status  Discuss