鱼C论坛

 找回密码
 立即注册
查看: 1957|回复: 7

求助、八皇后问题,运行不出结果

[复制链接]
发表于 2021-10-23 17:25:11 | 显示全部楼层 |阅读模式

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

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

x

求助、八皇后问题,运行不出结果
#include <stdio.h>
#include <stdlib.h>

typedef int bool;
#define true 1
#define false 0
int num=0;
char m[8][8]={'*'};


bool Check(int row,int column){
        int i,j;
        if(row==1)return true;
        for(i=0;i<=row-2;i++){
                if(m[i][column-1]=='Q')return false;
        }
        i=row-2;
        j=i-(row-column);
        while(i>=0&&j>=0)
        {
                if(m[i][j]=='Q')return false;
                i--;
                j--;
        }
        i=row-2;
        j=row+column-i+2;
        while(i>=0&&j<=7){
                if(m[i][j]='Q')return false;
                        i--;
                        j++;
        }
        return true;
}
void Output(void){
        int i,j;
        num++;
        printf("可行解%d:\n",num);
        for(i=0;i<8;i++){
                for(j=0;j<8;j++){
                        printf("%c",m[i][j]);
                }
                printf("\n");
        }
}
void EightQueen(int row){
        int j;
        for(j=0;j<8;j++){
                m[row-1][j]='Q';
                if(Check(row,j+1)==true){
                        if(row==8)Output();
                        else EightQueen(row+1);
                }
                m[row-1][j]='*';
        }
}
void main(void){
        EightQueen(1);
}
















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

使用道具 举报

发表于 2021-10-23 18:43:26 | 显示全部楼层
本帖最后由 jhq999 于 2021-10-23 18:47 编辑
  1. if(m[i][j]='Q')return false;
  2.                         i--;
  3.                         j++;
复制代码
  1. if(m[i][j]=='Q')return false;//是==不是=
复制代码

建议以后先写值后写变量:
  1. if('Q'==m[i][j])return false;//是==不是=
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-23 18:59:23 | 显示全部楼层
  1. #include <stdio.h>
  2. #define QUEENS 8
  3. #define IS_OUTPUT 1

  4. int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1];
  5. int inc, * a = A, * b = B + QUEENS, * c = C;
  6. void lay(int i) {
  7.     int j = 0, t, u;

  8.     while (++j <= QUEENS)
  9.         if (a[j] + b[j - i] + c[j + i] == 0) {
  10.             k[i][j] = a[j] = b[j - i] = c[j + i] = 1;
  11.             if (i < QUEENS) lay(i + 1);
  12.             else {
  13.                 ++inc;
  14.                 if (IS_OUTPUT) {
  15.                     for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))
  16.                         for (t = QUEENS + 1; --t; ) k[t][u] ? printf("Q ") : printf("+ ");
  17.                     printf("\n\n\n");
  18.                 }
  19.             }
  20.             a[j] = b[j - i] = c[j + i] = k[i][j] = 0;
  21.         }
  22. }

  23. int main(void) {
  24.     lay(1);
  25.     printf("%d皇后共计%d个解\n", QUEENS, inc);
  26.     return 0;
  27. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-23 19:14:18 | 显示全部楼层

不写注释都是耍流氓
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-23 19:52:10 | 显示全部楼层
jhq999 发表于 2021-10-23 19:14
不写注释都是耍流氓

是全部都不懂呢?还是某些代码不懂?都是些基础代码,没有用到任何深入复杂代码啊?如果是全部都不懂,温馨建议从零学起,如果只是思路不明白,可以共同学习。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-23 20:08:57 | 显示全部楼层
傻眼貓咪 发表于 2021-10-23 19:52
是全部都不懂呢?还是某些代码不懂?都是些基础代码,没有用到任何深入复杂代码啊?如果是全部都不懂,温 ...

开个玩笑
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-23 20:15:40 | 显示全部楼层
  1. #include <stdio.h>
  2. #define QUEENS 8

  3. int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1]; // 定义棋盘大小,用于存储皇后位置
  4. int inc, * a = A, * b = B + QUEENS, * c = C; // 定义棋盘边界大小(b 比原棋盘大,主要是为了方便出界计算)

  5. void lay(int i)
  6. {
  7.     int j = 0, t, u;
  8.     while (++j <= QUEENS) // j 为预设所有皇后位置
  9.         if (a[j] + b[j - i] + c[j + i] == 0){
  10.             
  11.             k[i][j] = a[j] = b[j - i] = c[j + i] = 1; // 真正皇后位置,1 表示该位置存在皇后,0表示该位置不存在皇后
  12.             
  13.             if (i < QUEENS) lay(i + 1); // 递归函数,参数 i+1,计算出新可能
  14.             else
  15.             {
  16.                 ++inc; // 多少个解法
  17.                
  18.                 /*----------------- 开始打印结果 -----------------*/
  19.                 for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))
  20.                 for (t = QUEENS + 1; --t; )
  21.                 k[t][u] ? printf("Q ") : printf("+ "); // 棋盘位置,Q 表示该位置存在皇后,+ 表示该位置为空
  22.                 printf("\n\n\n");
  23.             }
  24.             a[j] = b[j - i] = c[j + i] = k[i][j] = 0; // 如果位置不符合皇后,则赋值 0,继续循环下一个位置
  25.         }
  26. }

  27. int main(void) {
  28.     lay(1); // 从位置 1 开始预设所有皇后位置
  29.     printf("%d皇后共计%d个解\n", QUEENS, inc);
  30.     return 0;
  31. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-24 10:25:06 | 显示全部楼层
本帖最后由 桃花飞舞 于 2021-10-24 11:02 编辑

抱歉没看你的代码,我来讲下思路吧下来的图
8.png


图上面只考虑当前皇后一下面一半的因为有一半还没有放皇后,也就是说只考虑左下、正下、右下三个方向。
说白了就是一个递归的思想。xxx那行的弯曲箭头是考虑当前行不能放皇后,就回到上一行的情况。
下面是代码
------------------------------------------------------------------
  1. #include <stdio.h>
  2. #include <string.h>
  3. #define N 8

  4. typedef struct _tag_Pos
  5. {

  6.         int ios;
  7.         int jos;
  8. }Pos;

  9. static char board[N+2][N+2];
  10. static Pos pos[]={{-1,-1},{-1,0},{-1,1}};
  11. static int count=0;

  12. void init()    //初始化棋盘
  13. {       
  14.         int i = 0;
  15.         int j = 0;
  16.         for( i=0; i<N+2; i++)
  17.         {
  18.                 board[0][i] = '#';
  19.                 board[N+1][i] = '#';
  20.                 board[i][0] = '#';
  21.                 board[i][N+1] = '#';
  22.         }
  23.         for ( i=1; i<=N; i++)
  24.         {
  25.                 for (j=1; j<=N; j++)
  26.                 {
  27.                         board[i][j] = ' ';
  28.                 }
  29.         }
  30. }

  31. int check(int i, int j) //核对有没有和别的皇后冲突
  32. {
  33.         int ret =1;
  34.         int p = 0;

  35.         for (p=0;p<3;p++)
  36.         {
  37.                 int ni = i;
  38.                 int nj = j;

  39.                 while( ret && (board[ni][nj]) != '#')
  40.                 {
  41.                         ni = ni + pos[p].ios;
  42.                         nj = nj + pos[p].jos;

  43.                         ret = ret && (board[ni][nj] != '*');
  44.                 }
  45.         }
  46.         return ret;
  47. }

  48. void display()   //显示出棋盘和皇后的结果
  49. {
  50.         int i = 0;
  51.         int j = 1;
  52.        
  53.         for(i=0; i<N+2; i++)
  54.         {
  55.                 for (j=0;j<N+2;j++)
  56.                 {
  57.                         printf("%c", board[i][j]);
  58.                 }
  59.                 printf("\n");
  60.         }
  61. }



  62. void find(int i)  //如果i>N就是到了棋盘边界,就display()显示出结果,否则就继续查找新的结果
  63. {
  64.         int j = 0;

  65.         if ( i> N )
  66.         {
  67.                 count++;
  68.                
  69.                 printf("Solution: %d\n", count);

  70.                 display();

  71.                 getchar();
  72.         }
  73.         else
  74.         {
  75.                 for(j=1; j<=N; j++)
  76.                 {
  77.                         if( check(i, j) )
  78.                         {
  79.                                 board[i][j] = '*';

  80.                                 find(i+1);

  81.                                 board[i][j] = ' ';
  82.                         }
  83.                 }
  84.         }
  85. }


  86. int main()
  87. {
  88.         init();
  89.        
  90.         find(1);
  91.         return 0;
  92. }
复制代码

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

使用道具 举报

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

本版积分规则

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

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

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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