Home > 算法研究 > [算法]经典算法8皇后(N皇后)问题的解法,C语言实现

[算法]经典算法8皇后(N皇后)问题的解法,C语言实现

今天写点简单的,C语言求解八皇后问题,相信学过C语言的朋友一定知道这个经典问题吧,解法也是多种,目前主要有回溯,递推两种方法,今天讲回溯+递归的求法,效率可能不太高,不过直接易于理解

问题 : 能不能在一个标准的国际象棋棋盘上放8个皇后,使她们相互之间不能互吃具体点就是,在一个8*8的棋盘上放皇后,皇后是所有方向上都可以移动的,现在要让她们不能互吃的话就要使得她们不会在同一条线上

具体解法:从第一行第一列的位置开始放棋子(假定列优先),然后记录其占用的行斜直线的编号,然后放第二个棋子,在排除前面所有棋子的所占的编号的情况下选择到有效位置,然后继续,直到放满8个棋子为止


代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
*八皇后算法问题
*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 ; col++){
	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){/*如果没有遍历所有row*/
			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++){/* 画棋盘*/
	for(j = 1 ; j <= N ; j++){
		gotoxy(i * 2 , j);/*注意字符占位问题大写Q和点号占两个字符位*/
		putch('.');
	}/*for*/
 }/*for*/
 Queen(1); /* 开始回溯算法 */
 gotoxy(1 , N + 3); /* 显示最后结果 */
 printf("%d Solution(s)n", count);
 system("pause");
}/*main*/
Categories: 算法研究 Tags:
  1. December 23rd, 2008 at 17:16 | #1

    CG什么时候有空教教我c语言的入门。。。

  2. December 23rd, 2008 at 18:37 | #2

    好的,有时间一定

  1. No trackbacks yet.