论坛 › C\C++交流 › S1E36.八皇后

Saito77 发表于 2022-10-3 16:52:11

S1E36.八皇后

#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 < 4; t++)
      {
                if (queen == 1 && t != j)
                {
                        return 0;
                }
      }

      // 判断列
      for (t = j, s = 0; s < 4; 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 < 4 && t < 4; s++, t++)
      {
                if (queen == 1)
                {
                        return 0;
                }
      }

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

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

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

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

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

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

                return;
      }

      // 迭代每一行
      for (row = 0; row < 4; 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 < 4; i++)
      {
                for (j = 0; j < 4; j++)
                {
                        queen = 0;
                }
      }

      setQueen(0, queen);

      return 0;
}

请教一下鱼油们，为什么if的条件要多一个 t != j和 s != i。

aaron0919 发表于 2022-10-3 17:24:12

本帖最后由 aaron0919 于 2022-10-3 17:27 编辑

这我的#include<cstdio>
int vis,l,r;//竖列，两个斜线
int map;
int cnt;
void dfs(int x)
{
        if(x > 8)
        {
                cnt++;
                printf("No. %d\n",cnt);
                for(int i = 1;i <= 8;i++)
                {
                        for(int j = 1;j <= 8;j++)
                        {
                                printf("%d ",map);
                        }
                        printf("\n");
                }
                return;
        }
        for(int i = 1;i <= 8;i++)
        {
                if(vis == 0 && l == 0 && r ==0)//x-i有可能为负数
                {
                        map = 1;
                        vis = 1;
                        l = 1;
                        r = 1;
                        dfs(x+1);
                        vis = 0;
                        l = 0;
                        r = 0;
                        map = 0;
                }
        }
}
int main()
{
        dfs(1);
}

aaron0919 发表于 2022-10-3 17:28:52

代码一定要用<>代码格式发送

Saito77 发表于 2022-10-3 21:33:09

aaron0919 发表于 2022-10-3 17:24
这我的

很抱歉啊！看了一个小时，还是没看明白，没啥头绪。麻烦鱼油可以细讲一下吗？

Saito77 发表于 2022-10-3 21:33:49

aaron0919 发表于 2022-10-3 17:28
代码一定要用代码格式发送

ok{:5_109:}

查看完整版本: S1E36.八皇后