鱼C论坛

 找回密码
 立即注册
查看: 3175|回复: 0

[学习笔记] 《数据结构与算法》——八皇后问题

[复制链接]
发表于 2017-8-1 21:45:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
算法的核心就是通过递归的办法不断地遍历棋盘,如果前n-k个皇后都找到位置了,那么就能判断第n-k+1个能否找到位置。
遍历一行的每一个位置,通过递归的办法不断地判断这一行的每一个位置是否满足条件,若满足条件调用一次函数,遍历下一行的每个位置,当遍历完八行,每一行都找到满足条件的位置则打印并返回,若是出现一行找不到满足条件的位置,则返回但不打印。
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. using namespace std;

  5. int n = 0;

  6. void Output(int chess[8][8])
  7. {
  8.         n++;
  9.         printf("No.%d\n", n);
  10.         for (int i = 0; i < 8; i++)
  11.         {
  12.                 for (int j = 0; j < 8; j++)
  13.                 {
  14.                         cout << chess[i][j] << " ";
  15.                 }
  16.                 cout << endl;
  17.         }
  18.         cout << endl;
  19. }

  20. int isDanger(int chess[8][8], int row, int col)
  21. {
  22.         int flag1 = 1, flag2 = 1, flag3 = 1, flag4 = 1, flag5 = 1, flag6 = 1;
  23.         for (int i = row; i >= 0; i--)
  24.         {
  25.                 if (chess[i][col] == 1)
  26.                 {
  27.                         flag1 = 0;
  28.                         break;
  29.                 }
  30.         }
  31.         for (int i = row; i < 8; i++)
  32.         {
  33.                 if (chess[i][col] == 1)
  34.                 {
  35.                         flag2 = 0;
  36.                         break;
  37.                 }
  38.         }
  39.         for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
  40.         {
  41.                 if (chess[i][j] == 1)
  42.                 {
  43.                         flag3 = 0;
  44.                         break;
  45.                 }
  46.         }
  47.         for (int i = row, j = col; i < 8 && j < 8; i++, j++)
  48.         {
  49.                 if (chess[i][j] == 1)
  50.                 {
  51.                         flag4 = 0;
  52.                         break;
  53.                 }
  54.         }
  55.         for (int i = row, j = col; i < 8 && j >= 0; i++, j--)
  56.         {
  57.                 if (chess[i][j] == 1)
  58.                 {
  59.                         flag5 = 0;
  60.                         break;
  61.                 }
  62.         }
  63.         for (int i = row, j = col; i >= 0 && j < 8; i--, j++)
  64.         {
  65.                 if (chess[i][j] == 1)
  66.                 {
  67.                         flag6 = 0;
  68.                         break;
  69.                 }
  70.         }

  71.         if (flag1&&flag2&&flag3&&flag4&&flag5&&flag6)return 0;
  72.         else return 1;
  73. }

  74. void queen(int chess[8][8], int row, int n)
  75. {
  76.         int chess2[8][8];
  77.         for (int i = 0; i < 8; i++)
  78.         {
  79.                 for (int j = 0; j < 8; j++)
  80.                 {
  81.                         chess2[i][j] = chess[i][j];
  82.                 }
  83.         }

  84.         if (row == 8)
  85.         {
  86.                 Output(chess2);
  87.         }
  88.         else
  89.         {
  90.                 for (int j = 0; j < n; j++)
  91.                 {
  92.                         if (!isDanger(chess2, row, j))
  93.                         {
  94.                                 for (int i = 0; i < 8; i++)
  95.                                 {
  96.                                         chess2[row][i] = 0;
  97.                                 }
  98.                                 chess2[row][j] = 1;
  99.                                 queen(chess2, row + 1, n);
  100.                         }
  101.                 }
  102.         }

  103. }

  104. int main()
  105. {
  106.         int chess[8][8];
  107.         for (int i = 0; i < 8; i++)
  108.         {
  109.                 for (int j = 0; j < 8; j++)
  110.                 {
  111.                         chess[i][j] = 0;
  112.                 }
  113.         }
  114.         queen(chess, 0, 8);
  115.         printf("\nThere is %d ways in total\n", n);

  116.         system("PAUSE");
  117. }
复制代码

评分

参与人数 1鱼币 +3 收起 理由
小甲鱼 + 3

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 02:25

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表