CS 141 - Lab 8
8-Puzzle
Directions
Find a partner. Solve the following programming
problem in C++. When you finish, turn it in electronically, one copy
per team. When you are done, you should work on Programming Assignment 4.
Overview
Given a Puzzle class that represents the state of the
"8 puzzle", implement BFS to find the shortest sequence of moves to find
the solution to the puzzle.
Details
If you don't know what the 8-Puzzle is, spend a few minutes Googling it to
figure it out. Now, download the following files:
puzzle.h
puzzle.o
I have implemented, in puzzle.o, a Puzzle class (the interface to which
is publicized in puzzle.h). It stores a single state of the 8-Puzzle,
and allows you to permute that state, returning the new permutation.
(Read puzzle.h for full information.)
Your job is to implement BFS on this state type, and print out the
shortest path from an initial configuration to the solved configuration.
Your main() function should input 9 distinct (each one different) integers
(0-8) from standard input and use those as an initial configuration.
Then run BFS from that configuration until "isSolved()" returns true.
Print out the list (using the provided << operator) of states that
you pass through on the way to a solution. Please give preference to the
operations in the following manner (so as to arbitrate equal length paths).
Testing
You may want to create your own test cases for this, but please do so
by hand (rather than randomly). There are unsolvable puzzles, and
the possible puzzle-space is of size 9! = 362880, which could take a little
while to search through.
Test cases can be found here. Run these using regular UNIX
redirection & testing:
./lab8 < inputFile | diff - outputFile
Where inputFile and outputFile will be a pair of these:
lab8test1.in
lab8test1.out
lab8test2.in
lab8test2.out
lab8test3.in
lab8test3.out