【算法】 八皇后问题之回溯法

1. 八皇后问题描述

  会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

2. 解题思路

  每次填满第一行第一列，当不满足时候，试下第一行第二列，依次进行，递归的出口为找到第八个点，跳出递归。，在循环里面还要判断是否满足不同行，不同列，不同对角线。

  使用回溯法来解决该问题，下面的代码是我看到过的最精简的代码，相关的注释都写在代码上了。

#define QUEEN_NUM  8
int c[QUEEN_NUM] = {0};

bool is_ok(int row)
{
    for(int i=0;i<row;i++)
    {
        //判断列和斜对角是否有与之前的皇后冲突。
        if(c[row] == c[i] || abs(c[row]-c[i]) == row-i) return false;
    }
    return true;
}
int queue(int row)
{
    static unsigned char total = 0;  //total为所有八皇后解法的个数
    if(row == QUEEN_NUM)
    {
        total++;
    }else{
       for(int col = 0;col<QUEEN_NUM;col++)
       {
           c[row] = col;
           if(is_ok(row)) //该位置可以放置
           {
               queue(row+1);//放置下一行
           }
       }
    }
    return total;
}

int main()
{
    unsigned char total = queue(0);
    printf("total = %d\n",total);
    return 0;
}

运行得出结果，总共有92中结果。