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)

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

最后，就剩下启动函数了

    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;
                }
            }
        }
    }

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

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

C++简单实现八皇后问题,布布扣,bubuko.com

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

原文：http://blog.csdn.net/xanxus46/article/details/21724453