219 . 8-puzzle
Description
The 8-puzzle is an old fashion game contrived by Sam Loyd in the 1870s. The board of the 8-puzzle is composed of 3x3 grids. There are 8 movable tiles on the board numbered from 1 to 8. The purpose of this game is to arrange the tiles on the board back to the initial state. The tiles can only move toward the space on the board.
Figure 1
For example (Figure 1), you can move tile #2 downward or tile #3 to the right. The terminating condition is as Figure 2. The numbers are ordered from left to right, up to down.
Figure 2
Bee's mom gave him an 8-puzzle, but Bee is stupid. Once he has randomized the board, he is not able to solve it. One day he brought his 8-puzzle to school, and one of his classmates said, "What an easy game, I can solve it within 20 steps!" Bee got angry and asked you to find the states which cannot be solved in 20 steps.
Input Format
There are multiple test cases in the input. The first line is an integer k, denoting the number of test cases. For each test cases there are 3 lines with 3 separated numbers, denoting the state of the 8-puzzle.
Output Format
For each test case, print the minimum steps needed if this configuration can be solved in 20 steps. Otherwise print "Hard".
Sample Input 1
2 1 2 3 4 5 6 8 7 0 1 2 3 4 5 6 7 0 8
Sample Output 1
Hard 1
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|