Listing 5-A
Listing 5-B
Listing 5-C
Listing 5-D
Listing 5-1
Listing 5-2
Listing 5-A UML notation for ADT flight map possible operations |
// Reads flight information into the flight map. +readFlightMap(cityFileName: string, flightFileName: string): void // Displays flight information. +displayFlightMap(): void // Displays the names of all cities that HPAir serves. +displayAllCities(): void // Displays all cities that are adjacent to a given city. +displayAdjacentCities(aCity: City): void // Marks a city as visited. +markVisited(aCity: City): void // Clears marks on all cities. +unvisitAll(): void // Sees whether a city was visited. +isVisited(aCity: City): boolean // Inserts a city adjacent to another city in a flight map. +insertAdjacent(aCity: City, adjCity: City): void // Returns the next unvisited city, if any, that is adjacent to a given city. // Returns a sentinel value if no unvisited adjacent city was found. +getNextCity(fromCity: City): City // Tests whether a sequence of flights exists between two cities. +isPath(originCity: City, destinationCity: City): boolean |
Listing 5-B C++ implementation of searchR |
/** Tests whether a sequence of flights exists between two cities.
@pre originCity and destinationCity both exist in the flight map.
@post Cities visited during the search are marked as visited
in the flight map.
@param originCity The origin city.
@param destinationCity The destination city.
@return True if a sequence of flights exists from originCity.
to destinationCity; otherwise returns false. */
bool Map::isPath(City originCity, City destinationCity)
{
bool result,
done;
// Mark the current city as visited
markVisited(originCity);
// Base case: the destination is reached
if (originCity == destinationCity)
result = true;
else // Try a flight to each unvisited city
{
done = false;
City nextCity = getNextCity(originCity);
while (!done && (nextCity != NO_CITY)) {
done = isPath(nextCity, destinationCity);
if (!done)
nextCity = getNextCity(originCity);
} // end while
result = done;
} // end if
return result;
} // end isPath
|
Listing 5-C Pseudocode of algorithm for placing queens in columns |
// Places queens in eight columns.
placeQueens(queen: Queen):void
if (queen 's column is greater than the last column )
The problem is solved
else
{
while ( unconsidered squares exist in queen' s column and the problem is unsolved)
{
Find the next square in queen 's column that is
not under attack by a queen in an earlier column
if ( such a square exists )
{
Place a queen in the square
// Try next column
placeQueens( new Queen(firstRow, queen' s column + 1))
if (no queen is possible in the next column)
{
Delete the new queen
Remove the last queen placed on the board and
consider the next square in that column
}
}
}
}
|
Listing 5-1 The header file for the class Board |
/** @file Board.h */
#ifndef _BOARD
#define _BOARD
#include "Queen.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
static const int BOARD_SIZE = 8;
class Board
{
private:vector < queens * >queens; // Array of pointers to queens on the board
/** Sees whether a queen exists in position (inRow, inCol). */
bool isQueen (int inRow, int inCol) const;
/** Attempts to place queens on board, starting with the designated queen. */
const placeQueens (Queen * queenPtr);
/** Removes the last queen from the board, but does not deallocate it. */
void removeQueen ();
/** Places a queen on the board. */
void setQueen (const Queen * queenPtr);
public:
/** Supplies the Queen class with a pointer to the board. */
Board ();
/** Clears the board and removes pointer from queens. */
~Board ();
/** Clears board. */
void clear ();
/** Displays board. */
void display () const;
/** Initiates the Eight Queens problem. */
void doEightQueens ();
/** @return The number of queens on the board.*/
int getNumQueens () const;
/** @return A pointer to the queen at the designated index.*/
const Queen *getQueen (int index) const;
}; // end Board
#endif
|
Listing 5-2 The class Queen |
class Board; // Forward declaration of Board class
/** The Queen class. */
class Queen
{
public:
/** Places a queen in upper-left corner of board. */
Queen ();
/** Places a queen in supplied location. */
Queen (int inRow, int inCol);
/** @return Column number. */
int getCol () const;
/** @return Row number. */
int getRow () const;
/** Moves queen to next row. */
void nextRow ();
/** Sees whether the queen is under attack by another queen.
@return True if another queen is in the same row or the same
diagonal; otherwise, returns false. */
bool isUnderAttack () const;
/** Saves a pointer to the board for all queens. */
static void setBoard (const Board * bPtr);
private:
int row; // Row (or prospective row) of queen if it is on the board
int col; // Column (or prospective column) of queen if it is on
// the board
// All queens share the same board
static const Board *boardPtr;
}; // end Queen
|
Listing 5-D An implementation of placeQueens |
bool Board::placeQueens (Queen * queenPtr)
{
// Base case: Try to place a queen in a nonexistent column.
if (queenPtr->getCol () >= BOARD_SIZE)
{
delete queenPtr;
return true;
} // end if
bool isQueenPlaced = false;
while (!isQueenPlaced && queenPtr->getRow () < BOARD_SIZE)
{
// If the queen can be attacked, try moving it
// to the next row in the current column
if (queenPtr->isUnderAttack ())
queenPtr->nextRow ();
else
{
// Put this queen on the board and try putting a
// new queen in the first row of the next column
setQueen (queenPtr);
Queen *newQueenPtr = new Queen (0, queenPtr->getCol () + 1);
isQueenPlaced = placeQueens (newQueenPtr);
// If it wasn't possible to put the new queen in the next column,
// backtrack by deleting the new queen and moving the last
// queen placed down one row
if (!isQueenPlaced)
{
delete newQueenPtr;
removeQueen ();
queenPtr->nextRow ();
} // end if
} // end if
} // end while
return isQueenPlaced;
} // end placeQueens
|