八皇后问题(递归&非递归)

VC6.0下编译通过。

递归解法

#include<iostream>
using namespace std;

class ChessBoard {
public:
    ChessBoard(); //8*8 chessboard

    ChessBoard(int); //n*n chessboard

    void findSolutions();
private:
    const bool available; //初始化位置 合法性

    const int squares; //边长

    bool *column,*leftDiagonal,*rightDiagonal; //存放 列、左斜线、右斜线 合法性

    int howMany; //解法记数

    int *positionInRow; //每行中的queen位置（col值）

    void putQueen(int); //放置queen

    void printBoard(); //打印棋盘

    void initializeBoard(); //初始化棋盘

};

ChessBoard::ChessBoard() : available(true),squares(8) {
    initializeBoard();
}

ChessBoard::ChessBoard(int n) : available(true),squares(n) {
    initializeBoard();
}

void ChessBoard::initializeBoard() {
    register int i;
    column=new bool[squares];
    positionInRow=new int[squares];
    leftDiagonal=new bool[squares*2-1]; //一共有[squares(边长)*2-1]条左右斜线

    rightDiagonal=new bool[squares*2-1]; //左斜线可以用[row+col(下标)]区分，右斜线可以用[row-col+(squares-1)]区分

    for(i=0; i<squares; i++)
    {
        positionInRow[i]=-1;
    }
    for(i=0; i<squares; i++)
    {
        column[i]=available;
    }
    for(i=0; i<squares*2-1; i++)
    {
        leftDiagonal[i]=rightDiagonal[i]=available;
    }
    howMany=0;
}

void ChessBoard::putQueen(int row) {
    for(int col=0; col<squares; col++)
        if(column[col]==available && leftDiagonal[row+col]==available && rightDiagonal[row-col+(squares-1)]==available)
        {
            positionInRow[row]=col; //记录queen放置的位置

            column[col]=!available;
            leftDiagonal[row+col]=!available;
            rightDiagonal[row-col+(squares-1)]=!available;
            if(row < squares-1)
                putQueen(row+1); //递归放置下一行queen

            else //row > squares-1

            {
                howMany++; //找到一个解,howMany递增

                printBoard(); //结束，打印结果

            }
            column[col]=available; //当某行找不到可放置位置时需回溯，则应先将当前位置设为可放置（合法）

            leftDiagonal[row+col]=available; //当找到一个解（row=7）递归由深到浅一层层结束，将每层放置queen的位置设为可放置（合法）,

            rightDiagonal[row-col+(squares-1)]=available; //到递归结束时，棋盘所有位置均为合法，这样才可以进行下一轮(col++)的解法查找。

        }
}

void ChessBoard::findSolutions() {
    putQueen(0);
    cout<<howMany<<" solutions found.\n";
}

void ChessBoard::printBoard() {
    for(int row=0; row<squares; row++)
    {
        for(int col=0; col<squares; col++)
        {
        if(positionInRow[row] == col)
            cout<<'Q';
        else
            cout<<'.';
        }
        cout<<'\n';
    }
    cout<<endl<<endl<<endl;
}

void main()
{
    ChessBoard *chessboard = new ChessBoard();
    chessboard->findSolutions();
}