P R E L I M I N A R Y S P E C I F I C A T I O N Due 2:00 am, Friday, 09 April 2009 CPSC 223b Homework #5 Hashes and Deques Redux: The Nine Puzzle (40) The nine puzzle is a square 3x3 tray in which are placed 8 square 1x1 tiles numbered from 1 to 8. The remaining space is empty, so an adjacent tile can slide into that space, leaving its former location empty. For example, +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | 1 | 2 | 3 | | 1 | 2 | 3 | | 1 | - | 3 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | 4 | - | 5 | ==> | - | 4 | 5 | or | 4 | 2 | 5 | or | 4 | 5 | - | or ... +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | 6 | 7 | 8 | | 6 | 7 | 8 | | 6 | 7 | 8 | | 6 | 7 | 8 | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ (where - denotes the empty space). Given an initial configuration and a goal configuration, for example, +---+---+---+ +---+---+---+ | 2 | 3 | 6 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ | 1 | 5 | 8 | and | 4 | 5 | 6 | +---+---+---+ +---+---+---+ | - | 4 | 7 | | 7 | 8 | - | +---+---+---+ +---+---+---+ the object is to move from the former to the latter by sliding the tiles around. Write a program Nine09 [-r] [-n] [HEIGHT WIDTH] MAXLENGTH INITIAL GOAL that solves the nine puzzle given an INITIAL position (236158-47 above) and a GOAL position (12345678- above). To make the task more challenging, Nine09 uses breadth-first search (see Note 4) to find some SHORTEST sequence of at most MAXLENGTH moves (if one exists) and prints out the complete sequence of positions separated by newlines; e.g., % Nine09 100 236158-47 12345678- 236158-47 2361584-7 23615847- 23615-478 23-156478 2-3156478 -23156478 123-56478 123456-78 1234567-8 12345678- If no such move sequence exists, then nothing is printed; e.g., % Nine09 100 12345678- 12345687- The label on each tile can be any single printing character (other than -, which denotes the empty square), but the labels need not be unique. The optional -n flag causes the number of moves to be printed instead of the sequence of positions. The optional HEIGHT and WIDTH (whose default values are 3 and 3) allow other rectangular puzzles to be solved as well. In a real nine puzzle, it is as easy to move a line (vertical or horizontal) of tiles as a single tile; e.g., +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | 1 | 2 | 3 | | 1 | 2 | - | | 1 | 2 | 3 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | 4 | 5 | 6 | | 4 | 5 | 3 | | 4 | 5 | - | | 4 | 5 | 6 | +---+---+---+ ==> +---+---+---+ or +---+---+---+ or +---+---+---+ or ... | 7 | 8 | 9 | | 7 | 8 | 6 | | 7 | 8 | 6 | | 7 | 8 | - | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | a | b | - | | a | b | 9 | | a | b | 9 | | a | b | 9 | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ Under the optional (no extra credit) -r flag, Nine09 searches for some shortest sequence of moves from this more general set. Use the submit command to turn in the source files for Nine09, a Makefile, and your log file (see Homework #1). YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION WHERE YOU SPEND AT LEAST ONE HOUR WRITING OR DEBUGGING CODE, AND AT LEAST ONCE EVERY FIVE HOURS DURING LONGER SESSIONS. (ALL SUBMISSIONS ARE RETAINED.) Notes: 1. Your program should represent a position as a null-terminated string in the format used to specify the INITIAL and GOAL positions on the command line. 2. Your program may assume that both HEIGHT and WIDTH are between 2 and 4. Indeed, you may find it easier to debug using a 2x3 or 3x2 (or even 2x2) tray since the number of possible states is much smaller. 3. Your program should verify that the command-line arguments are valid, e.g., - HEIGHT and WIDTH (if present) are positive integers between 2 and 4 - MAXLENGTH is a nonnegative integer - INITIAL and GOAL have the correct number of characters for the tray size - the characters appearing in INITIAL include precisely one - - the same characters (counting multiplicities) appear in GOAL and write a one-line error message to stderr and immediately exit otherwise. 4. Your program should find a shortest sequence of moves by breadth-first traversal/search using a hash table of (POSITION, REACHED-FROM, LENGTH) triples (*) and a queue of positions to visit: add the triple (GOAL, NULL, 0) to the hash table add the GOAL position to the queue while the queue is not empty remove the position P at the head of the queue let L be the length associated with P in the hash table if (L < MAXLENGTH) for each position P' reachable from P by moving one tile if P' is the INITIAL position print the sequence of moves and exit else if P' is not in the hash table add the triple (P', P, L+1) to the hash table add P' to the queue endif endfor endif endwhile Points to Ponder: Why start the search at the GOAL position? Is this algorithm complete as stated? (*) POSITION is the "current" position; REACHED-FROM is the position from which you moved to get here; LENGTH is the number of moves required to get here from the GOAL position. POSITION is the hash key; REACHED-FROM and LENGTH are attributes. 5. The hash table should be implemented as a separate module (and in a separate file) so that the code could be used in another application. It may use either chaining or linear probing, but to keep the load average low there should be roughly 50000 (chaining) or 300000 (linear probing) entries when solving the 3x3 puzzle (see below). The size may be independent of the tray size. 6. Your hash function should depend on all of the bits in the representation yet be general enough to handle changes in the symbolic constants that define the size of the tray. As discussed in class, reducing the string to an unsigned integer can be done with a combination of shifts/multiplies (to move bits to the left) and adds/xors (to introduce new characters). Good performance dictates that this integer not be invariant under permutations or depend on a subset of the characters (why?). Together with the fact that it should have as many as six digits unless the number of squares in the tray is very small (why?), this constrains the sizes of the shifts/multipliers. Reducing the integer to a number between 0 and the size of the hash table can be done by taking a remainder. One such function is /* Return hash of string into [0,SIZE) */ static int hash (char *s) { unsigned int sum; for (sum = 0; *s; s++) sum = (sum<<2) ^ *s; return sum % SIZE; } 7. You may reuse your Deque data structure from Homework #3 or use Hwk5/Deque.* (which is my benevolent implementation). 8. Warning: If there is no solution, the hash table will contain 9!/2 = 181440 entries when the while-loop ends (*). Thus your representation should be reasonably space-efficient (e.g., no more than 100 bytes per hash table entry). You may need to use the csh or tcsh command % limit datasize #kb or the bash command % ulimit -d #kb to allow your program to grow that large (otherwise malloc() may return NULL, which could lead to segmentation violations). (*) There are 9! arrangements of the 8 tiles and the empty square. However, these arrangements lie in two isomorphic sets and it is not possible to go from a member of one to a member of the other by sliding tiles. CS-223-03/25/09