回溯法解决8皇后问题(C++实现)

在8×8的棋盘中，同一行，同一列。同一斜线上只能有一个“皇后”棋子

#include<iostream>
using namespace std;
#define MAX 8
int queue[8], sum = 0;

void output()
{
	for (int i = 0; i<MAX; i++)
	{
		cout << queue[i] + 1<< ' ';
	}
	cout << endl;
	sum++;
}

int check(int n)
{
	for (int i = 0; i<n; i++)
	{
		if (queue[i] == queue[n] ||
			queue[i] - queue[n] == n - i || 
			queue[n] - queue[i] == n - i)		 //判断斜率
			return 1;
	}
	return 0;
}
void DFS(int n)
{
	for (int i = 0; i<MAX; i++)
	{
		queue[n] = i;	
		if (!check(n))	//如果没有发生冲突
		{
			if (n == MAX - 1)
			{
				cout << "排列方法之一：";
				output();
			}
			else
				DFS(n + 1);	//递归
		}
	}
}

int main()
{
	DFS(0);
	cout <<"共有"<< sum <<"种方法"<< endl;
	system("pause");
	return 0;
}