八皇后问题是这样一个问题: 将八个皇后摆在一张 8*8 的国际象棋棋盘上, 使每个皇后都无法吃掉别的皇后, 一共有多少种摆法, 其中皇后是最强大的一枚棋子, 可以吃掉与其在同一行, 列和斜线的敌方棋子?
经典解法: 回溯法
- void queen(int row){
- if(row==n)
- total++;
- else
- for(int col=0;col!=n;col++){
- c[row]=col;
- if(is_ok(row))
- queen(row+1);
- }
- }
算法是逐行安排皇后的, 其参数 row 为现在正执行到第几行. n 是皇后数, 在八皇后问题里当然就是 8 啦.
第 2 行好理解, 如果程序当前能正常执行到第 8 行, 那自然是找到了一种解法, 于是八皇后问题解法数加 1.
如果当前还没排到第八行, 则进入 else 语句. 遍历所有列 col, 将当前 col 存储在数组 c 里, 然后使用 is_ok() 检查 row 行 col 列能不能摆皇后, 若能摆皇后, 则递归调用 queen 去安排下一列摆皇后的问题.
还不太清楚? 再慢点来, 刚开始的时候 row=0, 意思是要对第 0 行摆皇后了.
- #include<iostream>
- #include<math.h>
- using namespace std;
- int n=8;
- int total=0;
- int *c=new int(n);
- bool is_ok(int row){
- for(int j=0;j!=row;j++){
- if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
- return false;
- }
- return true;
- }
- void queen(int row){
- if(row==n)
- total++;
- else
- for(int col=0;col!=n;col++){
- c[row]=col;
- if(is_ok(row))
- queen(row+1);
- }
- }
- int main(){
- queen(0);
- cout<<total;
- return 1;
- }
来源: http://www.bubuko.com/infodetail-2748184.html