回溯算法与八皇后问题(N皇后问题)1 问题描述八皇后问题是数据结构与算法这一门课中经典的一个问题。

下面再来看一下这个问题的描述。

八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。

更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？2 回溯算法回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。

回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。

N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。

这也是N皇后问题的传统解法，很经典。

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步3) 在当前位置上满足条件的情形：在当前位置放一个皇后，若当前行是最后一行，记录一个解；若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；若当前行是最后一行，当前列不是最后一列，当前列设为下一列；若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；以上返回到第2步4) 在当前位置上不满足条件的情形：若当前列不是最后一列，当前列设为下一列，返回到第2步;若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。

为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。

为了便于将上述算法编程实现，将它用另一种形式重写：Queen()Loop:if check_pos(curr_row, curr_col) == 1 thenput_a_queen(curr_row, curr_col);if curr_row == N thenrecord_a_solution();end if;if curr_row != N thencurr_row = curr_row + 1;curr_col = 1;elseif curr_col != N thencurr_col = curr_col + 1;elsebacktrack();end if;end if;elseif curr_col != N thencurr_col = curr_col +1;elsebacktrack();end if;end if;end Queen;3 实现3.1 数据结构这里，用一个N个元素的一维数组来表示。

数组的下标表示棋盘的行，数组的元素表示该行皇后所在的列。

这个结构自然就消除了列冲突，因为每一行只有一个皇后。

还有利用它解决行冲突，也很简单，只要比较各个元素就行了，看有没有相等的元素。

斜线冲突也简单，因为同一斜线上的在一直线上，该直线的斜率为+1(左下至右上)或-1(左上至右下)，所以，左下至右上的冲突检测方法为看式子是否成立(row –curr_row)/(col –curr_col) = 1，也就是(row - col) = (curr_row –curr_col)，相同，则有冲突。

同理，左上至右下看式子(row + col) = (curr_row +curr_col)。

这里，也是看下标与其对应元素的和与差是不是与要检测位置的相应结果相同，如果有一个相同，就有冲突。

数据结构一确定，冲突检测方法就有了，关键的部分的算法就完成了。

3.2 代码/*************************************************************** File: NQueen.cDescripton: N皇后问题求解之回溯版Author: liuqh, Hunan UniversityDate: 2007.5.22, Tues.Version: 1.0**************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>#include <math.h>#define SOLS(n) (int)(pow(2.0, (double)(n)))#define DEBUG/*************************全局变量定义**************************/int N = -1; /*棋盘的大小*/char *p_board = NULL; /*指向棋盘，这里是用一个长度为N 的一维数组表示的*/char *buf = NULL; /* 输出缓冲 */int buf_index = -1;/*********************************本编译单元的函数声明*********************************/static int queen(FILE *fp);static int clear_board(int i);static int check_pos(int curr_row);static int record_a_solution(FILE *fp, int solutions);static int backtrack(int *p_curr_row);static void flush_buf(FILE *fp, int solutions);/*** 函数：main()** 功能：程序入口** 入口: 参数个数（整型）；程序名与N的大小** 出口：** 返回：成功返回0，否则返回-1** 备注：*/int main(int argc, char **argv){clock_t start, finish;double duration;int solutions;FILE *fp;/* 命令行参数检查*/if (argc != 2){fprintf(stderr, "用法: queen N\n") ;return -1;}N = atoi(argv[1]);if (N <= 0){fprintf(stderr, "用法: queen N \n N必须大于0\n") ;return -1;}/*开始计时*/start = clock();p_board = (char*)calloc(N, sizeof(char));if (NULL == p_board){fprintf(stderr, "为棋盘分配内存失败\n") ;return -1;}fp = NULL;if ((fp = fopen("solutions.txt", "w")) == NULL){free(p_board);fprintf(stderr, "创建文件solutions.txt失败！\n") ;return -1;}solutions = queen(fp);if (-1 == solutions){free(p_board);if (fclose(fp) == EOF){fprintf(stderr, "关闭文件solutions.txt失败！\n") ;return -1;}fprintf(stderr, "调用queen()失败\n") ;return -1;}printf("共有%d种解决方案，具体结果请查看文件solutions.txt\n", solutions) ;fprintf(fp, "solutions = %d\n", solutions);free(p_board);/*操作完成，计时结束*/finish = clock();/*计算时间间隔，以秒为单位*/duration = (double)(finish - start) / CLOCKS_PER_SEC;printf("计算完毕,共耗时%f秒!\n", duration);fprintf(fp, "time = %f\n", duration);if (fclose(fp) == EOF){fprintf(stderr, "关闭文件solutions.txt失败！\n") ;return -1;}return 0;}/*** 函数：queen()** 功能：计算N皇后问题的解** 入口: 记录结果的文件指针** 出口：** 返回：成功返回解的个数，出错返回-1** 备注：*/int queen(FILE *fp){int curr_row;int result;result = 0;if (clear_board(0) == -1){fprintf(stderr, "清空棋盘失败！\n") ;return -1;}curr_row = 0;p_board[curr_row] = (char)0;buf = (char*)calloc(SOLS(N)*N, sizeof(char));if (NULL == buf){fprintf(stderr, "为解分配内存失败\n") ;return -1;}while (1){if (check_pos(curr_row)== 1){if (N-1 == curr_row){result++;record_a_solution(fp, result);}if (curr_row != N-1){curr_row++;p_board[curr_row] = (char)0;continue;}}if (p_board[curr_row] != (char)(N-1)){p_board[curr_row] ++;}else{if (backtrack(&curr_row) == 1){break;}}} /* end while */flush_buf(fp, result);free(buf);return result;}/*** 函数：clear_board()** 功能：初始化棋盘** 入口: 初始化开始的行(整型), 全局变量p_board， N ** 出口：初始化后的棋盘，这里指指针p_board指向的数组** 返回：成功返回0，出错返回-1** 备注：*/int clear_board(int i){if (memset(&p_board[i], -1, N-i) == NULL){return -1;}return 0;}** 函数：check_pos()** 功能：检查某个位置是否能放一个皇后** 入口: 位置所在的行(整型), 全局变量p_board， N** 出口：** 返回：可以放置的话返回1，否则返回0** 备注：*/int check_pos(int curr_row){int i;int sum, sub;/*检查是否有行冲突*/for (i = 0; i < curr_row; i++){if (p_board[i] == p_board[curr_row]){return 0;}}/*检查斜线方向的冲突*/sum = curr_row + p_board[curr_row];sub = curr_row - p_board[curr_row];for (i = 0; i < curr_row; i++){if (i+p_board[i] == sum || i - p_board[i] == sub){return 0;}}return 1;}** 函数：record_a_solution()** 功能：记录一个合法的解** 入口：记录结果的文件指针；解的个数（整型）全局变量p_board， N** 出口：存储解的缓存buf（字符串）** 返回：成功，返回0，否则返回-1** 备注：解先缓存在内存中，这样快一点，要提高速度，修改SOLS宏以获得更大的缓冲区*/int record_a_solution(FILE *fp, int solutions){if (++buf_index != SOLS(N)){if (memcpy(&buf[buf_index*N], p_board, N) == NULL){fprintf(stderr, "拷贝解到缓冲时出错！\n") ;buf_index--;return -1;}}else{flush_buf(fp, solutions);}return 0;}/*** 函数：backtrack()** 功能：回溯到上一行** 入口: 全局变量p_board， N** 出口：当前行(整型指针)** 返回：可以回溯，返回0，否则返回1，表示算法可以退出了** 备注：可能递归调用自身*/int backtrack(int *p_curr_row){if (0 == *p_curr_row){if (clear_board(p_board[*p_curr_row]) == -1){fprintf(stderr, "backtrack():清空棋盘失败！\n") ;}return 1; }if (clear_board(p_board[*p_curr_row]) == -1){fprintf(stderr, "backtrack():清空棋盘失败！\n") ;return -1;}(*p_curr_row)--;if (p_board[*p_curr_row] != N-1){p_board[*p_curr_row]++;return 0;}else{return backtrack(p_curr_row);}}/*** 函数：flush_buf()** 功能：刷新缓冲区** 入口: 记录结果的文件指针；当前全部解的个数（整型）；全局变量buf，buf_index， N** 出口：** 返回：** 备注：*/void flush_buf(FILE *fp, int solutions){int k,i, j;for (k = 0; k <= buf_index; k++){fprintf(fp, "solutions %d\n",solutions - (buf_index - k));fprintf(fp, "--------------------------------------\ n");for (i = 0; i < N; i++){for (j = 0; j < N; j++){fprintf(fp, "%3c", j == buf[k*N+i] ? 'Q' : 'x');}fprintf(fp, "\n");}fprintf(fp, "--------------------------------------\ n");}buf_index = -1;}（注：可编辑下载，若有不当之处，请指正，谢谢!）。