八皇后问题

    八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果，事实上就是有92种解法

 

    初始状态下在一个8×8国际象棋盘上没有任何棋子（皇后），然后顺序在第1行、第2行、...、第8行上布放棋子（皇后）。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足皇后间不会出现相互“攻击”的现象，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局

 

提示

 

    用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，回复安放该棋子前的状态，试探本行的第j+1列

 

    在解题过程中，主要需要解决以一几个问题：

 

        冲突
          （1）列：规定每一列放一个皇后，不会造成列上的冲突
          （2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态
          （3）对角线：对角线有两个方向，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态

 

        数据结构的选择
          （1）数组A。A[I]表示第I个皇后放置的列，范围1...8
          （2）行冲突标记数组B。B[I]=0表示第I行空闲，B[I]=1表示第I行被占领，范围1...8
          （3）对角线冲突标记数组C、D。C[I-J+7]=0表示第(I-J)条对角线空闲，C[I-J+7]=1表示第(I-J)条对角线被占领，范围-7...+7；D[I+J]=0表示第(I+J)条对角线空闲，D[I+J]=1表示第(I+J)条对角线被占领，范围2...16

 

 

/*
 * eight queen problem
 *     This code snippet provides a recursive method to solve the eight-queen problem.
 *
 * @author: openspace
 * @date: 2009-05-09
 */

#include <iostream>

using namespace std;

const int SIZE = 8;

class EightQueen
{
public:
    EightQueen();
    ~EightQueen();

    void solve(int startRow);                // solve the eight-queen problem

    bool check(int row,int col) const;       // judge whether (row,col) can be selected
    void clear() const;                      // clear the board state and records
    void printBoard() const;                 // print the board layout

private:
    char *boardState;                        // chessboard
    int *rowRecords,                         // records whether each row or col has selected point
        *colRecords;        
    int *diagoal,                            // records whether a point is selected on the 
        *clinodiagoal;                       // corresponding (clino)diagoal line

    int count;                               // total answers
};

EightQueen::EightQueen()
{
    count = 0;    
    boardState = new char[SIZE * SIZE];        
    rowRecords = new int[SIZE];
    colRecords = new int[SIZE];
    diagoal = new int[2*SIZE - 1];
    clinodiagoal = new int[2*SIZE - 1];
    clear();
}

EightQueen::~EightQueen()
{
    delete[] boardState;
    delete[] rowRecords;
    delete[] colRecords;
    delete[] diagoal;
    delete[] clinodiagoal;
}

void EightQueen::clear() const
{
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < SIZE; j++)
            boardState[i*SIZE + j] = 'O';

    for (int i = 0; i < SIZE; i++) {
        rowRecords[i] = 0;
        colRecords[i] = 0;
    }

    int size = 2 * SIZE - 1;
    for (int i = 0; i < size; i++) {
        diagoal[i] = 0;
        clinodiagoal[i] = 0;
    }    
}

void EightQueen::solve(int startRow)
{
    if (startRow == SIZE) {
        count++;
        printBoard();
        return;
    }

    for (int col = 0; col < SIZE; col++)
        if (!check(startRow, col)) {
            boardState[startRow * SIZE + col] = '*';
            rowRecords[startRow] = 1;
            colRecords[col] = 1;
            diagoal[startRow+col] = 1;
            clinodiagoal[startRow-col+7] = 1;

            solve(startRow + 1);

            // reset the point just tested

            boardState[startRow * SIZE + col] = 'O';
            rowRecords[startRow] = 0;
            colRecords[col] = 0;
            diagoal[startRow+col] = 0;
            clinodiagoal[startRow-col+7] = 0;
        }
}

bool EightQueen::check(int row, int col) const
{
    return rowRecords[row] || colRecords[col] || diagoal[row+col] || clinodiagoal[row-col+7];
}

void EightQueen::printBoard() const
{
    static int rowPos[SIZE], colPos[SIZE];

    cout << "*******" << count << "th answer*******" << endl;
    cout << " ";
    for (int i = 0; i < SIZE; i++)
       cout << " " << i;
    cout << endl;

    for (int i = 0; i < SIZE; i++)    {    // print the board layout
        cout << i << " ";
        for (int j = 0; j < SIZE; j++) {
            cout << boardState[i*SIZE + j] << " ";
            if (boardState[i*SIZE + j] == '*') {
                rowPos[i] = i;
                colPos[i] = j;
            }
        }
        cout << endl;
    }
    cout << endl;

    for (int i = 0; i < SIZE; i++)    {    // print the points location
        cout << " (" << rowPos[i] << "," << colPos[i] << ") ";
        rowPos[i] = -1;
        colPos[i] = -1;
    }    
    cout << endl;
}

int main()
{
    EightQueen eightQueen;
    eightQueen.solve(0);

    system("pause");

    return 0;
}