如何暴力解决弱N皇后问题（比较sb的做法）

暴力嘛，大概还有一个说法就是枚举，穷举的意思了。穷举， 顾名思义为遍历一个集合。这个集合的意义很广， 在解决不同的问题过程中， 这个需要穷举的集合也不尽相同。 比如，我们可以穷举一遍一个给定的整数数组，寻找其中最大的一个； 我们可以穷举问题域，找出满足特定条件的项；等等。

那么，下面我想写一下如何利用穷举去解决比较弱的n（n<8）的皇后问题。

在N X N格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

        我们先考虑N = 4的情况，也就是在4*4的棋盘上布局。 由于任意两个皇后不能在同一行出现， 所以每行一定有且仅有一个皇后。我们假设r0, r1, r2, r3分别表示第一，二，三，四行的皇后所在的位置。r0, r1, r2, r3都有可能在第一，二，三，四列，也就是取值可能为0,1,2,3。

主要穷举的代码如下：O（n^4）.....我醉了。。。

int ValidCount = 0;
for(int r0 = 0; r0 < 4; r0++) {
for(int r1 = 0; r1 < 4; r1++) {
for(int r2 = 0; r2 < 4; r2++) {
for(int r3 = 0; r3 < 4; r3++) {
bool isValid = true;
// 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后
// 2. 验证 任意两个皇后没有处于同一列。
if (r0 == r1 || r0 == r2 || r0 == r3 || r1 == r2 || r1 == r3 || r2 == r3) isValid = false;
// 3. 验证 任意两个皇后没有处于同一条斜线上
if ((r0 + 0 == r1 + 1) || (r0 + 0 == r2 + 2) || (r0 + 0 == r3 + 3) || (r1 + 1 == r2 + 2) || (r1 + 1 == r3 + 3)
|| (r2 + 2 == r3 + 3)) isValid = false;
if ((r0 - 0 == r1 - 1) || (r0 - 0 == r2 - 2) || (r0 - 0 == r3 - 3) || (r1 - 1 == r2 - 2) || (r1 - 1 == r3 - 3)
|| (r2 - 2 == r3 - 3)) isValid = false;
// 4. 找到合法的布局
if (isValid) {
// 更新合法布局总数
ValidCount++;
// 输出布局
for(int i = 0; i < 4; i++) if(r0 == i) printf("Q"); else printf(".");
printf("n");
for(int i = 0; i < 4; i++) if(r1 == i) printf("Q"); else printf(".");
printf("n");
for(int i = 0; i < 4; i++) if(r2 == i) printf("Q"); else printf(".");
printf("n");
for(int i = 0; i < 4; i++) if(r3 == i) printf("Q"); else printf(".");
printf("nn");
}
}
}
}
}
printf("TotalValidCount=%d", ValidCount);

int ValidCount = 0;
const int N = 8;
int r[N];
for(r[0] = 0; r[0] < N; r[0]++) {
for(r[1] = 0; r[1] < N; r[1]++) {
for(r[2] = 0; r[2] < N; r[2]++) {
for(r[3] = 0; r[3] < N; r[3]++) {
for(r[4] = 0; r[4] < N; r[4]++) {
for(r[5] = 0; r[5] < N; r[5]++) {
for(r[6] = 0; r[6] < N; r[6]++) {
for(r[7] = 0; r[7] < N; r[7]++) {
bool isValid = true;
// 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后
// 2. 验证 任意两个皇后没有处于同一列。
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] == r[j]) isValid = false;
// 3. 验证 任意两个皇后没有处于同一条斜线上
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] + i == r[j] + j) isValid = false;
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] - i == r[j] - j) isValid = false;
// 4. 找到合法的布局
if (isValid) {
// 更新合法布局总数
ValidCount++;
// 输出布局
for (int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) if(r[i] == j) printf("Q"); else printf(".");
printf("n");
}
printf("n");
}
}
}
}
}
}
}
}
}
printf("TotalValidCount=%d", ValidCount);

众所周知，8皇后问题有92个解！！！

再用递归来小优化一下：

void search(int* r, int N, int step) {
if (step == N) {
bool isValid = true;
// 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后
// 2. 验证 任意两个皇后没有处于同一列。
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] == r[j]) isValid = false;
// 3. 验证 任意两个皇后没有处于同一条斜线上
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] + i == r[j] + j) isValid = false;
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if (r[i] - i == r[j] - j) isValid = false;
// 4. 找到合法的布局
if (isValid) {
// 输出布局
for (int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) if(r[i] == j) printf("Q"); else printf(".");
printf("n");
}
printf("n");
}
return;
}
for(r[step] = 0; r[step] < N; r[step]++) {
search(r, N, step + 1);
}
}
int main() {
const int N = 8;
int r[N];
search(r, N, 0);
}

最后

以上就是醉熏冰淇淋为你收集整理的如何暴力解决弱N皇后问题（比较sb的做法）的全部内容，希望文章能够帮你解决如何暴力解决弱N皇后问题（比较sb的做法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。