回溯法与八皇后问题

1. 八皇后问题描述2. 解题思路

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中结果。