八皇后问题的解法

使用了回溯算法。八皇后问题是一个经典的递归问题，在一个8x8的棋盘上放置8个皇后，要求任意两个皇后不能位于同一行、同一列或同一对角线上。

首先，定义了4个数组a、b、c和d，用来存储皇后的位置信息。数组a表示每行皇后的列数，数组b表示每列是否已经有皇后，数组c和d分别表示两个方向的对角线是否已经有皇后。

然后，定义了总计数器total和皇后数量n，并且实现了打印函数print()，用来输出满足条件的解。

接下来是主函数main()，其中首先输入皇后的数量n，然后调用queen(1)函数，开始遍历棋盘上的每一行。在queen函数中，通过循环遍历每一列，判断该位置是否可以放置皇后。如果可以放置，则记录该位置并继续递归调用queen函数，以放置下一行的皇后。当递归到达第n+1行时，表示找到了一个满足条件的解，调用print函数进行输出。

最后输出结果total，即所有满足条件的解的个数。

该算法使用了回溯的思想，在搜索过程中剪枝，减少了不必要的搜索空间，从而提高了效率

#include<iostream>
using namespace std;

int a[100], b[100], c[100], d[100];
int total;
int n;

void print() {
    if (total <= 2) {
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    total++;
}

void queen(int i) {
    if (i > n) {
        print();
        return;
    }
    
    for (int j = 1; j <= n; j++) {
        if (!b[j] && !c[i+j] && !d[i-j+n]) {
            a[i] = j;
            b[j] = 1;
            c[i+j] = 1;
            d[i-j+n] = 1;
            queen(i+1);
            b[j] = 0;
            c[i+j] = 0;
            d[i-j+n] = 0;
        }
    }
}

int main() {    
    cin >> n;
    queen(1);
    cout << total;
    return 0;
}

本文将详细介绍dfs的的应用。

前置芝士

深度优先搜索（dfs）：

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search。

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 举例说明：下图是一个无向图：

如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是 $B$ 也可以是 $C,D$ ），则我们可能得到如下的一个访问过程： $A\to B \to E$ （没有路了！回溯到 $A$ ) $\to C \to F \to H \to G \to D$ （没有路，最终回溯到 $A$ , $A$ 也没有未访问的相邻节点，本次搜索结束）。简要说明深度优先搜索的特点：每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序（具体做法是创建一个list，然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表)，则我们可以得到所谓的"拓扑排序",即topological sort。 ——百度百科

思路分析

过程

我们用一个 $y$ 数组来标记当前这一列有没有被标记（即这一列有没有皇后存在）， $xie1$ 数组来标记 / 这样子方向的对角线有没有皇后， $xie2$ 数组来标记 \ 这样子方向的对角线有没有皇后。

问题来了，列我们好标，但对角线却不好标。

我们先来看 $xie1$ 数组：

看来我们只能找规侓了。

首先先看第一组： $(1,1)$ 、 $(2,2)$ 、 $(3,3)$ 、 $(4,4)$ 、 $(5,5)$ 、 $(6,6)$ 。他们的和不一样，不好找规律，这是我们就不要局限于只看和了，我们看一下差，都是 $0$ ！我们来看一下第二组： $(4,1)$ 、 $(5,2)$ 、 $(6,3)$ ，他们的差是 $2$ ！我们发现，每个对角线中的点的 $x,y$ 坐标的 $y-x$ 都是一样且独一无二的！这就是 $xie1$ 数组的规律。

这是有个问题， $y-x$ 有可能是负数，这是我们只需加 $n$ 就好了（变成 $y-x+n$ ）。

我们先来看 $xie2$ 数组： 我们画几组样例就会发现它的规律是 $x+y$ 。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],cnt;
bool y[1000001],xie1[10000001],xie2[100000001];
void dfs(int hang,int dep)
{
	if(dep==n+1)
	{
		if(cnt>=3)
		{
			cnt++;
			return;
		}
		cnt++;
		for(int i=1;i<=n;i++)   //a数组存答案
			cout<<a[i]<<' ';
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!y[i] && !xie1[i-hang+n] && !xie2[i+hang])
		{
			y[i]=1;
			xie1[i-hang+n]=1;
			xie2[i+hang]=1;
			a[dep]=i;
			dfs(hang+1,dep+1);
			y[i]=0;
			xie1[i-hang+n]=0;
			xie2[i+hang]=0;
			a[dep]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(1,1);
	cout<<cnt;
	return 0;
}

显然，这个题要用DFS 但是，这个题真的必须用DFS吗？👀️ 6 <= n <=13 ∴让人不由自主地想到：打表 于是此蒟蒻开始：

if(n==6) //打表进行中......
{
puts("2 4 6 1 3 5");
puts("3 6 2 5 1 4");
puts("4 1 5 2 6 3");
puts("4");
}
if(n==7)
{
puts("1 3 5 7 2 4 6");
puts("1 4 7 3 6 2 5");
puts("1 5 2 6 3 7 4");
puts("40");
}
if(n==8)
{
puts("1 5 8 6 3 7 2 4");
puts("1 6 8 3 7 4 2 5");
puts("1 7 4 6 8 2 5 3");
puts("92");
}
if(n==9)
{
puts("1 3 6 8 2 4 9 7 5");
puts("1 3 7 2 8 5 9 4 6");
puts("1 3 8 6 9 2 5 7 4");
puts("352");
}
if(n==10)
{
puts("1 3 6 8 10 5 9 2 4 7");
puts("1 3 6 9 7 10 4 2 5 8");
puts("1 3 6 9 7 10 4 2 8 5");
puts("724");
}
if(n==11)
{
puts("1 3 5 7 9 11 2 4 6 8 10");
puts("1 3 6 9 2 8 11 4 7 5 10");
puts("1 3 7 9 4 2 10 6 11 5 8");
puts("2680");
}
if(n==12)
{
puts("1 3 5 8 10 12 6 11 2 7 9 4");
puts("1 3 5 10 8 11 2 12 6 9 7 4");
puts("1 3 5 10 8 11 2 12 7 9 4 6");
puts("14200");
}
if(n==13)
{
puts("1 3 5 2 9 12 10 13 4 6 8 11 7");
puts("1 3 5 7 9 11 13 2 4 6 8 10 12");
puts("1 3 5 7 12 10 13 6 4 2 8 11 9");
puts("73712");
}
return 0;
}

已AC，我是蒟蒻

/*
	这道题的关键就在于对角线的处理，
	我采用的方法是：
	观察发现: 
	  如果两枚棋子在对角线或是在对角线
	  的平行线上时，行数之差的绝对值与
	  列数之差的绝对值相等 
	所以我便编写了check函数来控制
	对角线的处理 
	vis数组的作用是控制列数不相同
	cnt代表目前是在第几行 
*/
#include <bits/stdc++.h>
using namespace std;
int n,l[15],ans;//l数组存答案，ans表示个数 
bool vis[15];
void dfs(int cnt);/*如果写在前面会头重脚轻
破坏美感 */ 
bool check(int x,int cnt)
{
	for (int i = 1;i < cnt;i++)
	{
		if (abs(cnt - i) == abs(x - l[i]))
		{
			return 0;
		}
	}
	return 1;
}/*但为了不太脚重头轻，我把check函数写在了前面
这样就舒服了*/ 
int main()
{
	cin >> n;
	dfs(1);
	cout << ans;
	return 0;
}
void dfs(int cnt)
{
	if (cnt == n+1)
	{
		ans++;//这一句须写在if前面，先算个数再判断 
		if (ans <= 3)
		{
			for (int i = 1;i <= n;i++)
			{
				cout << l[i] << " ";
			}
			cout << "\n";
		}
		return;/*这里我刚开始忘写了，
		但居然AC了！！！ 
		让我非常疑惑*/ 
	}
	for (int i = 1;i <= n;i++)
	{
		if (!vis[i])//列 
		{
			if (check(i,cnt))//对角线 
			{
				l[cnt] = i;
				vis[i] = 1;
				dfs(cnt+1);
				vis[i] = 0; 
			}
		}
	}
}/*已AC，请谨慎使用，
别忘点赞***********************************！！！！！！！！！！！！！！！*/