八皇后问题递归解答~

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

直接看代码~虽然比较弱~但是思路还是满清晰的~

#include <iostream>
using namespace std;

int A[8]; //A[s]=t; 代表:第s行的第t列有皇后,s和t的取值范围是[0,7]
int num; //num:代表总的解法数

bool IsCorrect (int, int);

void EightQueen (int); //递归

int main ()
{
EightQueen (0);
cout << "num = " << num << endl;

return 0;
}

/* 判断在第row行的第column列放皇后是否可行,即判断
   该行的皇后是否会和第0行到第row-1行的皇后冲突*/
bool IsCorrect (int row, int column)
{
        for (int i = 0; i < row; ++i)
        {
                //条件1判断是否和以前的皇后在同一行上,条件2、3判断是否和以前的皇后在同一对角线上
                if (column == A[i] || row + column == i + A[i] || (row – i == column – A[i]))
                {
                        return false;           //发生冲突,不可行
                }
        }
        return true;
}

/* 求解八皇后问题的递归函数
   row: 代表行一共从0到7共8行*/
void EightQueen (int row)
{
        int column;
        for (column = 0; column < 8; ++column)
        {
                A[row] = column;                //代表第row行的第column列放皇后
                if (IsCorrect (row, column))    //判断在第row行的第column列放皇后是否可行
                {
                        if (row == 7)           //若可行,且若row已到达最后一行,则++num
                        {
                                ++num;
                                return;                 //此行很重要,无此行时num竟为7!可能因为无此行时下面的EightQueen(row+1)本不该执行,但却执行了,导致错误
                        }
                        EightQueen (row + 1);
                }
        }
}

Xushine

484