最近在学一些算法相关的知识，学习之余准备动手写一点随笔记录学习过程。在加深理解的同时分享给大家，不足之处请各位多多指正。一个人能走得很快，但一群人能走得更远。

不多说，直接上代码。

核心代码部分

void FindQueen(int row){
    if(row > 7){
        ans++;
        return;
    }

    for(int column = 0; column < 8; column ++)
        if(check(row,column)){
            arr[row] = column;
            FindQueen(row+1);
            arr[row] = -1;
        }
}

代码理解（重点）

首先，我放弃了使用二维数组来表示棋盘，而是选择了一个一维数组 arr[8] 。从而棋子的摆放可以用 arr[row] = column 来表示为：在第 row 行的第 column 列处摆放了棋子（行列皆从0开始计数）。全局数组 arr[8] 在初始化时，置所有值为-1。

当 row > 7 时，已经找到一解， ans计数并返回。当 row <= 7 时，也就是还没有找到正确解的情况下，我们用 for 循环搜索第row行的所有列。这时，就存在两种情况。

• 该行存在一个位置，且该位置上的棋子不会与之前摆放的棋子冲突
  这时，我们认为该行上的位置已经找到，修改 arr 数组，递归进入下一行。
• 改行不存在上述位置，即该行上所有位置都会与之前摆放的棋子产生冲突
  这时，函数会回退到上一次调用它的地方并继续执行剩下的语句，即执行 arr[row] = -1。该语句恢复环境，并指出我们刚刚在 (row,column) 处放的棋子已经不可能使后续要摆放的棋子满足条件。然后 for 循环执行 column++ ，在第 row 行继续找下一个可能的位置。

check函数

bool check(int row, int column){
    for(int i = 0; i < row; i++)
        if(arr[i] == column) return false;
    
    for(int i = 0; i < row; i++)
        if(abs(row-i) == abs(column - arr[i])) return false;

    return true;
}

因为代码是逐行进行递归的，因此不会产生行冲突（一维数组也保证了这一点）。第一个for循环检查(row,column)处是否与之前摆放的棋子产生列冲突，第二个for循环则检查两条对角线冲突。

完整代码

#include <iostream>
#include <cmath>
using namespace std;

int ans = 0;
int arr[8] = {-1};

bool check(int row, int column){
    for(int i = 0; i < row; i++)
        if(arr[i] == column) return false;
    
    for(int i = 0; i < row; i++)
        if(abs(row-i) == abs(column - arr[i])) return false;

    return true;
}

void FindQueen(int row){
    if(row > 7){
        ans++;
        return;
    }

    for(int column = 0; column < 8; column ++){
        if(check(row,column)){
            arr[row] = column;
            FindQueen(row+1);
            arr[row] = -1;
        }
    }
}

int main(void){
    FindQueen(0);
    cout << ans << endl;
    return 0;
}