By Gabriel Duarte, UNIFESO Brazil
João is a boy who loves to play with logic games, he spends several hours of your day solving puzzles.
Currently the game that he's spending more time playing is the Sliding Puzzle, also known as Game of Eight, in which he has at hand a tray of 3 rows and 3 columns where each element of this board has a number or a blank space.
The object of the game is simple, given a scrambled board (Figure 1), João should leave it ordered (Figure 2) and the only movement possible to solve the problem is to move a number to the blank space.
Solve the toy is not a problem for João, he's already doing it without difficulty, but he was intrigued to know what is the minimum number of moves needed to solve.
Figure 1 - Figure 2
The input consists of several test cases, each case will have 3 lines each with 3 numbers 0-8, where zero represents the blank space. Assume that the toy is always scrambled.
The entry ends with the end of the file.
For each test case print the message "Quantidade minima de passos = X", where X is the total required, followed by the steps made to resolve, each step must be separated by a blank line. if you can't solve the problem print: "Problema sem solucao".
Input Sample | Output Sample |
123 |
Quantidade minima de passos = 2
123 |