// File: queen-verbose.cpp
// same as queen.cpp, but with lots more output

//	eight queens puzzle in C++
//	written by Tim  Budd, Oregon State University, 1996
//

//      this "verbose" version traces the queen interactions
//      [Jerry Roth, Gonzaga University, Feb. 2000]

# include <iostream.h>
# define bool int // not all compilers yet support booleans

class queen {
public:
		// constructor
	queen (int, queen *);
	
		// find and print solutions
	bool findSolution();
	bool advance();
	void print();

private:
		// data fields
	int row;
	const int column;
	queen * neighbor;
	
		// internal method
	bool canAttack (int, int);
	void indent();
};

queen::queen(int col, queen * ngh)
	: column(col), neighbor(ngh)
{
	row = 1;
	indent();
	cout << "Queen " << column << " constructed." << endl;
}

bool queen::canAttack (int testRow, int testColumn)
{
		// test rows
	if (row == testRow)
	{
		indent();
		cout << "Queen " << column << " can attack position "
			 << testColumn << "," << testRow << endl;
		return true;
	}
		
		// test diagonals
	int columnDifference = testColumn - column;
	if ((row + columnDifference == testRow) ||
		(row - columnDifference == testRow))
	{
		indent();
		cout << "Queen " << column << " can attack position "
			 << testColumn << "," << testRow << endl;
		return true;
	}
			
		// try neighbor
	return neighbor && neighbor->canAttack(testRow, testColumn);
}

bool queen::findSolution()
{
	// test position against neighbors

        // The while loop is not necessary since advance() always
        // moves the queen to the next "safe" position.
        // [Jerry Roth, Gonzaga University, Feb. 2000]

	//while (neighbor && neighbor->canAttack (row, column)) 
	if (neighbor && neighbor->canAttack (row, column)) 
		if (! advance())
			return false;
			
			// found a solution
	indent();
	cout << "Queen " << column << " is currently safe." << endl;
	return true;
}

bool queen::advance()
{
	if (row < 8) {
		indent();
		cout << "Queen " << column << " is advancing to next row." << endl;
		row++;
		return findSolution();
		}
		
	indent();
	cout << "Queen " << column << " is out of rows." << endl;

	if (neighbor && ! neighbor->advance())
		return false;
		
	indent();
	cout << "Queen " << column << " is starting back at row 1." << endl;

	row = 1;
	return findSolution();
}

void queen::print()
{
	if (neighbor)
		neighbor->print();
	cout << "column " << column << " row " << row << '\n';
}

void queen::indent()
{
	int i;
	for (i=1; i<=column; i++) {
		cout << "  ";
	}
}

int main() {
	queen * lastQueen = 0;
	
	for (int i = 1; i <= 8; i++) {
		lastQueen = new queen(i, lastQueen);
		if (! lastQueen->findSolution())
			cout << "no solution\n";
		}
		
	lastQueen->print();
}