// File: 8Queens.cpp
// Appropriated from URL: http://www.cjhon.com/c++/8queens.cpp
//
//	PROJECT: 8 Queens
//	AUTHOR: Jimmy Hon
//	DATE: 	November 11, 2001
//
//	Project can be located at http://vjhon.ne.mediaone.net/c++
//

// Pre-Processor Directives
#include <iostream>
#include "apmatrix.h"
#include <fstream.h>
using namespace std;
// Constant,Variable, and Type Declarations
 ofstream outFile("e:\\8queens.txt");

// Function Prototypes
void PlaceQueen (apmatrix<bool> &board, int &solutions, int col);
bool CheckSpace (const apmatrix<bool> &board, const int row, const int col);
void PrintBoard(const apmatrix<bool> &board);

// Main Function
void main()
{
	apmatrix<bool> board(8,8,false);	//board with no queens on it
	int solutions=0;			//found no solutions so far

	PlaceQueen(board,solutions,0);
	return;
}

// Functions
void PlaceQueen (apmatrix<bool> &board, int &solutions,int col)
{
	for (int row=0; row<=7; row++)
	  if (CheckSpace(board,row,col))  //If that space is not under attack...
	    { board[row][col]=true;   //Puts a queen on the space
	      if (col==7)		
	          { //If a queen is placed in the last column
	            //Output solution number...
		    outFile << ++solutions << ". "<< endl; 
		    PrintBoard(board);	//then output the board
		  }
	      else //If not last column, go on to next column
                  PlaceQueen(board, solutions, col+1);
                  //Take the queen off the space; continue like it didn't work
	      board[row][col]=false;	
	    }
}









bool CheckSpace (const apmatrix<bool> &board,const int row, const int col)
{
	int r,c;
	for (r=row, c=col; r>=0 && c>=0;r--,c--)
		if (board[r][c])
			return false;	//queen attacking space from upper left

	for (c=col; c>=0; c--)
		if (board[row][c])
			return false;	//queen attacking space from same row
	

	for (r=row, c=col; r<=7 && c>=0; r++, c--)
		if (board[r][c])
			return false;	//queen attacking space from lower left

	return true;	//space is not under attack
}
		
void PrintBoard(const apmatrix<bool> &board)
{
	outFile << "  |---|---|---|---|---|---|---|---|" << endl;
	for (int r=0;r<=7;r++)
	{	
		outFile << 8-r <<" |";		//outputs row number 1-8
		for (int c=0;c<=7;c++)
		{
			if (board[r][c]) outFile << " Q |";
			else outFile << "   |";
		}
		outFile <<endl << "  |---|---|---|---|---|---|---|---|" << endl;
	}

	outFile << "    ";
	for (int i='A'; i<='H'; i++)
		outFile << char(i) << "   ";	//outputs row letter A-H
	outFile << endl;
}