weixin_43113933
2020-07-05 23:21
采纳率: 92.1%
浏览 116

一个关于8皇后回溯递归,全局变量失效的超大疑惑?

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
bool d[16]= {0},b[9]= {0},c[16]= {0};
int sum=0,a[9];
int search(int);
int print();
int main()
{
    search(1);//从第1个皇后开始放置
}
int search(int i)
{
    int j;
    for (j=1; j<=8; j++)//每个皇后都有8位置(列)可以试放
        if ((!b[j])&&(!c[i+j])&&(!d[i-j+7]))//寻找放置皇后的位置
            //由于C++不能操作负数组,因此考虑加7
        {
            //放置皇后,建立相应标志值
            a[i]=j;//摆放皇后
            b[j]=1;//宣布占领第j列
            c[i+j]=1;//占领两个对角线
            d[i-j+7]=1;
            if (i==8)
            {

                print();//8个皇后都放置好,输出
            }
            else
                search(i+1);//继续递归放置下一个皇后
            b[j]=0;//递归返回即为回溯一步,当前皇后退出
            c[i+j]=0;
            d[i-j+7]=0;
        }
}
int print()
{
    int i;
    sum++;//方案数累加1
    cout<<"sum="<<sum<<endl;
    for (i=1; i<=8; i++)//输出一种方案
        cout<<setw(4)<<a[i];
    cout<<endl;
}
网上这个解决8皇后问题的,逻辑对的,现在问题是sum失效,并没有起到全局变量的效果,这点特别苦恼,没想明白。sum输出总是循环输出。前41种方案还在正常的累加统计,后面的就开始输出2了,此后又从1开始,循环,无规则。全局变量按道理就是单纯累加统计,不管是不是递归才是。特别苦恼,难道还有深层次的原因吗

sum=40
4 7 1 8 5 2 6 3
sum=41
4 7 3 8 2 5 1 6
sum=2
4 7 5 2 6 1 3 8
sum=1
4 7 5 3 1 6 8 2
sum=2
4 8 1 3 6 2 7 5
sum=3
4 8 1 5 7 2 6 3
sum=4
4 8 5 3 1 7 2 6
sum=5
5 1 4 6 8 2 7 3

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • 胖狗子修行之路 2020-07-06 11:45
    已采纳

    改成这样可以解决,具体原因我也懵逼了,蹲一个大佬

    int a[9], sum = 0;
    

    预测一波数组越界

    破案
    修改:

    c[17]= {0}
    

    即可
    原因:
    i 和 j都有可能取到8的值,c[i+j]越界
    验证

                if (i==8)
                {
                    cout << i << " " << j << endl;
                    print();//8个皇后都放置好,输出
                }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题