Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
SampleInput
1 8 5 0
SampleOutput
1 92 10
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int map[20][20]; //棋盘 6 int ans[20]={0},num,n; //n为输入的数，num为结果，ans[n]存储结果 7 8 void dfs(int x,int y) 9 { 10 if(map[x][y]) //如果标记不是0的话，证明不可放，回朔到上一种情况 11 return; 12 int i,xx,yy; 13 if(x==n) //如果已经放好n个棋子，证明这是一个可行解，可行解个数加一，回朔到上一种情况 14 { 15 num++; 16 return; 17 } 18 //对8个方向进行搜索，把(x,y)所在横排，竖排，斜排上面的元素全部标记为非0 19 xx=x;yy=y; 20 while(xx>0) map[xx--][yy]++; //左 21 xx=x;yy=y; 22 while(yy>0) map[xx][yy--]++; //下 23 xx=x;yy=y; 24 while(xx<=n) map[xx++][yy]++; //右 25 xx=x;yy=y; 26 while(yy<=n) map[xx][yy++]++; //上 27 xx=x;yy=y; 28 while(xx<=n&&yy<=n) map[xx++][yy++]++; //右上 29 xx=x;yy=y; 30 while(xx<=n&&yy>0) map[xx++][yy--]++; //右下 31 xx=x;yy=y; 32 while(xx>0&&yy<=n) map[xx--][yy++]++; //左上 33 xx=x;yy=y; 34 while(xx>0&&yy>0) map[xx--][yy--]++; //左下 35 36 for(i=1;i<=n;i++) 37 { 38 dfs(x+1,i); //棋子序号加一，棋子横坐标变为x+1(因为当x处有棋子时，横坐标为x都标记为非0) 39 //然后依次增加纵坐标y，找到一个标记位为0的位置(如果非0则返回，继续查找) 40 //如果找到了，则继续重复这一步。 41 } 42 43 //如果没找到，则恢复原样[把由(1,1)推出的map[][]上的标记恢复) 44 //并返回到set();中，继续执行set();中的j层循环，把初始值设为(1,2)[2即为j+1],重复执行上述步骤。 45 xx=x;yy=y; 46 while(xx>0) map[xx--][yy]--; 47 xx=x;yy=y; 48 while(yy>0) map[xx][yy--]--; 49 xx=x;yy=y; 50 while(xx<=n) map[xx++][yy]--; 51 xx=x;yy=y; 52 while(yy<=n) map[xx][yy++]--; 53 xx=x;yy=y; 54 while(xx<=n&&yy<=n) map[xx++][yy++]--; 55 xx=x;yy=y; 56 while(xx<=n&&yy>0) map[xx++][yy--]--; 57 xx=x;yy=y; 58 while(xx>0&&yy<=n) map[xx--][yy++]--; 59 xx=x;yy=y; 60 while(xx>0&&yy>0) map[xx--][yy--]--; 61 } 62 63 void set() //分别找到n为1到10的所有结果，并存到ans[i]中 64 { 65 int i,j; 66 for(i=1;i<=10;i++) 67 { 68 num=0;n=i; 69 for(j=1;j<=i;j++) 70 { 71 memset(map,0,sizeof(map)); 72 dfs(1,j); //增加初始棋子的y坐标 73 } 74 ans[i]=num; 75 } 76 } 77 78 79 int main(){ 80 int t; 81 set(); 82 while(cin>>n,n) 83 { 84 cout<<ans[n]<<endl; 85 } 86 87 return 0; 88 }
遍历过程：
x轴↓ y轴→
