论坛 › 《带你学C带你飞》（语法篇） › 通用解题思想：回溯法（附八皇后问题解析）

pixie0096 发表于 2020-2-25 18:46:54

朕想知道

前面那个人好丑 发表于 2020-2-27 21:25:17

朕想知道

不要打扰我 发表于 2020-2-28 11:54:45

1

kelvinlewis777 发表于 2020-2-28 17:28:00

朕想知道

兀凉 发表于 2020-3-3 15:00:44

签到

1481821848 发表于 2020-3-6 11:29:41

12

吕乐甜 发表于 2020-3-9 15:23:38

朕想知道

milesl 发表于 2020-3-9 23:06:35

什么情况

y12 发表于 2020-3-13 10:03:44

真想知道

言覃Jack 发表于 2020-3-13 16:01:35

真想知道

EmmmmmmTRUE 发表于 2020-3-13 21:43:05

朕想知道

欧奇诺 发表于 2020-3-16 10:41:38

.

嘟嘟橙 发表于 2020-3-16 11:47:52

朕想知道

可爱的华子 发表于 2020-3-16 16:55:26

朕想知道

Draem 发表于 2020-3-16 17:46:10

{:5_95:}

Draem 发表于 2020-3-16 18:13:48

#include <stdio.h>

int count = 0;

int check(int i, int j, int (*queen));
void setQueen(int i, int (*queen));

int check(int i, int j, int (*queen))
{
      int s, t;

      // 判断行
      for (s = i, t = 0; t < 8; t++)
      {
                if (queen == 1 && t != j)
                {
                        return 0;
                }
      }

      // 判断列
      for (t = j, s = 0; s < 8; s++)
      {
                if (queen == 1 && s != i)
                {
                        return 0;
                }
      }

      // 判断左上方
      for (s = i-1, t = j-1; s >= 0 && t >= 0; s--, t--)
      {
                if (queen == 1)
                {
                        return 0;
                }
      }

      // 判断右上方
      for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
      {
                if (queen == 1)
                {
                        return 0;
                }
      }

      // 判断左下方
      for (s = i+1, t = j-1; s < 8 && t >= 0; s++, t--)
      {
                if (queen == 1)
                {
                        return 0;
                }
      }

      // 判断右下方
      for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
      {
                if (queen == 1)
                {
                        return 0;
                }
      }

      // 经过上面层层关卡还能存活，那么说明符合条件,返回1
      return 1;
}

void setQueen(int col, int (*queen))
{
      int i, j, row;

      // 所有皇后放置完毕
      if (col == 8)
      {
                for (i = 0; i < 8; i++)
                {
                        for (j = 0; j < 8; j++)
                        {
                              if (queen != 0)
                              {
                                        printf("Q ");
                              }
                              else
                              {
                                        printf("* ");
                              }
                        }
                        putchar('\n');
                }

                putchar('\n');
                count++;

                return;
      }

      // 迭代每一行
      for (row = 0; row < 8; row++)
      {
                // 检查每一行中对应的每一列能否放置皇后
                if (check(row, col, queen))
                {
                        // 如果queen符合条件，则放置皇后
                        queen = 1;
                        // col+1，进入下一层递归
                        setQueen(col+1, queen);
                        // 只有两种情况会执行下面语句
                        // 1. col+1遇到所有的row都不合适
                        // 2. 完成整个二维数组的放置
                        // 无论哪种情况，
                        queen = 0;
                }
      }
}

int main(void)
{
      int queen;
      int i, j;

      // 初始化二维数组，1表示已放置皇后，0表示没有
      for (i = 0; i < 8; i++)
      {
                for (j = 0; j < 8; j++)
                {
                        queen = 0;
                }
      }

      setQueen(0, queen);

      return 0;
}

诚信肥宅 发表于 2020-3-16 23:12:25

1

风与尘的誓约 发表于 2020-3-17 15:25:37

{:10_254:}

汉末天子 发表于 2020-3-17 15:43:43

正想知道

苏瓦奥术 发表于 2020-3-19 11:09:32

朕想知道

查看完整版本: 通用解题思想：回溯法（附八皇后问题解析）