Game "15"

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.


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:

  1. Output will start with total number of shifts.
  2. Each shift will be represented as one word 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.

Description of file format

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 X
Note: 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).

Maximal number of points assigned for functionality
Part Points
Basic functionality 15
Support for -solve 25
Support for -show 15
Support for alternative final state5