回溯法经典—n-皇后问题
n-皇后问题是回溯法中经典中的经典，其基本问题描述是:在一个nxn的格子中放n个皇后，使得每个皇后不能相互攻击，任意两个皇后能够互相攻击的条件是他们在同一条对角线或者同一行或者同一列上
问题可以转换为从第0行开始放置皇后一直放到n-1行，使得每一行在放置皇后的同时，不能与前面的皇后相互攻击
即列，对角线不冲突即可(行肯定不冲突)
伪代码描述
所以，我们可以用一个3x(2n)的数组来标志对应的列，主对角线，副对角线上是否已经有皇后
vis[0][index] = 1标示第index列上已经有皇后
vis[1][index] = 1标示第index条主对角线上已经有皇后
vis[2][index] = 1标示第index条副对角线上已经有了皇后
那么我们简单推理一下格子(x, y)使得
vis[0][y] = 1
vis[1][y-x+n] = 1 //为防止出现负数下标，所以每一个对应的编号加上n
vis[1][y+x] = 1
最后，我们用c++代码来实现
#include <iostream>using namespace std;int n = 4;int v[2][8];int c[4];void search(int cur) { if (cur == n) { for (int i = 0; i < n; i++){ cout << " "; for (int j = 0; j < n; j++) if (j == c[i]) cout << "Q "; else cout << "* "; cout << endl; } cout << endl; } else { for (int j = 0; j < n; j++) { if (!v[0][j] && !v[1][j-cur+n] && !v[2][cur+j]) { c[cur] = j; v[0][j] = v[1][j-cur+n] = v[2][cur+j] = 1; search(cur+1); v[0][j] = v[1][j-cur+n] = v[2][cur+j] = 0; } } }}int main() { search(0); return 0;}
