main.cpp

搜索8皇后问题的第一个解。使用了两种方法：1.普通的回朔法搜索。 2.修改后的搜索（先搜索most contrainted变量的方法) 使用vc++.net 2003开发

// The program for 8 Queens Problem.
// Shen Hongwei, 2006.04.03, created it
// Shen Hongwei, 2006.04.07, corrected the error of searching duplicate states.

#include <stdio.h>
#include <conio.h>
#include <memory.h>

#define WIDTH 64  // the width of the chessboard 

#undef NAIVE_SEARCH  // NAIVE_SEARCH should be defined if you want to search next column instead of the column with fewest unattacked squares
//#define NAIVE_SEARCH

int count = 0;   // global variable, the number of expanded nodes. 

struct State
{
	int num;    // the num of queens in the state
	int Queens[WIDTH];  // if Queens[i]==-1, no queen is in the ith column, else a queen is in col i, row Queens[i].
};

// refresh board status (invoked after a new queen is put onto the chessboard)
void RefreshStatus(bool status[], int col, int row)
{
	for (int i=0; i<WIDTH; i++) // modify status of squares in same column and same row
	{
		status[col*WIDTH+i] = false;
		status[i*WIDTH+row] = false;
	}

	// the following 4 for statements modify status of squares in diagonals

	for (int i=col, j=row; i>=0 && j>=0 ; i--,j--) 
		status[i*WIDTH+j] = false;

	for (int i=col, j=row; i<WIDTH && j>=0 ; i++,j--)
		status[i*WIDTH+j] = false;

	for (int i=col, j=row; i>=0 && j<WIDTH ; i--,j++)
		status[i*WIDTH+j] = false;

	for (int i=col, j=row; i<WIDTH && j<WIDTH ; i++,j++)
		status[i*WIDTH+j] = false;
}

// for debug
void PrintState(struct State state)
{
	printf("%d queens ", state.num);
	for(int i=0;i < WIDTH; i++)
		printf("%d,", state.Queens[i]);

	printf("\n");
}


// Recursive function
// Do search from given state and board status
bool Search(struct State state, bool boardStatus[])
{
	int  freeNum[WIDTH];  // freeNum[i] is the number of unattacked squares in column i

	// Calculate how many unattacked squares in each column 
	// and find out the 1st col which has fewest (but more than 0) unattacked squares
#ifdef NAIVE_SEARCH 
	int iMin = state.num;
#else
	int iMin = -1;
	int nMin = WIDTH+1;
	for (int i=0; i < WIDTH; i++) {
		freeNum[i] = 0;
		if (state.Queens[i] != -1)   // if one column with no queen in it has no unattacked squares, stop search toward this path.  shw, 2006.04.06
			continue;
		for (int j=0; j < WIDTH; j++)
			if (boardStatus[i*WIDTH+j])
				freeNum[i]++;

		if (freeNum[i] < nMin) {
			iMin = i;
			nMin = freeNum[i];
		}
	}

	if (nMin<1)   // if there is one column with no unattacked squares in it, stop searching in this branch.
		return false;
#endif

	for (int j=0; j<WIDTH; j++) {
		if (boardStatus[iMin*WIDTH+j])	{
			// before modifying status and state, duplicate them
			bool newStatus[WIDTH*WIDTH];
			struct State newState = state;
			memcpy(newStatus, boardStatus, sizeof(newStatus));
			newState.num++;
			newState.Queens[iMin] = j;
			RefreshStatus(newStatus, iMin, j);
			count++;  // a new search node is being searched.
			// PrintState(newState);  // for debug

			if (newState.num == WIDTH) {
				// output the solution
				for (int k=0; k<WIDTH; k++)
					printf("col %d,row %d\n", k,newState.Queens[k]);
				return true;
			} else {
				if (Search(newState, newStatus) == true)  // recursive invoking
					return true;
			}
		} // end of if
	} // end of for (int j...

	return false;
}

main()
{
	struct State state; 
	bool boardStatus[WIDTH*WIDTH];  // boardStatus[i*WIDTH+j] indicates if the square in col i,row j is unattcked.

	// initialization
	state.num=0;
	for (int i=0; i<WIDTH; i++)
		state.Queens[i] = -1;

	for (int i=0; i<WIDTH*WIDTH; i++)
		boardStatus[i] = true;
   
	// invoke Search function
	if (Search(state, boardStatus))  
		printf("The first solution is found after %d nodes expanded. \n", count);
	else
		printf("No solution is found after %d nodes expanded. \n", count);

	printf("Press any key to exit.\n");
	getch();
}