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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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 | +---+---+---+ | - | 4 | 7 | +---+---+---+	and	| 4 | 5 | 6 | +---+---+---+ | 7 | 8 | - | +---+---+---+

the object is to move from the former to the latter by sliding the tiles around.


Write a program

Nine20  [-r] [-n] [HEIGHT WIDTH] MAXSTEPS 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, Nine20 uses breadth-first search (see the

description in Note 4) to find some SHORTEST sequence (if one exists) with at

most MAXSTEPS moves and prints out the complete sequence of positions separated

by newlines.  For example,


% ./Nine20 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.,


% ./Nine20 8 236158-47 12345678-


(since the shortest sequence has 10 moves) or


% ./Nine20 100 12345678- 12345687-


(since there is no sequence of moves from 12345678- to 12345687-.


The label on each tile can be any single printing character (see "man isprint")

other than -, which denotes the empty square, but the labels may not be unique.

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., for a 4 x 3 puzzle:



+---+---+---+       +---+---+---+    +---+---+---+    +---+---+---+

| 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, Nine20 searches for some shortest sequence of moves from this more general set.         
  Under the optional (no

extra credit) -n flag, the number of moves is printed instead of the sequence

of positions.



Use the submit command to turn in your source files for Nine20, a Makefile, and

your log file (see the specification for Homework #1).  All files must contain

your name and Yale netID.


YOU MUST SUBMIT YOUR FILES (INCLUDING YOUR LOG FILE) AT THE END OF ANY SESSION

WHERE YOU WRITE OR DEBUG CODE, AND AT LEAST ONCE EVERY HOUR DURING LONGER

SESSIONS.  (All submissions are retained.)


Notes

~~~~~

1. Your program should represent positions as null-terminated strings in the

format used to specify the INITIAL and GOAL positions on the command line.

This is based on the normal row-by-row mapping of a 2D array to a 1D array.

2. Nine20 verifies that the command-line arguments are valid, g.,

   • HEIGHT and WIDTH (if present) are sequences of digits

• HEIGHT and WIDTH (if present) are positive integers between 2 and 5

• MAXSTEPS is a sequence of digits

• 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.

Warning:  More than 1/4 of the tests will involve detecting errors in the

command-line arguments.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme