八皇后问题是能用回溯法解决的一个经典问题。八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。现在拓展了下，编个程序解答n皇后问题
.
/*n皇后问题（该程序用回溯法解答）
*
*(C) LC
*/
#include<stdio.h>
#include<math.h>
#define MAX 20
static int x[MAX];
static int sum;
int Place(int k)//判断该位置可不可以放置皇后
{
int j;
for(j = 1; j < k; j++)
if((abs(k-j) == abs(x[j] - x[k])) || (x[j] == x[k]))
return 1;
return 0;
}
void output(int x[], int n)
{
int i, j;
int a[n][n];
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
a[i][j] = 0;
for(i = 1; i <= n; i++)
{
if(x[i])
a[i - 1][x[i] - 1] = 1;
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
printf("%d\t", a[i][j]);
printf("\n");
}
printf("\n");
}
void Backtrack(int t, int n)
{
int i;
if(t > n)
{
output(x, n);
sum++;
}
else
for(i = 1; i <= n; i++)
{
x[t] = i;
// printf("good!%d\t%d\t%d\n", x[t], t, i);
if(!Place(t))
Backtrack(t + 1, n);
}
}
int main(void)
{
int n;
printf("------------------------------\n");
printf("please input n of the game!\n");
scanf("%d", &n);
Backtrack(1, n);
printf("sum = %d\n", sum);
return 0;
}
|
运行该程序，当n = 4时候的输出结果：
------------------------------
please input n of the game!
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
sum = 2
|
运行该程序，当n = 8时候的输出结果：
------------------------------
please input n of the game!
8
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
......
sum = 92
|
阅读(1006) | 评论(0) | 转发(1) |
