Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently.
The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:
1 2 3
4 5 6
7 8 9
At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.
Help Johnny to find the shortest number of steps needed to reach the goal state.
Input
The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle which Johnny would like to solve.
The input data for successive test cases is separated by a blank line.
Output
For each test case print a single line containing the shortest number of steps needed to solve the corresponding puzzle. If there is no way to reach the final state, print the number -1.
Example
First thing to notice is, that board is allways 3x3 so you’ve got only 9! = 362880 possibilities, how can board look like. And that’s quite small number.
So you can construct graph. Each vertex represent one different board configuration. The edge between two vertex means, that you can go from first state of board to the second state with one step - so you switch two numbers with sum equal to prime number (there are only few prime numbers smaller than 17 so you can hard-wired it to your solution).
When you crate this graph it’s only some search in it. The best option is Breath First Search - BFS. You can precompute result with using only one BFS. You start in vertex representing final state and for each other vertex you remembered the shortest path from final state to this state. That is also answer, if we start in this state. If you cannot reach some state from final state, than answer is -1.
9! is a lot of states to draw on paper, you can try with 2x2 board first (and skip the “prime property”)…
Graph definition is as follows, vertexes are all possible board configurations and there is directed edge from configuration C1 to C2 iff C2 is created from C1 by swapping numbers
1 2 -> 1 4 // two states, one edge - 2 and 4 swapped
3 4 3 2
@avanee >> Then forget the problem for now I would say, and improve on basics. Don’t expect entire work to be done by others. You asked for an efficient algorithm and @michal27 and @betlista have already done that. Do more problems on graphs and then come back to this. Put some effort from your side too.
