八皇后之回溯法（C语言版）算法与数据结构

题目描述：八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。题目分析：显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1≤i≤n且1≤xi≤n，即第n个皇后放在第i行第xi列上。由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为: xi≠xj; 若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j = xi-xj; 在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj；综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为: |i-xi| ≠ |j-xj| 代码：

#include #include using namespace std; int x[100]; int num = 0; /* 考察皇后k放置在x[k]列是否会发生冲突 */ bool place(int k) { int i; //需要依次考虑第k行与其前面的已经放置好的皇后是否冲突 for( i = 1; i < k; i ++){ if( x[k] == x[i] || abs(k-i) == abs(x[k] - x[i])) return false; } return true; }void queen(int n) { int k; for(int i = 0; i <= n; i++ ) x[i] = 0; //初始化，开始每一列都没有皇后 k = 1; while( k >= 1){ x[k] ++; //在下一列放置第k个皇后 while( x[k] <= n && !place(k))//x[i]存放的是第i行应该放置的列值，每一个x[i]的取值应该是第一列到第n列 x[k] ++; //搜索下一列 //每次放置好一个皇后之后，判断一下是 if( x[k] <= n &&k == n){//第n行的皇后也放置好了，说明每一个皇后都放在了可以的位置，得到一个输出 num ++ ; //for(int i = 1; i <= n; i++) // cout << x[i] << endl; } else if(x[k] <= n && k < n) k ++; //放置下一个的皇后 else {// k行的皇后没有找到合适的位置，回溯 x[k] = 0; k --; } } } int main() { int n; cout << "输入皇后个数：\n" << endl; cin >> n; queen(n); cout<< num; return 0; }

转自：http://qbview.url.cn/getResourceInfo?appid=31&url=http%3A%2F%2Fwww.cnblogs.com%2Fqinyg%2Farchive%2F2012%2F05%2F21%2F2512353.html%3Fnsukey%3DOJQQTpWOuIp2prnBw2VYroIRElk6TKcYZxk5u0Snu882Zxcq13dx4ioWyZ68AyuqhcHBLZNDgBYdbMg26C5ClGmv5Y1v6ZXgHPNcuu7K1rDIfHI4RD5yzfrpiD6hF2cGIN9VY7UyASDeo1LgkGmbbMw%252F4FIZICBc%252BUoYBvn2BzfT2feZfUmGmyBOqONYvjtM&version=10000&doview=1&ua=Mozilla%2F5.0+(Macintosh%3B+Intel+Mac+OS+X+10_11_6)+AppleWebKit%2F601.7.7+(KHTML%2C+like+Gecko)+Version%2F9.1.2+Safari%2F601.7.7&keeplink=0&reformat=0