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

forrestlin

发布于 2018-05-23 17:53:30

7100

发布于 2018-05-23 17:53:30

文章被收录于专栏：蜉蝣禅修之道

近来无聊，想着几年前用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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2014年03月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法