八皇后递归详解
核心代码如下:
- // 八皇后递归解法
- #include<iostream>
- using namespace std;
- int queen[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};
- int count = 0;// 定义一个全局变量
- bool available(int pointi,int pointj) // 判断某个皇后是否与已有皇后冲突
- {
- for(int i = 1; i<pointi; i++)
- {
- if(pointj == queen[i])
- return false;// 同一列拒绝
- if((pointi-i) == (pointj-queen[i]))
- return false;// 同一主对角线拒绝
- if((pointi-i) + (pointj-queen[i]) == 0)
- return false;// 同一副对角线拒绝
- }
- return true;
- }
- void findSpace(int queenNumber) // 在第 queenNumber 行找能放皇后的位置
- {
- // 因为行数在递归中不断调用(即行数在递归一次取下一行), 所以只要遍历列的位置
- for(int i = 1; i<9; i++) // 从 1~8 遍历这一行的八个空位
- {
- if(available(queenNumber,i))
- {
- // 如果可以放这个位置就记录下第 queenNumber 个皇后的位置
- queen[queenNumber] = i;
- if(queenNumber == 8) // 如果八个皇后都放满了统计一下
- {
- count++;// 次数就增加一次
- return;
- }
- int nextNumber = queenNumber+1;// 还有皇后没放递归放下一个皇后(取下一行)
- findSpace(nextNumber);// 递归
- }
- }
- queen[--queenNumber] = -1;// 如果这一行没有可放的位置说明上一行皇后放的位置不行, 要为上一个皇后寻找新的可放位置(即就要重新再找一次)
- return;
- }
- int main()
- {
- findSpace(1);// 从 (1,1) 开始递归好理解
- cout <<count << endl;
- return 0;
- }
- View Code
八皇后问题可以不只是限制于八个皇后, 可以推广到 n 皇后问题, 下期介绍.
- // 八皇后递归解法(C 语言写法)
- //#include<iostream>
- //using namespace std;
- #include<stdio.h>
- int queen[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};
- int count = 0;// 定义一个全局变量
- bool available(int pointi,int pointj) // 判断某个皇后是否与已有皇后冲突
- {
- for(int i = 1; i<pointi; i++)
- {
- if(pointj == queen[i])
- return false;// 同一列拒绝
- if((pointi-i) == (pointj-queen[i]))
- return false;// 同一主对角线拒绝
- if((pointi-i) + (pointj-queen[i]) == 0)
- return false;// 同一副对角线拒绝
- }
- return true;
- }
- void findSpace(int queenNumber) // 在第 queenNumber 行找能放皇后的位置
- {
- // 因为行数在递归中不断调用(即行数在递归一次取下一行), 所以只要遍历列的位置
- for(int i = 1; i<9; i++) // 从 1~8 遍历这一行的八个空位
- {
- if(available(queenNumber,i))
- {
- // 如果可以放这个位置就记录下第 queenNumber 个皇后的位置
- queen[queenNumber] = i;
- if(queenNumber == 8) // 如果八个皇后都放满了统计一下
- {
- count++;// 次数就增加一次
- return;
- }
- int nextNumber = queenNumber+1;// 还有皇后没放递归放下一个皇后(取下一行)
- findSpace(nextNumber);// 递归
- }
- }
- queen[--queenNumber] = -1;// 如果这一行没有可放的位置说明上一行皇后放的位置不行, 要为上一个皇后寻找新的可放位置(即就要重新再找一次)
- return;
- }
- int main()
- {
- findSpace(1);// 从 (1,1) 开始递归好理解
- //cout << count << endl;
- printf("%d\n",count);
- return 0;
- }
C 写法
八皇后问题(递归方法详解)
来源: http://www.bubuko.com/infodetail-2866512.html