[算法]经典算法8皇后（N皇后）问题的解法，C语言实现

今天写点简单的，C语言求解八皇后问题，相信学过C语言的朋友一定知道这个经典问题吧，解法也是多种，目前主要有回溯，递推两种方法，今天讲回溯+递归的求法，效率可能不太高，不过直接易于理解 问题 ： 能不能在一个标准的国际象棋棋盘上放8个皇后，使她们相互之间不能互吃具体点就是，在一个8*8的棋盘上放皇后，皇后是所有方向上都可以移动的，现在要让她们不能互吃的话就要使得她们不会在同一条线上 具体解法：从第一行第一列的位置开始放棋子（假定列优先），然后记录其占用的行斜直线的编号，然后放第二个棋子，在排除前面所有棋子的所占的编号的情况下选择到有效位置，然后继续，直到放满8个棋子为止 代码如下： /**八皇后算法问题*author CG*2008 12 22*/#include "stdio.h"#include "stdlib.h"#include "conio.h"#define N 8 /* 设置皇后数量为8*/int a[N], b[2*N + 1], c[2*N +1];/*三个数组记录各个方向上的皇后*/int count = 0;/*计数器*/int Queen(int row) { int col; /* 局部变量 */ for (col = 1 ; col < N colbr> if (a[col - 1] + b[row + col - 2] + c[row - col + N - 1] == 0) { /* *这里这部很重要，用于判断皇后位置是否符合条件，只有各个方向的直线上 *都没有皇后才符合条件 * a[col-1] 记录第 col 列有无皇后, 1 表示有。 * b[row+col-2] 记录从左上数第 row+col-1 条斜率为 1 的线上有无皇后。 * c[row-col+N-1] 记录从右上数第 row-col+N-1 条斜率为 -1 的线上有无皇后。 */ a[col - 1] = 1; /* 更改数据 */ b[row + col - 2] = 1; c[row - col + N - 1] = 1; gotoxy(col * 2 , row);/* 画皇后 */ putch('Q'); if (row < N rowbr> Queen(row + 1); /*继续*/ } else {/*递归结束*/ count++; /*计数器+1*/ gotoxy(1 , N + 2); printf("Solution No %d ", count); getch(); } a[col - 1] = 0; /* 清空数据 */ b[row + col - 2] = 0; c[row - col + N-1] = 0; gotoxy(col * 2 , row); /* 清除图象 */ putch('.'); }/*if */ }/*for */return 0;}/*Queen */int main(){ int i, j; clrscr();/*清屏*/ for(i = 1 ; i < N i br> for(j = 1 ; j < N jbr> gotoxy(i * 2 , j);/*注意字符占位问题大写Q和点号占两个字符位*/ putch('.'); }/*for*/ }/*for*/ Queen(1); /* 开始回溯算法 */ gotoxy(1 , N + 3); /* 显示最后结果 */ printf("%d Solution(s)n", count); system("pause");}/*main*/ -------------------------------------------------------------------------------------- - 版权声明： - 如在本页面内无特别说明，本文内容均为[李大仁博客]原创，本文版权归[李大仁博客]所有。 - 欢迎转载，转载请务必在文章页面明显位置提供原文链接并注明出处。欢迎您在转载本文时保留本段声明。 - 文章标题： [算法]经典算法8皇后（N皇后）问题的解法，C语言实现 - 独立博客： 李大仁博客 - 永久链接：http://www.lidaren.com/archives/251 -------------------------------------------------------------------------------------- 以上内容由博客自动发布工具自动发布，最终显示内容和效果会与原文内容有所偏差，敬请谅解。