八皇后问题详解

八皇后问题详解

今天的八皇后也是递归训练的一个小环节。废话不多说，
首先我们获取题目的信息：

在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。例如：

现在我们把棋盘扩展到 n×n 的棋盘上摆放 n 个皇后，请问该怎么摆？

请编写程序，输入正整数 n，输出全部摆法（棋盘格子空白处显示句点“.”，皇后处显示字母“Q”，每两个字符之间空一格）。

输入格式：

正整数 n(n>0)

输出格式：

若问题有解，则输出全部摆法（每两种摆法之间空一行）。
若问题无解，则输出 None。

输入样例1：

3

输出样例1：

None

输入样例2：

6

输出样例2：

. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .

. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .

. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .

下面就直接上代码了，我会在代码后面反复注释，尽量让读者理解进去

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
char ch[N][N];//用一个二维数组来存储皇后放置的位置
bool col[N], l[N << 1], r[N << 1];//为了数组不会越界，就把N乘2了,涉及位运算了
bool mark;//设置一个变量，判断是否有解（有解输出排法，无解输出None）
int n;

//这个dfs是按行逐渐进行下去的，初始值为0行
void dfs(int x) 
{
    //如果x能够来到从初始值0来到n的位置就说明有一个解已经产生
    if (x == n) {
        /*
        加这个判断实属必要，当第一个解产生的时候，此时mark还是初始值false(0),
        所以把mark进入判断的第二个作用域，赋值为true(1),如果还有第二个解，
        此时的mark已经为true，所以输出换行，看到这里是不是有些明白了，对，没错！
        这个判断就是为了“解”与“解”之间能有个换行符而存在的！
        */
        if (mark)
        {
            cout << endl;
        }
        else 
        {
            mark = 1;
        }
        //下面就是遍历这个“解”了
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                cout << ch[i][j];
                if(j!=n-1)
                {
                     cout<<' ';//处理字符与字符之间的空格
                 }
            }
            putchar(10);//输出一行后需要换行，换行的ASCII数为10
        }
        return;//当这个“解”遍历完的时候，可以安排它消亡了
    }
    
    //下面代码是这个题的核心，请务必！务必！务必！要不择一切手段也要弄懂
    
    /*
    要明白下面的for循环的意思，记住是x代表行数，下面的 i 代表的是x行 i 列,
    如果不明白，请反复看，已经是 保姆式 教学了，
    */
    for (int i = 0; i < n; i++) 
    {
        //下面的判断是核心中核心:
        //第一个判断col[i]是判断i列能不能放，col[i]=1,说明不能放（因为下面的判断是！col[i]）
        //第二个判断l[x + i]是判断主对角线能不能放，
        //第三个判断r[n - x + i]是判断副对角线能不能放，
        //第二第三个如果不能理解，建议直接强记模板！
        if (!col[i] && !l[x + i] && !r[n - x + i]) 
        {
            col[i] = l[x + i] = r[n - x + i] = 1;//如果能放，对状态进行标记
            ch[x][i] = 'Q';
            dfs(x + 1);//第一行结束，对下一行进行判断,都 x+1了，你说是不是下一行
            
            //对该坐标进行归“零”处理
            ch[x][i] = '.';
            col[i] = l[x + i] = r[n - x + i] = 0;
        }
    }
}
int main() {
    //这个就是对数组进行初始化处理，如果不知道的建议搜  memset()详解
    memset(ch, '.', sizeof(ch));//初始化地图数组,这个函数在cstring这个头文件下面
    cin >> n;
    dfs(0);//这个就没得说了，从第一行开始遍历，0就是第一行。
    //无解就输出  None  咯！
    if (!mark)
    {
        cout << "None";
    }
    return 0;
}

八皇后题解如上，如看不懂，那就反复的看吧，这涉及到了递归的知识，借用一句话：“ 要理解递归，你要先理解递归，直到你理解递归”。
今天八皇后有点难，反复的敲一下，总有好处，读书也是这样：“书读百遍，其义自见！”（保姆式教学）