The puzzle consists of a 4 by 4 grid containing 15 slideable squares
and one blank space. The puzzle is initialized by randomly sliding the
squares until they are sufficiently "shuffled". The player then moves
individual squares, or entire rows/columns until the pieces are back in
ascending order. To make moves, specifying the "to" and "from" positions would be burdensome. Instead, moves are identified by specifying a square that is in the same row or column as the blank space. The application then responds by moving all squares between the blank space and the designated square in the direction of the blank space. The projectWrite an implementation that supports the demonstrated DOS user interface. Later, modify the application to support a user-specified width and height. Finally, adapt the design to include a graphical user interface like that to the right.Five iterations:
Iteration 1What data structure would best support the functionality we are trying to capture. With the DOS user interface, we need to model rows and columns. With the subsequent graphical user interface, rows and columns will be managed for us by the GridLayout component. A one-dimensional array optimizes simplicity, but requires the developer to row-column logic. A two-dimensional array optimizes row-column logic, but requires a double loop construct every time any element is accessed.
|
> java FifteenPuzzleDos 9 3 4 12 10 13 5 8 2 14 1 7 6 11 15 Move: 9 3 4 12 9 13 5 8 10 2 14 1 7 6 11 15 Move: 12 3 4 12 9 13 5 8 10 2 14 1 7 6 11 15 |
In the spirit of "make it run", the first iteration will be limited to
the subset of functionality demonstrated to the right.
When the user specifies a "move", the program should find the
corresponding square, add 10 to that square's value, and re-display the
puzzle. Instructions and issues:
int number; while (true) { System.out.print( "\nMove: " ); number = Integer.parseInt( IOutils.getKeyboard() ); if (number == 0) break; } Iteration 2The puzzle is begun once the squares have been sufficiently scrambled. How is that done in the real game? Do you take all the squares out of the board, and then put them back on the board in jumbled order? I hope not. When I first implemented this puzzle, I wrote a very simple algorithm that basically did just that. It wasnt until the next day that I realized you can make the puzzle unsolvable by truly randomizing the squares.
|
> java FifteenPuzzleDos 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Move: 3 1 2 13 4 5 6 7 8 9 10 11 12 13 14 15 Move: 13 1 2 23 4 5 6 7 8 9 10 11 12 13 14 15 Move: 13 1 2 23 4 5 6 7 8 9 10 11 12 23 14 15 |
2 4 8 5 7 12 11 6 13 3 14 10 1 15 9 Move:Instructions and issues:
1 2 8 3 5 6 11 14 7 4 12 9 10 13 15 Move: 11 1 2 8 3 5 6 11 14 7 4 12 9 10 13 15 Move: 6 1 2 8 3 5 6 11 14 7 4 12 9 10 13 15 Move: 8 1 2 3 5 6 8 11 14 7 4 12 9 10 13 15Instructions and issues:
9 8 3 4 11 2 6 12 1 7 15 14 10 13 5 Move: 5 9 8 3 4 11 2 6 12 1 7 15 14 10 13 5 Move: 4 9 8 3 11 2 6 4 1 7 15 12 10 13 5 14 Move: 9 9 8 3 11 2 6 4 1 7 15 12 10 13 5 14Instructions and issues:
This would have been invaluable advice before we started the first iteration. A 4-by-4 grid is certainly the most common implementation of this puzzle, but there is nothing inherently sacred about that configuration. Let's use this iteration to test the Weinberg assertion. Refactor the current implementation to request the dimensions of the puzzle's grid.
The more general problem is often easier to solve, and in programming, the more general design may be easier to implement, may operate faster on the machine, and can actually be better understood by the user. In addition, it will almost certainly be easier to maintain, for often we won't have to change anything at all to meet changing circumstances that fall within its range of generality. [Gerald Weinberg]
Width: 7 Height: 3 10 1 2 4 6 7 9 11 3 5 13 20 14 8 16 15 17 18 19 12 Move: 2 10 1 2 4 6 7 9 11 3 5 13 20 14 8 16 15 17 18 19 12 Move: 5 10 1 2 5 4 6 7 9 11 3 13 20 14 8 16 15 17 18 19 12 Move: 9 10 1 2 5 4 6 7 9 11 3 13 20 14 8 16 15 17 18 19 12Instructions and issues:
The next decision to face is what kind of array? One-dimensional, or two-dimensional? The latter would seem to be an obviously natural mapping. But, whenever the array needs to be initialized or searched, a double loop construct is necessary. Because a a single loop is half as much effort as a double loop, a one-dimensional array was chosen in listing 2.1.
Using a one-dimensional array means that we will have to do for ourselves what the compiler is happy to do for us make a one-dimensional address space appear as though it is actually two-dimensional. The logic "squares[i * 4 + j]" in the display() function is where the 1D-to-2D magic happens. If we had chosen a 2D data structure, the code would have been reduced to "squares[i][j]".
Listing 2.1 uses a constructor to load the values 1-15 into positions 0-14.
A value of zero was chosen to model the blank space. The actual "blank" is produced with logic encapsulated in the format() function.
The move() function doesnt require any more sophistication than sequential search.
Once the FifteenPuzzleDos class exists, main() is easy: create an instance of this remarkable tool, and iteratively display the board, solicit moves, and execute each move.
Listing 2.1
public class FifteenPuzzleDos { private int[] squares = new int[16]; public FifteenPuzzleDos() { for (int i=1; i < squares.length; i++) squares[i-1] = i; } public static void main( String[] args ) { FifteenPuzzleDos puzzle = new FifteenPuzzleDos(); int number; while (true) { puzzle.display(); System.out.print( "\nMove: " ); number = Integer.parseInt( IOutils.getKeyboard() ); if (number == 0) break; puzzle.move( number ); } } public void display() { System.out.println(); for (int i=0; i < 4; i++) { for (int j=0; j < 4; j++) System.out.print( format( squares[i * 4 + j] ) ); System.out.println(); } } private String format( int number ) { if (number == 0) return " "; return ((number < 10) ? " " : "") + number + " "; } public void move( int number ) { for (int i=0; i < squares.length; i++) if (squares[i] == number) { squares[i] += 10; break; } } }
Since the board needs to start out in a random state, the constructor should be assigned this initialization responsibility.
In the previous iteration, the blank started at position 15. From here, it can choose to travel to either of its neighbors positions 14 or 11. If it chose position 11, its next array of choices would be: 7, 10, or 15. It would seem useful to have a tool capable of computing all the neighbors of a specified square. Lets discuss the contract - what is required by, and what is expected of - for a find neighbors function.
It needs to know the position for which the neighbors are being requested. It then needs to return a list of the legal neighbors. Is the number of neighbors always the same? Some positions have four neighbors, but others have two or three. So, the function needs to return two things: the list of neighbors, and the number of elements in that list. We could try to mash both of these items into the functions return value. This would work if we returned the list of neighbors, and, established the convention that the first element in the list is the number of neighbors in the list.
Another choice would be to return a smart array an array that knows its own size. Arrays in Java provide that capability if they are created to be the correct size. Using this option would require creating a new array object each time our new findNeighbors function is called.
Yet another choice would use an output array parameter for the list of neighbors, and the return value of the function for the number of neighbors that were written to the array parameter. The user of the findNeighbors function passes in an array of length four, and the function populates the array with two, three, or four elements. This is the choice made in listing 2.2.
int[] neighborsArray = new int[4]; numberOfNeighbors = findNeighbors( blankPosition, neighborsArray );Once we have a findNeighbors abstraction (the implementation of which is conveniently deferred for now), the rest is easy. Simply pick a random element in the neighbors array, swap that square with the blank, and update the value of the blank variable.
moveToPosition = neigborsArray[ rn.nextInt(numberOfNeighbors) ]; temp = squares[moveToPosition]; squares[moveToPosition] = squares[blankPosition]; squares[blankPosition] = temp; blankPosition = moveToPosition;To pick a random element, we use the same nextInt() method as was used in the Mastermind project. That means a Random object will need to be added to our classs suite of attributes.
Listing 2.2 moves the blank 200 times in the scramble() method. This seems to produce a sufficiently random starting position.
The final piece is the findNeighbors() method. If the blank is on the top row, there is no neighbor above the blank. If the blank is on the bottom row, left column, or right column, then there is no neighbor: below, left, or right, respectively. Once the boundary conditions have been satisfied, we can populate the neigborsArray.
The above neighbor for position 4 is 0. The above neighbor for position 8 is 4. Do we have to write code to manually capture the above neighbor for all 12 positions that have an above neighbor? Or can we compute that neighbor in some general fashion?
Fortunately, there is a pattern every above neighbor can be found by subtracting 4 from the position of the original square. A similar computation works for finding below, left, and right neighbors. Listing 2.2 collects the complete changes for this iteration.
Listing 2.2
import java.util.Random; public class FifteenPuzzleDos { private Random rn = new Random(); private int[] squares = new int[16]; public FifteenPuzzleDos() { for (int i=1; i < squares.length; i++) squares[i-1] = i; scramble(); } private void scramble() { int[] neighbors = new int[4]; int numNeighbors, temp, moveTo, blank = 15; for (int i=0; i < 200; i++) { numNeighbors = findNeighbors( blank, neighbors ); moveTo = neighbors[ rn.nextInt(numNeighbors) ]; temp = squares[moveTo]; squares[moveTo] = squares[blank]; squares[blank] = temp; blank = moveTo; } } private int findNeighbors( int blank, int[] array ) { int numNeighbors = 0; if (blank > 3) array[numNeighbors++] = blank - 4; if (blank < 12) array[numNeighbors++] = blank + 4; if (blank % 4 != 0) array[numNeighbors++] = blank - 1; if (blank % 4 != 3) array[numNeighbors++] = blank + 1; return numNeighbors; } public void move( int number ) { ... } private String format( int number ) { ... } public void display() { ... } public static void main( String[] args ) { ... } }
Each function has the same form. If the specified position is "on the edge", then do nothing. If the blank space is not found, then do nothing. Otherwise, swap the specified position and its neighbor. If this function succeeded, then there is no need to evaluate the other functions.
private boolean tryAbove( int position ) { if (position < 4) return false; if (squares[position-4] != 0) return false; swap( position, position-4 ); return true; }Notice the logic for evaluating boundary conditions and direction. The modulus operator (aka [also known as] - the "remainder" operator) is very nondescript, but the leverage it offers is invaluable in many contexts. Here, it is perfect for identifying if the specified position is on the left or right edge. Many of the values hard-wired here will need to be fixed in iteration 4 when the width and height of the puzzle are configurable by the user.
private boolean tryAbove( int pos ) { if (pos < 4) return false; if (squares[pos-4] != 0) ... private boolean tryBelow( int pos ) { if (pos > 11) return false; if (squares[pos+4] != 0) ... private boolean tryLeft( int pos ) { if (pos % 4 == 0) return false; if (squares[pos-1] != 0) ... private boolean tryRight( int pos ) { if (pos % 4 == 3) return false; if (squares[pos+1] != 0) ...The modulus operator is a remarkable tool in the hands of a craftsman.
Listing 2.3
import java.util.Random; public class FifteenPuzzleDos { private Random rn = new Random(); private int[] squares = new int[16]; public FifteenPuzzleDos() { for (int i=1; i < squares.length; i++) squares[i-1] = i; for (int i=0; i < 400; i++) move( rn.nextInt(squares.length-1) + 1 ); } public void move( int number ) { if (number >= squares.length) return; int i; ////// find the slot this number is in ////// for (i=0; i < squares.length; i++) if (squares[i] == number) break; if (tryAbove(i)) return; if (tryBelow(i)) return; if (tryLeft(i)) return; if (tryRight(i)) return; } private boolean tryAbove( int pos ) { if (pos < 4) return false; if (squares[pos-4] != 0) return false; // the square above is blank swap( pos, pos-4 ); return true; } private boolean tryBelow( int pos ) { if (pos > 11) return false; if (squares[pos+4] != 0) return false; swap( pos, pos+4 ); return true; } private boolean tryLeft( int pos ) { if (pos%4 == 0) return false; if (squares[pos-1] != 0) return false; swap( pos, pos-1 ); return true; } private boolean tryRight( int pos ) { if (pos%4 == 3) return false; if (squares[pos+1] != 0) return false; swap( pos, pos+1 ); return true; } private void swap( int one, int two ) { int temp = squares[one]; squares[one] = squares[two]; squares[two] = temp; } private String format( int number ) { ... } public void display() { ... } public static void main( String[] args ) { ... }
Notice that each tryXxx() function calls itself until the edge is found. If the neighbor is the blank - or - a downstream neighbor is a neighbor to the blank, then the current square should be swapped, and all upstream neighbors should be told to swap themselves.
private boolean tryAbove( int pos ) { if (pos < 4) return false; if (squares[pos-4] != 0 && ! tryAbove(pos-4)) return false; // the slot above is blank OR the move above succeeded swap( pos, pos-4 ); return true; } private boolean tryBelow( int pos ) { if (pos > 11) return false; if (squares[pos+4] != 0 && ! tryBelow(pos+4)) return false; swap( pos, pos+4 ); return true; } private boolean tryLeft( int pos ) { if (pos%4 == 0) return false; if (squares[pos-1] != 0 && ! tryLeft(pos-1)) return false; swap( pos, pos-1 ); return true; } private boolean tryRight( int pos ) { if (pos%4 == 3) return false; if (squares[pos+1] != 0 && ! tryRight(pos+1)) return false; swap( pos, pos+1 ); return true; }
private boolean tryBelow( int position ) { if (position > width*(height-1)-1) return false;This is simply computing the threshold of square positions that fall on the bottom row.
Never solve a specific problem, when the solution to a general problem (that can be reasonably anticipated) is no more expensive.
Listing 2.5
private int[] squares; private int width, height; public FifteenPuzzleDos( int w, int h ) { width = w; height = h; squares = new int[w*h]; ... } private boolean tryAbove( int pos ) { if (pos < width) return false; if (squares[pos-width] != 0 && ! tryAbove(pos-width)) return false; swap( pos, pos-width ); return true; } private boolean tryBelow( int pos ) { if (pos > width*(height-1)-1) return false; if (squares[pos+width] != 0 && ! tryBelow(pos+width)) return false; swap( pos, pos+width ); return true; } private boolean tryLeft( int pos ) { if (pos % width == 0) return false; if (squares[pos-1] != 0 && ! tryLeft(pos-1)) return false; swap( pos, pos-1 ); return true; } private boolean tryRight( int pos ) { if (pos % width == width-1) return false; if (squares[pos+1] != 0 && ! tryRight(pos+1)) return false; swap( pos, pos+1 ); return true; } private void swap( int one, int two ) { ... } private String format( int number ) { ... } public void move( int number ) { ... } public void display() { System.out.println(); for (int i=0; i < height; i++) { for (int j=0; j < width; j++) System.out.print( format( squares[i * width + j] ) ); System.out.println(); } } public static void main( String[] args ) { System.out.print( "\nWidth: " ); int w = Integer.parseInt( IOutils.getKeyboard() ); System.out.print( "Height: " ); int h = Integer.parseInt( IOutils.getKeyboard() ); FifteenPuzzleDos puzzle = new FifteenPuzzleDos( w, h ); ...