Server Time: Tue Jul 23, 2019 12:32 am
 Welcome ( logout )
1139 - 8 Puzzle
 PDF (English) Statistics Forum
 Time Limit: 2 second(s) Memory Limit: 32 MB

An 8 Puzzle is played in a board of 3 by 3. Initially the board is scattered. Your goal is to make your board to the following board:

1 2 3

4 5 6

7 8 0

Here 0 denotes the blank. The moves are described in the following section:

1 2 3                1 2 3                1 2 0                1 0 2                1 6 2

4 0 6       ->     4 6 0       ->     4 6 3       ->     4 6 3    ->        4 0 3

7 8 5                7 8 5                7 8 5                7 8 5                7 8 5

Initial               right                   up                   left                 down

# Input

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a blank line. The next three lines will contain three integers each. You may assume that the given board is valid.

# Output

For each case, print the case number and the minimum number of moves required to reach the goal state. If it's impossible, then print 'impossible'.

# Output for Sample Input

3

1 2 3

4 5 6

8 7 0

1 2 3

4 5 6

7 0 8

1 3 2

4 6 5

7 8 0

Case 1: impossible

Case 2: 1

Case 3: 18

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan