八皇后问题

八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯 算法的典型案例。

问题描述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

回溯法

回溯法的处理思想类似于枚举搜索，我们枚举出每一种情况，然后在根据条件进行筛选，找到满足期望的值。我们把求解过程分为多个阶段，每个阶段我们都会面临一个十字路口，我们随便找一条路，走不通后，就回到上一个十字路口，选择另一个十字路口进行下一步，知道遍历完整个枚举情况。

回溯法的模板

在面临较简单的回溯问题是可以使用以下模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
 
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

算法思路： 用回溯法求解4皇后问题，算法尝试生成并以深度优先方式搜索一棵完全四叉有根树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置的情况，依次类推。

求解这个问题的回溯算法如算法4-QUEENS 在算法中，我们用术语“合法”来表示一个不互相攻击的4个皇后的放置，用术语“部分”来表示一个不互相攻击的少于4个皇后的放置。显而易见，放在位置xi和xj的两个皇后当且仅当xi = xj 时处在同一列上，不难看出两个皇后处在同一条对角线上当且仅当 xi –xj =i - j 或 xi –xj = j - i

回溯算法是一种递归的算法，用于解决组合问题或搜索问题。在解决八皇后问题时，我们可以使用回溯算法来尝试所有可能的放置方式，并在每一步中检查是否符合条件。如果当前放置的皇后导致冲突，我们就会回溯到上一步，尝试其他的放置方式。

具体来说，回溯算法在解决八皇后问题时的步骤如下：

1. 从第一行开始，逐行放置皇后。在每一行中，逐个尝试每一列，找到一个可以放置皇后的位置。
2. 检查当前位置是否与已经放置的皇后冲突。如果没有冲突，则继续递归地放置下一行的皇后。
3. 如果无法找到符合条件的位置，回溯到上一行，尝试其他的放置方式。
4. 当放置完最后一行的皇后时，找到一个解决方案，将其打印出来或以其他方式展示。
5. 继续尝试其他可能的解决方案，直到找到所有的解决方案。

通过回溯算法，我们可以找到所有可能的解决方案，解决八皇后问题。这种方法虽然简单，但是在实践中非常有效，可以帮助我们更好地理解回溯算法的应用和原理。 参考代码

#include<iostream>
using namespace std;
/*
问题描述：
       八皇后问题
*/
void print(bool array[][8] ,int count) {
    cout << "***********  "<<" 第 "<<count<<" 种解"<<"  ******************"<<endl;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
}
bool noDanger(bool array[][8], int row, int column) {
    if (0 == row) return true;  //第 0 行直接放置成功

    int i = row - 1, j = column;    //判断当前列是否存在皇后
    for (i; i >= 0; i--) {
        if (array[i][j] == true) return false;
    }

    i = row - 1; j = column - 1;
    for (; i >= 0 && j >= 0; i--, j--) {    //判断左上斜对角线是否存在皇后
        if (array[i][j] == true) return false;
    }

    i = row - 1; j = column + 1;
    for (; i >= 0 && j < 8; i--, j++) { //判断右上斜对角线是否存在皇后
        if (array[i][j] == true) return false;
    }

    return true;
}
void eightQueens(bool array[][8] ,int row, int &count) {
    
    for (int j = 0; j < 8; j++) {   //遍历每一列
        array[row][j] = true;       //在当前位置 放置皇后
        if (noDanger(array, row, j)) {  //判断皇后是否冲突
            if (7 == row) {         //若已放置到最后一行，输出当前的一个解
                count++;
                print(array,count);
            }
            else
            {
                eightQueens(array, row + 1,count);  //若未放置到最后一行，继续往下一行寻找
            }

        }
        array[row][j] = false;  
    }
}
int main() {
    bool array[8][8];       //维护一个二维矩阵 ，true代表该位置有皇后，false代表无
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            array[i][j] = false;        //初始化为 false
        }
    }
    int count = 0;  //解的总数
    eightQueens(array, 0,count);
    return 0;
}

深搜解法

#include<bits/stdc++.h>
using namespace std;
int n;
int a[15];//
int col[15];//列 
int zdjx[30];//正对角线 
int ndjx[30];//逆对角线 
int cnt;
//DFS基本结构 
void dfs (int step){
	//放入棋子 
	if(step==n)
	{
		cnt++;
		//只求前3行的解 
		if(cnt<=3){
			for(int i=0;i<n;i++)
			{
				cout<<a[i]+1<<" ";
			}
			cout<<"\n"; 
		} 
	}
	// 按列放置 
	for (int i=0;i<n;i++)
	{
		//当前列上没有棋子时，才可以放棋子 
		if(!(col[i]||zdjx[i-step+n]||ndjx[i+step])){
			a[step]=i;
			//列=1时，表示放置了棋子 
			col[i]=1;
			zdjx[i-step+n]=1;
			ndjx[step+i]=1;
			//放下一行 
			dfs(step+1);
			//恢复状态 
			col[i]=0;
			zdjx[i-step+n]=0;
			ndjx[step+i]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(0);
	cout<<cnt<<endl;
	return 0;
}