快速磨刀器原理:回溯法用堆栈实现八皇后问题；；悬赏20积分求解。

规则：设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第 2行，...第8行上布放棋子。在每一行中有8个可选位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘的同一行、同一列、或者同一斜线上。

解法：采用回溯法。在第n行第j列安放一个棋子时，需要纪录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。

#include
/* SIZE >= 4 时均有解,缺省定义8 */ #define SIZE 8
/* SIZE*SIZE棋盘 */ int chess[SIZE][SIZE] = {0};
/* 当前行/列是否越界 */ bool IsOut(int row,int col) { if(row >= 0 && row < SIZE && col >= 0 && col < SIZE) { return false; } else { return true; } }
bool queen(int n) { /* 递归终止条件 */ if(n == SIZE) { return true; } /* 遍历第n行 */ for(int j = 0; j < SIZE; j ++) { /* 假设在第n行j列放置一枚棋子 */ chess[n][j] = 1; /* 检验在"问题描述"中的三个条件 */ for(int k = 0; k < SIZE; k++) { /* 行扫描 */ if(k != j && chess[n][j] == chess[n][k]) { chess[n][j] = 0; } /* 列扫描 */ if(n != k && chess[n][j] == chess[k][j]) { chess[n][j] = 0; } /* 反斜线扫描 */ if(k!= 0 && !IsOut(n - k,j-k) && chess[n][j] == chess[n-k][j-k]) { chess[n][j] = 0; } if(k!= 0 && !IsOut(n + k,j+k) && chess[n][j] == chess[n+k][j+k]) { chess[n][j] = 0; } /* 正斜线扫描 */ if(k!= 0 && !IsOut(n - k,j+k) && chess[n][j] == chess[n-k][j+k]) { chess[n][j] = 0; } if(k!= 0 && !IsOut(n + k,j-k) && chess[n][j] == chess[n+k][j-k]) { chess[n][j] = 0; } } if(chess[n][j] == 1 && queen(n+1)) { /* 放置正确 */ return true; } else { /* 假设不成立 */ chess[n][j] = 0; } } return false; }
int main(int argc, char* argv[]) { queen(0); for(int i = 0; i < SIZE; i++) { for(int j = 0; j < SIZE; j++) { printf("%d ",chess[i][j]); } printf("\n"); } return 0; }

如里看不清请参考:
http://masterdog.bokee.com/140659.html

#include<iostream>
#include<iomanip>
#define EIGHT 8
#define TRUE 1
#define FALSE 0
using namespace std;
int queen[EIGHT];
int number=0;
int attack(int,int);
void print_table()
{ int x=0,y=0;
number+=1;
cout<<endl;
cout<<"八皇后的第"<<setw(2)<<number<<"组解"<<endl<<"\t";
for(x=0;x<EIGHT;x++)
{ for(y=0;y<EIGHT;y++)
if(x==queen[y])
cout<<"<*>";
else
cout<<"<->";
cout<<endl<<"\t";
}
system("pause");
}
void decide_position(int value)
{ int i=0;
while(i<EIGHT)
{ if(attack(i,value)!=1)
{ queen[value]=i;
if(value==7)
print_table();
else
decide_position(value+1);
}
i++;
}
}
int attack(int row,int col)
{ int i=0,atk=FALSE;
int offset_row=0,offset_col=0;
while((atk!=1)&&i<col)
{ offset_col=abs(i-col);
offset_row=abs(queen[i]-row);
if((queen[i]==row)||(offset_row==offset_col))
atk=TRUE;
i++;
}
return atk;
}
int main(void)
{ decide_position(0);
return 0;
}