Chinaunix首页 | 论坛 | 博客
  • 博客访问: 216332
  • 博文数量: 40
  • 博客积分: 2512
  • 博客等级: 大尉
  • 技术积分: 492
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-24 10:23
文章存档

2014年(1)

2011年(4)

2010年(35)

分类: C/C++

2010-10-03 16:44:43

   八皇后问题是能用回溯法解决的一个经典问题。八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯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


阅读(998) | 评论(0) | 转发(1) |
0

上一篇:回溯法

下一篇:贪心算法

给主人留下些什么吧!~~