Queens

//-----------------------------------------------------------------
// Queens Class.
// A class that helps solve the non-attacking queens problem.
//
//-----------------------------------------------------------------
// Taken from "Data Abstraction and Problem Solving with C++:
//    Walls and Mirrors", 2nd Ed., by Carrano, Helman, and Veroff.
// Significant changes by Charles Cusack, Oct 2000.
//-----------------------------------------------------------------
//
#include <cstdlib>
#include <iostream>
using namespace std;

class Queens
{
public:
   Queens(int n=8); // Creates an empty square board of size n.
   ~Queens();
   
   Queens(const Queens &Q);            // Copy Constructor
   Queens& operator=(const Queens &Q); // Assignment operator.

   void NewBoard(int n);      
   // Get a new board of size n by n.
   // Only allocates memory--values are not guaranteed.
   //
   // Precondition:  Board=NULL, or Board=ValidAddress
   // Postcondition: "this" is allocated memory for a board
   //    of size n by n.  No guarentees about entries, however.
   //    Any previously allocated memory is de-allocated.
   // Modifies:      BoardSize, Board

   void ClearBoard();         
   // Sets all squares to 'empty'.
   //
   // Precondition:  The board has been created.
   // Postcondition: All entries in the board are not empty.
   // Modifies:      Board

   void DisplayBoard();       
   // Displays the board.

   int PlaceQueens(int Column);
   // ------------------------------------------------------
   // Places queens in columns of the board beginning at the
   // column numbered Column.
   //
   // Precondition: Queens are placed correctly in columns 
   //    1 through Column-1.
   // Postcondition: If a solution is found, each column of 
   //    the board contains one queen, and it returns 1.
   //    otherwise, it returns 0.
   // Modifies:      Board
   // ------------------------------------------------------

private:

   enum square {empty,queen};  // The two types of squares.
   // NOTE: An enum in c++ allows you to delare a variable 
   // type that has values from the list.  It is REALLY an
   // int, but you can use it like any other variable type.
   // The above statement is just declaring a variable type
   // called square which can hold two different values--
   // "empty" or "queen".  The actual values stored in this
   // case are 0 and 1, but we can use the name empty and
   // queen instead.  The purpose is to make the code more
   // readable.
   // For instance, it is clear what is meant by 
   //     Board[i][j]=queen
   // But if I say
   //     Board[i][j]=1
   // What does that really mean?


   int BoardSize;              // The size of the board.
   square **Board;             // The board. 
   // NOTE:  We use a pointer to a pointer because we are 
   // going to use a dynamic 2-dimensional array.  Notice
   // that the type is square--the type of the enum defined
   // above.   The way we declare the dynamic memory with
   // this type is the same as if it was int or float, 
   // except we use the word square instead.

   void CopyBoard(const Queens &Q); 
   // Copies Q to the current object.
   // Used by the copy constructor and assign operator.
   //
   // Precondition:  Board=NULL, or Board=ValidAddress
   // Postcondition: "this" is a deep copy of Q.
   // Modifies:      BoardSize (maybe), Board

   void DeleteBoard();        
   // Deallocates the memory used for the board.
   //
   // Precondition:  Board=NULL, or Board=ValidAddress
   // Postcondition: All memory pointed to by Board is deleted.
   // Modifies:      BoardSize, Board

   void SetQueen(int Row, int Column);
   // Sets the square on the board in a given row and column
   // to QUEEN.

   void RemoveQueen(int Row, int Column);
   // Sets the square on the board in a given row and column 
   // to EMPTY.

   bool IsUnderAttack(int Row, int Column);
   // Determines whether the square on the board at a given 
   // row and column is under attack by any queens in the 
   // columns 1 through Column-1.
   // Precondition: Each column between 1 and Column-1 has a 
   // queen placed in a square at a specific row. None of 
   // these queens can be attacked by any other queen.
   // Postcondition: If the designated square is under 
   // attack, returns true; otherwise, returns false.
};