Game "15" was invited by American puzzlecreator Sam Loyd. It is played on a square playing desk which is divided into 16 fields (4 rows and 4 columns). The game is played with 15 playing cards numbered from 1 to 15. At the start of game playing cards are placed on the playing desk in any order. One field is empty. Playing cards can be shifted only if they are beside the empty field. In that case playing card can be shifted into the empty field. Goal of the game is to order playing cards accordingly to following picture.
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 |
It is proved that there exist initial placement of playing cards which can not be transformed to the goal state by shifting playing cards.
Write a program which will be able to solve game "15". Name the program xxgame (where xx is your starting number). The program will accept one argument and optional switch.
xxgame [switch] <filename>
The argument specifies name of file with initial placement of playing cards. Format of this file is described bellow.
When the program is started only with argument specifying file with initial placement then your program should decide if it is possible to reach the goal state from given initial state.
If the program is started with switch -solve then it
should find an optimal solution of the game. The optimal solution is
solution with minimal number of shifts needed for reaching the goal
state. The solution will be written into standard output with the
following format:
LEFT,
RIGHT, DOWN or UP. The word
corresponds to direction of shifting.
If the program is started with switch -show then it
also should find an optimal solution. The solution should be presented
graphically.
If you have done previous tasks, you should extend your program that it will accept second argument. This argument will be treated as a name of file which contains description of the goal state. In such case you program should treat this state as the final state instead of default.
Each definition file is a text file. A file contains 15 numbers and
one letter 'X' separated with whitespaces. Each number
corresponds to one playing card. Letter 'X' corresponds to
an empty field. Playing cards are written to a file from the top to the
bottom and from the left to the right.
Example: The default goal state can be written to a file as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 XNote: We use fact that new-line char is treated as whitespace to nicely format data.
Your program and all its modules should be stored in the directory
C:\ICP. Name the modules in such way that the two first
letters of its name are your starting number.
Write your starting number, a list of all used modules and a list of switches which are supported in your program as a comment at the beginning of the program.
There are several files with extension pos in the
directory C:\ICP. These files contain definitions of
several playing card placements and you can use them for testing purposes.
There is also game program which presents a very simple
sample solution of the task.
The permitted aid is English vocabulary, books which describe programming language, its environment (IDE) and standard libraries. You can not use books with description of various methods, algorithms and data structures.
You can get total of 100 points. 60 out of them are used for evaluating functionality, 30 for evaluating efficiency (smart and fast algorithms, sophisticated data structures). Last ten points are used for documentation (description of algorithm, comments, naming convention, neat way of writing code).
| Part | Points |
|---|---|
| Basic functionality | 15 |
Support for -solve | 25 |
Support for -show | 15 |
| Support for alternative final state | 5 |