八皇后问题，就是在8*8的棋盘上防止八个皇后，使他们不能互相攻击（横、竖、两个对角线都不能存在另一个棋子）。
八皇后问题的高效解法，可以维护一个左右对角线的数组，用于查找对角线是否有攻击的棋子。但是这种解法理解成本较高，不够直观。笔者一般采用维护一个二维数组用于模拟真实情况。
解法一：模拟二维数组，每次放置一个皇后前，遍历查找她的横、竖、对角线均不存在其他皇后。这种解法，代码非常简单易于理解。但是有一个小问题，即每次需要扫描位置的横、竖、对角线，平白无故会多扫描很多次。
bool eight_check(int iPos, int k, vector<vector<int>> &veBoard) { if (iPos >= 8 || k >= 8) return false; for (int i = 0; i < 8; ++i) { if (veBoard[i][k] == 1) return false; if (veBoard[iPos][i] == 1) return false; } int i = iPos; int j = k; while (i >= 0 && j >= 0) { if (veBoard[i--][j--] == 1) return false; } i = iPos; j = k; while (i >= 0 && j < 8) { if (veBoard[i--][j++] == 1) return false; } i = iPos; j = k; while (i < 8 && j >= 0) { if (veBoard[i++][j--] == 1) return false; } i = iPos; j = k; while (i < 8 && j < 8) { if (veBoard[i++][j++] == 1) return false; } return true; } int iTotalCountQueen = 0; void eight_queen(int iPos, vector<vector<int>> &veBoard) { if (iPos >= 8) { for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { cout << veBoard[i][j] << " "; } cout << endl; } cout << "-------------------------" << ++iTotalCountQueen << endl; return; } for (int i = 0; i < 8; ++i) { if (eight_check(iPos, i, veBoard)) { veBoard[iPos][i] = 1; eight_queen(iPos + 1, veBoard); veBoard[iPos][i] = 0; } } } void eight_queen() { std::vector<vector<int>> veBoard; veBoard.resize(8); for (int i = 0; i < 8; ++i) { veBoard[i].resize(8); } eight_queen(0, veBoard); }解法二：针对解法一，每个位置都需要扫描一遍横、竖、对角线带来的不必要遍历，可以针对性进行优化。将他们的先后顺序进行调整。开始时先扫描后放置，这次先放置，然后将放置位置的横、竖、对角线都进行标记，下次只需要判断某个格子是否存在值就可以。这样只需要在放置和回收的时候进行两次横、竖、对角线的标记与删除标记即可。
bool eight_check_two(int iPos, int k, vector<vector<int>> &veBoard) { if (iPos >= 8 || k >= 8) return false; return veBoard[iPos][k] == 0; } void eight_setval_two(int iPos, int k, vector<vector<int>> &veBoard, int iFlag) { for (int i = 0; i < 8; ++i) { veBoard[iPos][i] += iFlag; veBoard[i][k] += iFlag; } int i = iPos; int j = k; while (i >= 0 && j >= 0) veBoard[i--][j--] += iFlag; i = iPos; j = k; while (i >= 0 && j < 8) veBoard[i--][j++] += iFlag; i = iPos; j = k; while (i < 8 && j >= 0) veBoard[i++][j--] += iFlag; i = iPos; j = k; while (i < 8 && j < 8) veBoard[i++][j++] += iFlag; } void eight_queen_two(int iPos, vector<vector<int>> &veBoard) { if (iPos >= 8) { for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { cout << veBoard[i][j] << " "; } cout << endl; } cout << "two-------------------------" << ++iTotalCountQueen << endl; return; } for (int i = 0; i < 8; ++i) { if (eight_check_two(iPos, i, veBoard)) { eight_setval_two(iPos, i, veBoard, 1); eight_queen_two(iPos + 1, veBoard); eight_setval_two(iPos, i, veBoard, -1); } } } void eight_queen() { std::vector<vector<int>> veBoard; veBoard.resize(8); for (int i = 0; i < 8; ++i) { veBoard[i].resize(8); } eight_queen_two(0, veBoard); }这样效率比方法一高效一些些，但是却不方便查看。再拿一个数组用于保存结果就可以了
bool eight_check_two(int iPos, int k, vector<vector<int>> &veBoard) { if (iPos >= 8 || k >= 8) return false; return veBoard[iPos][k] == 0; } void eight_setval_two(int iPos, int k, vector<vector<int>> &veBoard, int iFlag) { for (int i = 0; i < 8; ++i) { veBoard[iPos][i] += iFlag; veBoard[i][k] += iFlag; } int i = iPos; int j = k; while (i >= 0 && j >= 0) veBoard[i--][j--] += iFlag; i = iPos; j = k; while (i >= 0 && j < 8) veBoard[i--][j++] += iFlag; i = iPos; j = k; while (i < 8 && j >= 0) veBoard[i++][j--] += iFlag; i = iPos; j = k; while (i < 8 && j < 8) veBoard[i++][j++] += iFlag; } std::vector<int> veEnd; void eight_queen_two(int iPos, vector<vector<int>> &veBoard) { if (iPos >= 8) { /*for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { cout << veBoard[i][j] << " "; } cout << endl; }*/ //for (auto &it : veEnd) cout << it << " "; cout << "two-------------------------" << ++iTotalCountQueen << endl; return; } for (int i = 0; i < 8; ++i) { if (eight_check_two(iPos, i, veBoard)) { eight_setval_two(iPos, i, veBoard, 1); veEnd.push_back(i); eight_queen_two(iPos + 1, veBoard); veEnd.pop_back(); eight_setval_two(iPos, i, veBoard, -1); } } } void eight_queen() { std::vector<vector<int>> veBoard; veBoard.resize(8); for (int i = 0; i < 8; ++i) { veBoard[i].resize(8); } //eight_queen(0, veBoard); eight_queen_two(0, veBoard); }效率并不是最高的解法，但是确实是相当容易理解的写法。
