最近在学一些算法相关的知识，学习之余准备动手写一点随笔记录学习过程。在加深理解的同时分享给大家，不足之处请各位多多指正。一个人能走得很快，但一群人能走得更远。
不多说，直接上代码。
核心代码部分
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;
}
