专栏首页蜉蝣禅修之道C++简单实现八皇后问题

C++简单实现八皇后问题

近来无聊,想着几年前用c#实现的八皇后,是参考网上的答案,如今过了几年,想试试有没进步,用c++简单地实现。

八皇后问题,是回溯算法的经典例子,它的规则要求是同一行同一列同一条斜线不能有两个皇后,不然会相互攻击。这条件听上去不难吧,可运算量却是惊人的多啊。

首先,程序是算法加数据结构,我这程序的数据结构是一个8*8的整型矩阵chessboard,全部初始化为0,这作为棋盘,每一格若为0则代表可以放棋子,另外还有一个长度为8的整型数组path,记录一次成功的排列,path[i]代表第i行棋子的位置。

然后,本程序有两个关键函数,

void setTrap(int*chessboard,int row,int column,int boardLength,char value)

该函数的含义是在row行column列放置棋子,并在同一行同一列同一斜线的格子加上value。

bool retreat(int*chessboard,int* path,int row,int boardLength)

该函数的含义是回退,在row行回退,返回是否成功,步骤是首先把当前行走的那一步撤销,然后再往前探测是否有可走的格子(value为0),若达到该行的尽头还没找到,返回false。

最后,就剩下启动函数了

    for (int i=0; i<board_length; i++) {
        for (int j=0; j<board_length; j++) {
            if(chessboard[i*board_length+j]==0){
                chessboard[i*board_length+j]=i+board_length;
                setTrap(chessboard, i, j, board_length,i+board_length);
                path[i]=j;
                break;
            }
            else if (j==board_length-1) {
                for (int k=i; k>0; k--) {
                    if (retreat(chessboard, path, k-1, board_length)) {
                        j=-1;
                        i=k;
                        break;
                    }
                }
            }
        }
        if (i==board_length-1&&path[board_length-1]!=-1) {
            //succeed to get one solution
            for (int i=0; i<board_length; i++) {
                cout<<path[i]<<" ";
            }
            solutionCount++;
            cout<<endl;
            for (int k=i; k>=0; k--) {
                if (retreat(chessboard, path, k, board_length)) {
                    i=k;
                    break;
                }
            }
        }
    }

本算法并未考虑棋盘旋转的情况,所以有不少重复的布局,故8*8的棋盘会有190中排列方式。

至此,本算法大体结束了,完整代码地址:http://download.csdn.net/detail/xanxus46/7078239

一段时间以后重新做回以前不会的算法,收获还是不少的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android之本地文件夹实时检测与上传服务实现

    forrestlin
  • ns-3构建简单点对点网络

    forrestlin
  • Android禁止横屏竖屏切换

    forrestlin
  • ASP获取微信小程序的OpenID服务器端代码

    尝试一下新鲜事物“微信小程序”,其中有一个业务场景,通过微信登陆小程序,这样需要获取小程序的用户ID(也就是openid)。微信小程序从安全角度考虑,不提供直接...

    疯狂的小程序
  • Eclipse上通过Pydev使用python

    转载自:http://www.cnblogs.com/linzhenjie/articles/2639113.html

    晓歌
  • sed uniq sort 实例

    这里使用-e,可以使用多个规则,发现sip,host,uri等替换成了—-,再次删除即可

    dogfei
  • 送Android大会200元优惠券

    2018安卓巴士开发者大会,是中国最具前沿性、专业性的安卓技术会议。由安卓巴士技术社区首次发起并组织的安卓线下交流大会,集结500位安卓开发,与你一起交流学习,...

    用户1269200
  • python文件名与包名冲突

    起因 不久前,写脚本的时候遇到了这个问题,在编写jira相关脚本的时候,上头让脚本名称为jira.py,但是使用的包JIRA里也有叫jira的子项,导致冲突,需...

    98k
  • Android Shader应用开发之霓虹闪烁文字效果

    本文实例为大家分享了Android霓虹闪烁文字效果的具体代码,供大家参考,具体内容如下

    砸漏
  • 74-递归函数练习:逐级列出目录内容

    凯茜的老爸

扫码关注云+社区

领取腾讯云代金券