// 8q.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include 

// let's define all the following as global 

#define number_of_queens 8 
// try 4 quuens to check the soultion first, then try 8 queens
static solution[number_of_queens];  
// the solution show the position of queens in each row.
int row;				
 // the indicator to each row, or each queen
int column;				 
// the indicator to each column, or queen's position
static int n;	  		 
// the solution counter

int validposition();	 
// check to see if the position is available, 1= available, 0 = NA
void report();			 
// generate one of the solutions

// declare the "report.dat" as the output file for the solutions
ofstream outReport( "report.dat", ios::out);

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// This program tries to place 8 queens on an 8 by 8 matrix such that 
// there is one and only one queen on the same column, the same row, 
// or the same diagonal in the matrix. The algorithm proceeds row by row 
// for each queen, and starts from column 0,1,2,..7 For each position, 
//if it is a valid position, place queen (row) on position (column), and
// move on to the next queen. Once queen 7 is positioned, a set of 
// solution is found. Report. If the position is not valid, move on to 
// the next column. If the column is more than 7,  back track to previous 
//row, and move queen to next column. If it backs track beyond row 0,
// then there is no more solutions to this problem, stop.
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int main(int argc, char* argv[])
{	
	outReport << "\nAll the solutions of the 8 queens problem\n";
	row=0; // start with the first row
	for(;;) // loop forever
	{
		column = 0; // start with first column

		// find a position (column) for the queen (row)
		for(;;)
		{
			if( validposition() == 1 )
			{
				solution[row] = column;
				row++; // go to next row
				break;
			}
			else
			{
				column++; // move to next column
				while(column == number_of_queens) 
// can not find an available position, so backtrack
				{
					row--;
					if(row < 0)  
// backtrack beyond first row, nor more solutions
					{
					outReport << "\n*** END ***\n";
					return 1; // done !!
				        }
				column = solution[row] + ; 
//backtrack to the next column of previous row
				}
			}
		}

		if(row == number_of_queens ) 
// we have obtain one set of solution, report 
		{
			outReport << "\n" << n++ << " : \t";
			report();
		}
	}
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// This function validate the current position "column" for the 
// current queen "row"
// It return 0 if the position is not valid, 
//    return 1 if it is a valid position (available to place a queen.
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int validposition()
{

	int i;
	int leftdiagcolumn;
	int rightdiagcolumn;

	for(i=0;i= number_of_queens) continue; 
// ignore if it is out of table
		if(solution[i] == rightdiagcolumn) return 0; 
// occupied, conflict
	}

	// no conflict, it is valid position
	return 1;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// generate a set of solution, these numbers represent the position for 
//each queen
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void report()
{
	int i;
	for(i=0;i < number_of_queens;i++)
	{
		outReport << solution[i] <<"\t";
	}
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ The End