Problem I. 265. (April 2011)
I. 265. Many of us know the 15 puzzle, where 15 tiles are shuffled and there is 1 empty square on a \(\displaystyle 4\times 4\) board. During the game one can move any neighboring tile into the empty square. The goal is to put all the 15 tiles into a predefined order, that is, into an ascending order from left to right and from top to bottom.
The original \(\displaystyle 4\times 4\) version can be played on an \(\displaystyle N\times M\) board with the same rules.
Your program should give the steps recovering the original state of the \(\displaystyle N\times M\) board. The first command line argument to your program is the name of the input file, while the second argument is the name of the output file.
The first line of the input file contains the values \(\displaystyle N\le 20\) and \(\displaystyle M\le 20\) separated by a space. Then each of the following \(\displaystyle N\) lines contain \(\displaystyle M\) numbers, separated by a space, describing a shuffled puzzle. The empty square is denoted by a 0.
The first line of the output file contains the (not necessary minimal) number of steps needed to recover the board from the shuffled state. The second line of the output file should contain exactly this number of characters, consisting of letters B, F, J or L. These letters describe in each step the direction from which we move the tile to the empty square (B -- left, F -- above, J -- right, L -- below). If the correct final order can not be realized, the first line of the output should be \(\displaystyle -1\).
In the example, Bemenet is the input, while Kimenet is a possible output.
The source code (i265.pas, i265.cpp, ...) together with a short documentation (i265.txt, i265.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted.
(10 pont)
Deadline expired on May 10, 2011.
Sorry, the solution is available only in Hungarian. Google translation
A feladat jóval nehézséget okozott, mint vártuk: a beküldők egyike sem adott a tesztesetek mindegyikére működő megoldást.
Ketten is utaltak egy működőképes algoritmusra, amely a soronként az első M-1 elemet; a sor utolsó elemét; majd az utolsó két sor elemeit oszloponként teszi helyre. Ezeket elemi lépésekre, az üres helyek tologatására, illetve az üres helyet kezdetben a sarkában tartalmazó téglalap körvonalának forgatására bontották.
A megvalósításba azonban hiba csúszott, ezért a tesztesetek többségében nem kaphattak pontot a versenyzők.
Az értékelésnél használt tesztesetek: i265teszt.zip
Statistics:
3 students sent a solution. 5 points: 1 student. 3 points: 1 student. 2 points: 1 student.
Problems in Information Technology of KöMaL, April 2011