Background

Puzzle of Fifteen

This exercise involves a well-known puzzle often referred to as the 'Puzzle of Fifteen'. The exact origin of the puzzle is unknown, but it first came to popularity in America during the 1870s. The puzzle consists of fifteen square tiles, labelled numerically from 1 to 15. They are arranged in a random ordering within a square tray that is just large enough to hold sixteen tiles in a 4 x 4 grid (see fig 1). The tiles should then be slid around the tray until they are in the correct ordering as shown in fig 2, with the blank space at the bottom-right hand corner. The tiles must not be picked out of the tray.

fig 1 6 1 10 2 7 11 4 14 5   9 15 8 12 13 3

fig 2: Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Loyd's Fifteen

Sam Loyd was an American puzzle-inventor during the 1870s. He was regarded by many as the greatest puzzle-maker in the world. In 1878, Loyd marketed his own version of the Puzzle of Fifteen - 'Loyd's Fifteen' (also called the 14-15 game). In essence it was the same game, but the difference Loyd made was to provide an initial tile arrangement. Loyd's initial set-up was as if the game had been completed, but then the 14 and 15 tiles were swapped (see fig 3). The aim of the game was as before- to arrange the tiles in ascending order. Loyd offered $1000 to anyone who could demonstrate their solution to the game. A craze for the puzzle hit the world, one which was not rivalled until the Rubik's Cube of the 1980's. People from all walks of life became hooked on the puzzle whose solution always seemed to be just around the next corner. However, no-one managed to solve the problem. Several years (and many puzzle sales), later, the impossibility of Loyd's puzzle was mathematically proven.

fig 3: Loyd's Fifteen

1	2	3	4
5	6	7	8
9	10	11	12
13	15	14

Sam Loyd had taken advantage of the fact that there are two state spaces involved in this game. A state space is a set of states (ie. tile arrangements) where every element can be transformed into any other element of that set through the normal transformation procedures. However, no state can be transformed legally into an element of a different state space. In the 'Puzzle of Fifteen', exactly half of all arrangements belong in state space 'A', (including the solution arrangement), and exactly half belong in state space 'B', (including, of course, Loyd's arrangement!). It turns out that when given a tile arrangement that belongs to the unsolvable state space, a new arrangement can be generated that belongs to the solvable state space by simply swapping two adjacent tiles (without disturbing any others). The opposite, of course, is also true. So it is not possible to swap two adjacent tiles without upsetting the arrangement of other tiles. That is why Loyd's Fifteen cannot be solved. This concept is not simple even for the educated minds of today, so it is hardly surprising that Loyd had so many people fooled back in the nineteenth century!

Rate Your Mind, Pal!

Over the 124 years since Sam Loyd's puzzle kick-started the sliding tile game market, many more tile puzzles have been devised. One of particular interest is the 'Rate Your Mind Pal' puzzle, which, again, involves a 4 x 4 grid of sliding tiles. This time, the tiles are labelled with characters, initially forming the phrase 'RATE YOUR MIND PLA', as shown in fig 4. The task is to rearrange the tiles to form the corrected phrase 'RATE YOUR MIND PAL', with the blank space in its usual position at the bottom right of the grid. At a first glance, this seems to be identical to the 14-15 puzzle, and therefore appears impossible. However, there is a subtle difference, and the 'Rate Your Mind Pal' game can be solved. See if you can spot the subtle difference and solve the problem.

fig 4: Rate Your Mind Pal

R	A	T	E
Y	O	U	R
M	I	N	D
P	L	A

Lab Exercises

Your task is to create a working 'Puzzle of Fifteen' game. Many versions of the game use a tiled image instead of numbers, simply because it is more pleasing to the eye. Your solution will follow this example by allowing the user to play the game with any jpg or gif image he chooses.

The exercise is split into five parts. You are all expected to have a good attempt at the first three. However, to reach the higher marks, you must complete part four, which requires you to develop a quality user interface. The experts among you should relish the challenge of part five, which will stretch even the most experienced of programmers.

You should use javadoc comments throughout this exercise. To generate documentation for your classes based on your comments, use

kanga% javadoc *.java

There are several 'good' ways of solving this exercise, and a considerable deviation from the model answer is expected. However, there are also many pitfalls and ways to get lost when writing a program of this complexity. So plan everything on paper before you code it, keep your method and variable names consistent and meaningful, make use of static class variables where appropriate and, above all, endeavour to uphold modularity. This means making sure your classes and methods do exactly what they are supposed to do and no more. Most methods have only one function to perform. Do not add 'extra' instructions into methods that cause it to perform more than one function. Decide well in advance which classes will have access to which other classes. Declare private as many of your instance variables as you can.

1. Reading and Displaying an Image on Screen

Write a program called SliderGame that can display an image in a frame. Let the user specify the image in the command line arguments. So, the following line at the xterm prompt

kanga% java SliderGame test.jpg

To create a BufferedImage object, use some code like the following:

ImageIO.read( new File( "foo.jpg" ) );

Hints

• You will need two classes, one that extends JFrame, and one that extends JPanel.
• You should add your JPanel class to the content pane of the JFrame class (e.g. getContentPane().add(p), where p is your panel.).
  
• You should override the paintComponent(Graphics) method in JPanel to display your image. The Graphics class has a method drawImage().
• If you need to provide an ImageObserver object as an argument to a method, use null.

2. Tiling your Image

Adapt your program so that it creates a 4 x 4 grid of tiles, each displaying a piece of the full image. Create only fifteen tiles, as the bottom right tile space should be left blank. Display your tiles on screen in their correct order, as they would appear if you had succesfully completed the Puzzle of Fifteen. Each tile should have a black border of width 1 pixel.

You will need to write a Tile class. The most important method in this class will be a draw method. This will accept a Graphics object as one of its arguments. The draw method is where the image and a border will be drawn.

You should adapt your JPanel class constructor so that it creates and stores the tiles needed for the game. Use a 4 x 4 grid by default. Think about how and where in your program you will define this default setting so that it will be easy to modify.

Remember to use Javadoc comments as you develop your classes.

Hints

• You should organise your grid using an (i, j) co-ordinate system where i refers to the row and j to the column. You should be able to calculate pixel positions for tiles from the i and j variables that denote the cells they occupy on the grid. There are other ways that you could organise your data storage, but this is certainly one of the better ones.
• Remember that the position of the tile within the grid is not the same as its pixel position on the screen, although the two are probably linked by a 1-1 mapping.
• When choosing how to store your data, you should aim to eliminate any redundancy. Stored data that is stored elsewhere, or could be derived from stored data elsewhere, is considered to be redundant (not neccessary).
• Don't forget to update your paintComponent method so that it draws all the Tile objects.

3. Making Moves

Have the tiles shuffled into a random, yet solvable, configuration of positions. Construct an implementation of the MouseListener interface to allow the user to make moves using the mouse. Do not worry about using the mouse to drag a tile- simply clicking on a tile is enough to indicate the move the user wishes to make as there is only one possible place where a tile could move to (the blank). Only legal moves should be allowed, by which it is meant that clicking a tile that is not adjacent to the blank space should not have any effect. Once the game is solved, prevent the user from making any more moves.

Think very carefully about how to approach this part- it is the most important part of the exercise. You may need to improve the way you store the state of the game, but hopefully you can just build on what you already have.

You will need to write a method to shuffle your tiles around. There are more than one ways of doing this, although whatever method you choose, be sure to always leave the tiles in a solvable arrangement. You may find it helpful to read up on some of the theory of the game. Try http://kevingong.com/Math/SixteenPuzzle.html.

Write a method for moving tiles. If you wish, you may write another method that causes the tiles to slide across the screen as well as updating the internal game structure. There are no marks for this, but it will improve the visual impact of the game tremendously.

You should write a class to implement MouseListener. If you make it an inner class it will have access to the variables of the outer class. All new Java books have sections on MouseListeners and how to use them. Try Chapter 8 in Core Java, by Horstmann & Cornell, for example.

Hints

• You might like to download and study the program MyClickExample.java from the Swing lecture of the Red Hot Java Course, which tiles a frame in a slightly different way to here and reports on where the user clicks the mouse.
• Make sure your program can work with different size grids.
• There is a method to check whether any given game state is solvable. You must count the number of inversions in the grid. An inversion is when a tile precedes another tile with a lower number on it. The solution state has zero inversions. For example, if, in a 4 x 4 grid, number 12 is top left, then there will be 11 inversions from this tile, as numbers 1-11 come after it.
  1. If the grid size is odd, then the number of inversions in a solvable situation are even.
  2. If the grid size is even, and the blank is on an odd row (first, third etc), then the number of inversions in a solvable situation are odd.
  3. If the grid size is even, and the blank is on an even row (second, fourth etc), then the number of inversions in a solvable situation are even.
• Make your code as readable as possible. Make use of whitespace, comments and meaningful variable names.
• Continue to use Javadoc comments.
• If you attempt the optional sliding element of this part, you may find it helpful to use the Thread.sleep(int) method to cause your program to pause for a specific length of time.

4. User Interface

Implement a user interface for your game. Allow the user to change the number of tiles on the grid, start a new game or exit the program. When the game is won your program should let the user know by way of a popup message.

This part is left mostly up to you as to how you allow users to choose these options. There is a lot of scope at this stage for experimenting with the vast Swing libraries that Java provides. Refer to the API and Java textbooks for information on using Swing. Horstmann & Cornell's Core Java has a substantial chapter on Swing. If you have the time, feel free to develop your program further, adding more varied options.

Hints

• You should make use of Swing's JMenuBar class so users can select options using a conventional drop-down menu.
• Investigate the JOptionPane class. It has some very useful static methods for you to use to display a popup message.
• You might like to download and study the program BarChartEvents.java from the Swing lecture of the Red Hot Java Course, which also has a menu and some menu items..

5. Computer Player

Implement a function for automatically solving the puzzle. Make this function accessible through your user interface. The tiles must be seen to be moving around the screen in the usual manner.

This part is very hard, and not worth very many marks. It is up to you how you attempt to solve this part. You are not expected to produce an optimal solution. Try searching the web for strategies for solving the puzzle.

Mark scheme

1. Design and coding

2. Reading and displaying an image

3. Tiling your Image

4. Making Moves

5. User Interface

6. Computer Player