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.C Programming

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.


  1. 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:

Instructions Files

C Programming Experts

expert
Simon M.
C Programming

44 Answers

expert
Arapera Billing
C Programming

89 Answers

View More Experts
Disclaimer

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.

Get Free Quote!

260 Experts Online