C语言实现N皇后问题

欢迎大家来到IT世界,在知识的湖畔探索吧!

N皇后问题是一个经典的回溯算法问题，它要求在N×N的棋盘上放置N个皇后，使得它们无法互相攻击。根据国际象棋的规则，皇后可以沿着水平、垂直和对角线方向移动任意数量的空格进行攻击。因此，问题的核心在于找到一种放置方法，使得任何两个皇后都不在同一行、同一列或同一对角线上。

完整代码实现

#include 
   
     #include 
    
      #include 
     
       #include 
      
        // 结果集结构体，用于存储所有解 typedef struct { char *solutions; // 三维数组存储所有解 int capacity; // 当前分配的内存容量 int size; // 实际解的数量 } SolutionSet; // 初始化解决方案集 SolutionSet* createSolutionSet(int initialCapacity) { SolutionSet *set = (SolutionSet*)malloc(sizeof(SolutionSet)); set->solutions = (char*)malloc(initialCapacity * sizeof(char)); set->capacity = initialCapacity; set->size = 0; return set; } // 扩展解决方案集容量 void expandSolutionSet(SolutionSet *set) { set->capacity *= 2; set->solutions = (char*)realloc(set->solutions, set->capacity * sizeof(char)); } // 添加一个解到解决方案集 void addSolution(SolutionSet *set, char solution, int n) { if (set->size >= set->capacity) { expandSolutionSet(set); } // 深拷贝棋盘状态 char newSolution = (char)malloc(n * sizeof(char*)); for (int i = 0; i < n i newsolutioni='strdup(solution[i]);' set->solutions[set->size++] = newSolution; } // 释放解决方案集内存 void freeSolutionSet(SolutionSet *set, int n) { for (int i = 0; i < set->size; i++) { for (int j = 0; j < n j freeset->solutions[i][j]); } free(set->solutions[i]); } free(set->solutions); free(set); } // 检查当前位置是否合法 bool isSafe(int row, int col, bool *cols, bool *diag1, bool *diag2, int n) { return !cols[col] && !diag1[row - col + n - 1] && !diag2[row + col]; } // 回溯算法核心函数 void backtrack(int row, int n, char board, SolutionSet *set, bool *cols, bool *diag1, bool *diag2) { if (row == n) { addSolution(set, board, n); return; } for (int col = 0; col < n; col++) { if (isSafe(row, col, cols, diag1, diag2, n)) { // 放置皇后 board[row][col] = 'Q'; cols[col] = true; diag1[row - col + n - 1] = true; // 主对角线 diag2[row + col] = true; // 次对角线 // 递归下一行 backtrack(row + 1, n, board, set, cols, diag1, diag2); // 回溯撤销 board[row][col] = '.'; cols[col] = false; diag1[row - col + n - 1] = false; diag2[row + col] = false; } } } // 主函数：解决N皇后问题 char* solveNQueens(int n, int* returnSize) { if (n <= 0) { *returnSize = 0; return NULL; } // 初始化棋盘 char board = (char)malloc(n * sizeof(char*)); for (int i = 0; i < n; i++) { board[i] = (char*)malloc((n + 1) * sizeof(char)); // +1存放'\0' memset(board[i], '.', n); board[i][n] = '\0'; } // 初始化标记数组 bool *cols = (bool*)calloc(n, sizeof(bool)); bool *diag1 = (bool*)calloc(2 * n - 1, sizeof(bool)); // 主对角线数量：2n-1 bool *diag2 = (bool*)calloc(2 * n - 1, sizeof(bool)); // 次对角线数量：2n-1 SolutionSet *set = createSolutionSet(10); // 初始容量10 backtrack(0, n, board, set, cols, diag1, diag2); // 释放临时资源 for (int i = 0; i < n i freeboardi freeboard freecols freediag1 freediag2 returnsize='set-'>size; char *result = set->solutions; free(set); // 仅释放结构体，保留结果数组 return result; } // 示例使用 int main() { int n = 4; int returnSize; char *solutions = solveNQueens(n, &returnSize); printf("%d皇后问题共有%d种解法：\n", n, returnSize); for (int i = 0; i < returnSize; i++) { printf("解法%d:\n", i + 1); for (int j = 0; j < n; j++) { printf("%s\n", solutions[i][j]); } printf("\n"); } // 释放结果内存 for (int i = 0; i < returnSize; i++) { for (int j = 0; j < n; j++) free(solutions[i][j]); free(solutions[i]); } free(solutions); return 0; } 
       
      
     
   

欢迎大家来到IT世界,在知识的湖畔探索吧!

代码详细解析

1. 数据结构设计

• SolutionSet结构体：
• solutions：三维指针数组，存储所有合法的棋盘布局。
• capacity：当前分配的内存容量，避免频繁扩容。
• size：实际找到的解的数量。
• 设计要点：
• 三维数组结构：solutions[i]表示第i个解，solutions[i][j]为第j行字符串。
• 容量与解数量分离：避免频繁内存分配。

2. 核心算法实现

初始化函数createSolutionSet

• 功能：创建初始结果容器。
• 参数：initialCapacity初始容量（建议设为10）。
• 内存分配：
• 分配SolutionSet结构体内存。
• 预分配解指针数组空间。

动态扩容机制expandSolutionSet

• 触发条件：当size >= capacity时调用。
• 优化点：翻倍扩容策略减少realloc调用次数，均摊时间复杂度为O(1)。

解存储管理addSolution

• 关键操作：
• strdup()复制每行字符串，避免指针共享。
• 独立存储每个解的棋盘状态，防止回溯修改影响已存解。

冲突检测函数isSafe：

• 列冲突：使用cols数组记录已被占用的列。
• 主对角线：行列差row-col范围为-(n-1)到n-1，通过+n-1偏移到非负索引。
• 次对角线：行列和row+col范围为0到2n-2。

回溯函数backtrack：

• 递归流程：

终止条件：处理完所有行（row == n），保存当前棋盘状态。

遍历列：在当前行的每一列尝试放置皇后。

安全检查：通过isSafe()确保当前位置合法。

状态更新：放置皇后后更新标记数组。

递归深入：处理下一行。

回溯恢复：撤销当前操作，尝试其他可能性。

主函数实现solveNQueens

• 关键步骤：

动态棋盘初始化：每行末尾添加’\0’，便于直接作为字符串处理。

标记数组分配：使用calloc初始化为false。

回溯入口：从第0行开始递归搜索。

资源清理：释放临时使用的棋盘和标记数组，返回结果集。

3. 内存管理

• 动态分配棋盘：

欢迎大家来到IT世界,在知识的湖畔探索吧!char board = (char)malloc(n * sizeof(char*)); for (int i = 0; i < n; i++) { board[i] = (char*)malloc((n + 1) * sizeof(char)); }

• 每行末尾添加\0以便直接作为字符串处理。
• 结果集管理：
• 深拷贝解决方案：使用strdup复制每行字符串，避免指针共享。
• 动态扩容机制：当解的数量达到当前容量时，容量翻倍并realloc。
• 资源释放freeSolutionSet：
• 棋盘和标记数组：在回溯完成后立即释放。
• 释放顺序：从内到外逐层释放，避免内存泄漏。
• 调用示例：用户获取解后需手动释放结果内存。

4. 复杂度分析

• 时间复杂度：O(N!)，最坏情况下需要探索所有可能的排列。
• 空间复杂度：O(N²)用于存储棋盘，O(N)用于递归栈深度。

5. 示例输出（n=4时）

4皇后问题共有2种解法： 解法1: .Q.. ...Q Q... ..Q. 解法2: ..Q. Q... ...Q .Q..

关键优化点

1. 对角线索引计算优化：

• 主对角线索引：row – col + n – 1
• 次对角线索引：row + col
• 确保索引始终在合法范围内。

2. 结果集动态扩容：

• 初始容量设为10，每次翻倍扩容，减少realloc调用次数。

3. 减少字符串操作：

• 使用memset快速初始化棋盘行，避免逐字符赋值。

扩展改进方向

• 位运算优化：使用位掩码代替布尔数组，减少内存占用。
• 并行计算：对于大规模N值，可将不同行的搜索任务分配到多个线程。
• 对称性剪枝：利用棋盘的对称性减少重复计算。
• 迭代法实现：改用栈模拟递归，避免栈溢出风险。