你本来是有机会的，
但是你输了，
你不能活在过去。
——派大星《海绵宝宝》
数据结构 —— N皇后
C语言程序
可以更改N值而修改棋盘规格
/*******************************************
*
* 回溯法N皇后
* create: 2020年6月4日19点59分
* author: LOS
*
*******************************************
* 此程序作法与回溯法的01背包类似
*******************************************
* 空间树不是二叉树，在回溯法中，空间树是存储了
* 每一步所可能的所有结果，并且遍历该结果寻找到
* 最优路径。
*******************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CAPACITY 500 // 可操作数据的最大容量
#define N 5 // 皇后的总数量
typedef int Elem; // 定义最小元素
typedef struct Node{
struct Node *nodes[N]; // 子节点
Elem curChessBoard[N][N]; // 存储棋盘的状态 0表示没有皇后，1表示有皇后
} Node;
struct {
Node Nodes[MAX_CAPACITY];
int size;
} NodeCapacity; // 存储所有可操作数据的容器
Node* rootNode;
int count = 0;
void init() { // 初始化全局变量
NodeCapacity.size = 0;
}
Node* createChessBoard() {
Node* p = &NodeCapacity.Nodes[NodeCapacity.size];
NodeCapacity.size++;
return p;
}
void printChessBoard(Elem chessBoard[N][N]) {
int j, k;
count++;
printf("第%d种情况：
", count);
printf("-----------------
");
for (j = 0; j < N; j++) { // 行
for (k = 0; k < N; k++) {
printf("%d ", chessBoard[j][k]);
}
putchar('
');
}
printf("-----------------
");
}
void trackBack(Node *node,int layer) { // layer层级
int i,j,k;
int disabledLines[N] = { 0 };
if (layer == N) {
printChessBoard(node->curChessBoard); // 输出棋盘
return; // 到最终子叶节点则直接出栈
}
// 判断剪枝 跳过根
for (i = 0; i < N; i++) { // 指定某一行
for (j = 0; j < layer; j++) { // 针对i行
if (node->curChessBoard[i][j]) {
disabledLines[i] = 1;
}
}
for (j = 0; j < N; j++) { // 针对列（此为不可能存在的现象，不作判断）
// 此处留着更改遍历策略时使用
}
for (j = i + 1, k = layer - 1; j < N && k >= 0; j++, k--) { // 左下方向寻找
if (node->curChessBoard[j][k]) {
disabledLines[i] = 1;
}
}
for (j = i - 1, k = layer - 1; j >= 0 && k >= 0; j--, k--) { // 左上方向寻找
if (node->curChessBoard[j][k]) {
disabledLines[i] = 1;
}
}
for (j = i - 1, k = layer + 1; j >= 0 && k < N; j--, k++) { // 右上方向寻找（同理不作判断）
// 此处留着更改遍历策略时使用
}
for (j = i + 1, k = layer + 1; j < N && k < N; j++, k++) { // 右下方向寻找（同理不作判断）
// 此处留着更改遍历策略时使用
}
}
for (i = 0; i < N; i++) { // 在行上放皇后
if ( disabledLines[i] ) continue; // 被剪枝的部分跳过
node->nodes[i] = createChessBoard(); // 新建一个节点
memcpy(node->nodes[i]->curChessBoard, node->curChessBoard, sizeof(node->curChessBoard)); // 复制数组
node->nodes[i]->curChessBoard[i][layer] = 1; //放置皇后
trackBack(node->nodes[i], layer + 1);
}
}
void main() {
rootNode = createChessBoard(); // 有根节点即可
memset(rootNode->curChessBoard, 0, sizeof(rootNode->curChessBoard));
trackBack(rootNode, 0);
}
运行结果
第1种情况：
-----------------
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
-----------------
第2种情况：
-----------------
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
-----------------
第3种情况：
-----------------
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1
-----------------
第4种情况：
-----------------
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0
-----------------
第5种情况：
-----------------
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
-----------------
第6种情况：
-----------------
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
-----------------
第7种情况：
-----------------
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
-----------------
第8种情况：
-----------------
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
-----------------
第9种情况：
-----------------
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
-----------------
第10种情况：
-----------------
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
-----------------