八皇后问题（简单回溯）算法

随心而记，以供追忆
1，问题描述：八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
2，解决方式：由于本问题只有八皇后摆放，故可以使用穷举的思想，一一判断，此次采用回溯算法解决，且使用C++完成。
3，问题分析：
单元格内思想如下图所示

文章图片

回溯思想如下图所示

【八皇后问题（简单回溯）】

文章图片

以下为回溯算法代码（根据需求，故可不对皇后摆放的各种样式都储存进入本地，只使用一个8*8的二维数组进行操作）

void Queen(int i) { if (i>= N) display(Q); else for (int j = 0; j <= N-1; ++j){ Q[i][j] = 1; if (judgement(Q, i, j))//如果符合条件，保存下来 Queen(i + 1); Q[i][j] = 0; } }

以下为全部代码：

#include "stdafx.h" #include #define N 8 using namespace std; bool judgement(int Queen[][N], int i, int j); void display(int Queen[][N]); void Queen(int m); int Q[N][N] = { 0 }; int cout_num = 0; int main() { int m = 0; Queen(m); return 0; }void Queen(int i) { if (i>= N) display(Q); else for (int j = 0; j <= N-1; ++j){ Q[i][j] = 1; if (judgement(Q, i, j))//如果符合条件，保存下来 Queen(i + 1); Q[i][j] = 0; } }void display(int Queen[][N]) { cout_num++; cout << cout_num << " is :" << endl; for (int i = 0; i <= N-1; i++){ for (int j = 0; j <= N-1; j++) if (Queen[i][j] == 1) cout << "□"; else cout << "■"; cout << endl; } cout << endl; }bool judgement(int Queen[][N], int i, int j) { for (int m = 0; m <= i - 1; ++m){ for (int n = 0; n <= N-1; ++n){ if (Queen[m][n] == 1){ if (n == j || abs(i - m) == abs(j - n)) return false; } } } return true; }

图为运行后的显示结果：