原标题:C语言-求八皇后所有解
原文来自:CSDN 原文链接:https://blog.csdn.net/weixin_42098924/article/details/102918913
八皇后
1、介绍
八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。
2、思路
在一个8x8的棋盘下放置皇后,当前皇后的相同行、列,对角线,及反对角线都不能有其它皇后,否则就会被吃掉。所以为了保证八个皇后都能被放置不被吃。将用回溯算法来求取八皇后被放置的所有解。回溯就是当前的皇后无法放置时,回退到前一个皇后的状态,改变前一个皇后的位置,在改变了前一个皇后位置后,接下来重新放置当前皇后,找到合适位置,放置皇后,进行下一步,找不到合适位置,则继续回退,前一个的位置都试过还不行,则继续回退前一个的前一个,以此类推直到找到最后一个皇后能放置的位置,那么这就是一个解。
3、核心代码
int try(int i) {
int j, k, q = 0;
//遍历各行,寻找可放置皇后之处
for (j = 0; j < n; j++) {
if (row[j] == 1 // j 行可放子
&& d1[i - j + n - 1] == 1 // 主对角线可放子
&& d2[i + j] == 1) // 反对角线可放子
{
x[i] = j; // 记录:在 i列 j行放置皇后
set(i, j, 0); // 放置皇后:设置 j行及其对角线不可放子
if (i < n - 1) { // 题未解完
try(i + 1); // 尝试下一步
} else // 得到最终解
{
output();
}
set(i, j, 1); // 移去皇后(回溯):恢复 j行及其对角线可放子
}
}
}
4、完整代码
#include <stdio.h>
#include <stdlib.h>
#define n 8 //皇后个数
int x[n]; // 解
int row[n], // 行
d1[2 * n - 1], // 主对角线。同一线上,坐标差相同
d2[2 * n - 1]; // 反对角线。同一线上,坐标和相同
int success=1; //解的个数
// 在 j行 i列,放置皇后(e = 0) 或移去皇后(e = 1)
int set(int i, int j, int e) {
row[j] = e;
d1[i - j + n - 1] = e;
d2[i + j] = e;
}
//输出解
void output(){
int i;
printf("第%d组解: ", success++);
for (i = 0; i < n; i++)
printf("%3d", x[i]);
printf("n");
}
//在第 i列,选择放置皇后的行
int try(int i) {
int j, k, q = 0;
//遍历各行,寻找可放置皇后之处
for (j = 0; j < n; j++) {
if (row[j] == 1 // j 行可放子
&& d1[i - j + n - 1] == 1 // 主对角线可放子
&& d2[i + j] == 1) // 反对角线可放子
{
x[i] = j; // 记录:在 i列 j行放置皇后
set(i, j, 0); // 放置皇后:设置 j行及其对角线不可放子
if (i < n - 1) { // 题未解完
try(i + 1); // 尝试下一步
} else // 得到最终解
{
output();
}
set(i, j, 1); // 移去皇后(回溯):恢复 j行及其对角线可放子
}
}
}
int main() {
int i;
// 设置各行可放子
for (i = 0; i < n; i++)
row[i] = 1;
// 设置各对角线可放子
for (i = 0; i < 2 * n - 1; i++) {
d1[i] = d2[i] = 1;
}
//执行
try(0);
}
5、相关文件:Github
免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com