开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
6_6.C
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：4k
源码类别：

数据结构

开发平台：

C/C++

6_6.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 6_6.c                       */
  3. /*    应用递归来解 N 皇后问题               */
  4. /*    数字 1: 表示是放置皇后                */
  5. /*    数字 0: 表示没有放置                  */
  6. /* ======================================== */
  7. #define MAXQUEEN   8              /* 最大放置的皇后数   */
  9. int pad[MAXQUEEN][MAXQUEEN] = {   /* N X N 的棋盘       */
  10.          0, 0, 0, 0, 0, 0, 0, 0,
  11.          0, 0, 0, 0, 0, 0, 0, 0,
  12.          0, 0, 0, 0, 0, 0, 0, 0,
  13.          0, 0, 0, 0, 0, 0, 0, 0,
  14.          0, 0, 0, 0, 0, 0, 0, 0,
  15.          0, 0, 0, 0, 0, 0, 0, 0,
  16.          0, 0, 0, 0, 0, 0, 0, 0,
  17.          0, 0, 0, 0, 0, 0, 0, 0  };
  19. /* ---------------------------------------- */
  20. /*  放 N 个皇后的递归函数                   */
  21. /* ---------------------------------------- */
  22. int put_queen(int x,int y,int times)
  23. {
  24.    int i,j,result = 0;
  26.    if ( times > MAXQUEEN )        /* 终止条件           */
  27.       return 1;
  28.    else
  29.       if ( place(x,y) )           /* 检查是否可放置皇后 */
  30.       {
  31.          pad[x][y] = 1;           /* 放置皇后           */
  32.          for ( i = 0; i < MAXQUEEN; i++)
  33.             for ( j = 0; j < MAXQUEEN; j++)
  34.             {
  35.                /* 递归调用放置下一个皇后 */
  36.                result += put_queen(i,j,times + 1);
  37.                if ( result > 0 )
  38.                   break;
  39.             }
  40.          if ( result > 0 )        /* 找到了解           */
  41.             return 1;
  42.          else
  43.          {
  44.             pad[x][y] = 0;        /* 清除皇后           */
  45.             return 0;
  46.          }
  47.       }
  48.       else
  49.          return 0;
  50. }
  52. /* ---------------------------------------- */
  53. /*  检查皇后是否有相互攻击                  */
  54. /* ---------------------------------------- */
  55. int place(int x,int y)
  56. {
  57.    int x1,y1;
  59.    if ( pad[x][y] != 0 )          /* 己放置皇后         */
  60.       return 0;
  61.    x1 = x - 1;                    /* 检查左上方         */
  62.    y1 = y - 1;
  63.    while ( x1 >= 0 && y1 >= 0 )
  64.       if ( pad[x1--][y1--] != 0 )
  65.          return 0;
  66.    x1 = x + 1;                    /* 检查右下方         */
  67.    y1 = y + 1;
  68.    while ( x1 < MAXQUEEN && y1 < MAXQUEEN )
  69.       if ( pad[x1++][y1++] != 0 )
  70.          return 0;
  71.    x1 = x + 1;                    /* 检查右上方         */
  72.    y1 = y - 1;
  73.    while ( x1 < MAXQUEEN && y1 >= 0 )
  74.       if ( pad[x1++][y1--] != 0 )
  75.          return 0;
  76.    x1 = x - 1;                    /* 检查左下方         */
  77.    y1 = y + 1;
  78.    while ( x1 >=0 && y1 < MAXQUEEN )
  79.       if ( pad[x1--][y1++] != 0 )
  80.          return 0;
  81.    x1 = x;                        /* 检查下方           */
  82.    y1 = y + 1;
  83.    while ( y1 < MAXQUEEN )
  84.       if ( pad[x1][y1++] != 0 )
  85.          return 0;
  86.    x1 = x;                        /* 检查上方           */
  87.    y1 = y - 1;
  88.    while ( y1 >= 0 )
  89.       if ( pad[x1][y1--] != 0 )
  90.          return 0;
  91.    x1 = x + 1;                    /* 检查右方           */
  92.    y1 = y;
  93.    while ( x1 < MAXQUEEN )
  94.       if ( pad[x1++][y1] != 0 )
  95.          return 0;
  96.    x1 = x - 1;                    /* 检查左方           */
  97.    y1 = y;
  98.    while ( x1 >= 0 )
  99.       if ( pad[x1--][y1] != 0 )
  100.          return 0;
  101.    return 1;
  102. }
  104. /* ---------------------------------------- */
  105. /*  主程式: 用递归的方法解 N = 8 皇后问题.  */
  106. /* ---------------------------------------- */
  107. void main()
  108. {
  109.    int i,j;
  111.    put_queen(0,0,1);              /* 调用递归函数       */
  112.    printf("放置八皇后的棋盘图形:n");
  113.    for ( i = 0; i < MAXQUEEN; i++)   /* 印出棋盘的图形  */
  114.    {
  115.       for ( j = 0; j < MAXQUEEN; j++)
  116.          printf("%d",pad[i][j]);  /* 印出各座标值       */
  117.       printf("n");               /* 换行               */
  118.    }
  119. }