说明:西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八
个皇后如何相安无事的放置在棋盘上,1970年与1971年, E.W.Dijkstra与N.Wirth曾经用这个问 题来讲解程式设计之技巧。
解法关于棋盘的问题, 都可以用递回求解, 然而如何减少递回的次数?在八个皇后的问题,中
不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用再检查了,这个方 法称为分支修剪。
#include <iostream> #include <cmath> #include <cstring> using namespace std; int queen[9]; //数组初始化 void init() { memset(queen,0,9*sizeof(int)); } //输出结果 void print() { for(int i=1; i<9; i++) cout<<queen[i]<<" "; cout<<endl; } //剪枝函数 bool canPlaceQueen(int k) { for(int i = 1; i < k; i++) { //判断是否处于同一列或同一斜线 if(queen[i] == queen[k] || abs(k-i) == abs(queen[k]-queen[i])) return false; } return true; } //迭代方法求解八皇后过程 void eightQueen_1() { int k = 1; while(k>=1) { while(queen[k]<=7) { queen[k] += 1; if(k == 8 && canPlaceQueen(k)) { print(); } else if(canPlaceQueen(k)) { k++; } } queen[k] = 0; k--; } } //递归方法求解八皇后过程 void eightQueen_2(int k) { for(int i=1; i<9; i++) { queen[k] = i; if(k == 8 && canPlaceQueen(k)) { print(); return; } else if(canPlaceQueen(k)) { eightQueen_2(k+1); } } } int main() { init(); eightQueen_1(); // eightQueen_2(1); return 0; }