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.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of