main.cpp

八皇后问题解法,包括DFS,BFS和INF三种解法

#include <string.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <list>
using namespace std;

//最多的皇后数目
#define MAX_BOARDSIZE 50

class Node
{
public:
	Node(int b)
	{
		boardsize = b;
		xpos = -1;
		ypos = -1;
		depth = 0;
		memset(board, 0, sizeof(board));
		parent = NULL;
		memset(child, 0, sizeof(child));
		childCount = 0;
		strategy = 0;
	}
	~Node()
	{
		for(int i = 0; i < childCount; ++i)
		{
			delete child[i];
			child[i] = NULL;
		}
		childCount = 0;
	}
	
	Node* insertNewChild(int x, int y)
	{
		Node* pchild = new Node(boardsize);
		pchild->xpos = x;
		pchild->ypos = y;
		pchild->depth = depth + 1;
		pchild->parent = this;

		int i, j;
		for(i = 0; i < boardsize; ++i)
		{
			for(j = 0; j < boardsize; ++j)
			{
				pchild->board[i][j] = board[i][j];
			}
		}

		for(i = 0; i < boardsize; ++i)
		{
			pchild->board[x][i] = '.';
			pchild->board[i][y] = '.';
			/*if((x-i) >= 0 && (y-i) >= 0)
			{
				pchild->board[x-i][y-i] = '.';
			}
			if((x-i) >=0 && (y+i) < boardsize)
			{
				pchild->board[x-i][y+i] = '.';
			}*/
			if((x+i) < boardsize && (y-i) >=0)
			{
				pchild->board[x+i][y-i] = '.';
			}			
			if((x+i) < boardsize && (y+i) < boardsize)
			{
				pchild->board[x+i][y+i] = '.';
			}			
		}
		pchild->board[x][y] = 'Q';

		for(i = 0; i < boardsize; ++i)
		{
			for(j = 0; j < boardsize; ++j)
			{
				if(pchild->board[i][j] == 0)
				{
					++pchild->strategy;
				}
			}
		}
		
		child[childCount++] = pchild;



		return pchild;
	}

	void printboard()
	{
		int i, j;
		for(i = 0; i < boardsize; ++i)
		{
			for(j = 0; j < boardsize; ++j)
			{
				printf("%c ", board[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}

	static int cmp(const void *pT1,const void *pT2)
	{
		Node** p1 = (Node**)pT1;
		Node** p2 = (Node**)pT2;
		if ((*p1)->strategy <  (*p2)->strategy) return -1;
		if ((*p1)->strategy == (*p2)->strategy) return  0;
		if ((*p1)->strategy >  (*p2)->strategy) return  1;

	}
public:
	char boardsize;
	char xpos;
	char ypos;
	char depth;
	char board[MAX_BOARDSIZE][MAX_BOARDSIZE];
	Node* parent;
	char childCount;
	Node* child[MAX_BOARDSIZE];
	int strategy;
};

enum SEARCH_METHOD
{
	DFS,
	BFS,
	INF,
};

class NQueen
{
public:
	static int solution;
	static Node* treeSearch(int boardsize, SEARCH_METHOD method, bool bPrint = false, bool bOne = false)
	{
		solution = 0;
		Node* root = new Node(boardsize);
		switch(method) 
		{
		case DFS:
			expandDFS(root, boardsize, bPrint, bOne);
			break;
		case BFS:
			expandBFS(root, boardsize, bPrint, bOne);
			break;
		case INF:
			expandINF(root, boardsize, bPrint, bOne);
			break;
		default:
			break;
		}

		return root;
	}

	static int expandDFS(Node* p, int boardsize, bool bPrint, bool bOne)
	{
		if(p->depth == boardsize)
		{
			++solution;
			if(bPrint)
			{
				p->printboard();
			}
			if(bOne)
			{
				return -1;
			}
			return 1;
		}

		for(int i = 0; i < boardsize; ++i)
		{
			//该点可用
			if(p->board[p->xpos+1][i] == 0)
			{
				Node* child = p->insertNewChild(p->xpos+1, i);
				if(expandDFS(child, boardsize, bPrint, bOne) < 0)
				{
					return -1;
				}
			}
		}

		return 1;
	}

	static int expandBFS(Node* p, int boardsize, bool bPrint, bool bOne)
	{
		list<Node*> array;
		array.push_back(p);
		
		while(!array.empty())
		{
			Node* tmp = array.front();
			array.pop_front();
			if(tmp->depth == boardsize)
			{
				++solution;
				if(bPrint)
				{
					tmp->printboard();
				}
				if(bOne)
				{
					return -1;
				}
			}
			else
			{
				int i;
				for(i = 0; i < boardsize; ++i)
				{
					//该点可用
					if(tmp->board[tmp->xpos+1][i] == 0)
					{
						Node* child = tmp->insertNewChild(tmp->xpos+1, i);
						array.push_back(child);
					}
				}
			}
		}


		return 1;
	}

	static int expandINF(Node* p, int boardsize, bool bPrint, bool bOne)
	{
		if(p->depth == boardsize)
		{
			++solution;
			if(bPrint)
			{
				p->printboard();
			}
			if(bOne)
			{
				return -1;
			}
			return 1;
		}
		int i;
		for(i = 0; i < boardsize; ++i)
		{
			//该点可用
			if(p->board[p->xpos+1][i] == 0)
			{
				Node* child = p->insertNewChild(p->xpos+1, i);
			}
		}
		
		//按照策略对子节点排序
		qsort(p->child, p->childCount, 4, (Node::cmp));


		for(i = 0; i < p->childCount; ++i)
		{
			if(expandINF(p->child[i], boardsize, bPrint, bOne) < 0)
			{
				return -1;
			}
		}
		
		return 1;
	}
};
int NQueen::solution = 0;

int main()
{

	int i;

	//task 1 使用DFS运行
/*
	for(i = 4; i <= 6; ++i)
	{
		printf("For board size %d, use the DFS method, the solution is\n", i );
		Node* r = NQueen::treeSearch(i, DFS, true);
		delete r;
		
	}

	for(i = 7; i <= 13; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, DFS);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the DFS method, There are totally %d solutions.\n", i, NQueen::solution);
		printf("Time used : %d ms.\n", end-start);
    }

	for(i = 7; i <= 13; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, DFS, false, true);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the DFS method, find one solutions.\n", i);
		printf("Time used : %d ms.\n", end-start);
    }

	//task 1 使用BFS运行
	for(i = 4; i <= 6; ++i)
	{
		printf("For board size %d, use the BFS method, the solution is\n", i );
		Node* r = NQueen::treeSearch(i, BFS, true);
		delete r;
		
	}

	for(i = 7; i <= 13; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, BFS);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the BFS method,There are totally %d solutions.\n", i, NQueen::solution);
		printf("Time used : %d ms.\n", end-start);
    }

	for(i = 7; i <= 13; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, BFS, false, true);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the BFS method, find one solutions.\n", i);
		printf("Time used : %d ms.\n", end-start);
    }
	
	//task 2 使用INF运行
	for(i = 4; i <= 6; ++i)
	{
		printf("For board size %d, use the INF method, the solution is\n", i );
		Node* r = NQueen::treeSearch(i, INF, true);
		delete r;
		
	}
	
	for(i = 7; i <= 13; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, INF);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the INF method, There are totally %d solutions.\n", i, NQueen::solution);
		printf("Time used : %d ms.\n", end-start);
    }
*/	
	for(i = 7; i <= 40; ++i)
	{
		long start = clock();
		Node* r = NQueen::treeSearch(i, INF, false, true);
		delete r;
		long end = clock();
		
		printf("For board size %d, use the INF method, find one solutions.\n", i);
		printf("Time used : %d ms.\n", end-start);
    }
	
	return 1;
}