【题目链接】

ybt 1213：八皇后问题
OpenJudge NOI 2.5 1700:八皇后问题

【题目考点】

1. 深搜

【解题思路】

八皇后问题解法请参考：信息学奥赛一本通 1214：八皇后 | OpenJudge NOI 2.5 1756:八皇后

观察本题的输出，可以看出本题是按列放皇后得到的结果，先搜索将皇后放在第一列的位置，第一列的位置确定后再搜索将皇后放在第二列的位置。。。
设二维数组保存放皇后的状态，每当放完第8列，则输出一种合法的八皇后的情况。

另一种思路，仍然是按行放皇后，不过输出时输出保存放皇后情况的矩阵的转置。

【题解代码】

解法1：按列放皇后

#include <bits/stdc++.h>
using namespace std;
bool vis_c[10], vis_r[16], vis_l[16];//vis_c[i]:第i行是否被占用 vis_l[i]:第i右上左下斜线是否被占用 vis_r[i]:第i左上右下斜线是否被占用 
int mp[10][10], n;//mp[i][j]:是否有皇后 n:当前在输出第几个八皇后的情况 
//在位置x，y设置或拿开皇后后，对列、斜线占用情况的变化
void setVis(int x, int y, bool isSet)
{vis_c[x] = isSet;vis_r[x-y+8] = isSet;vis_l[x+y-1] = isSet;
}
//在第y列放皇后
void dfs(int y)
{for(int x = 1; x <= 8; ++x)//能否在第x行第y列放皇后{if(vis_c[x] == false && vis_r[x-y+8] == false && vis_l[x+y-1] == false)//如果(x,y)所在的列及斜线都没有被占用 {mp[x][y] = 1;setVis(x, y, true);//设置对列和斜线的占用 if(y == 8){++n;//情况编号加1cout << "No. " << n << endl;for(int i = 1; i <= 8; ++i){for(int j = 1; j <= 8; ++j)cout << mp[i][j] << ' ';cout << endl; }}elsedfs(y+1);setVis(x, y, false);//状态还原 mp[x][y] = 0;}}
}
int main()
{dfs(1);return 0;
}

解法2：按行放皇后，输出矩阵的转置

#include <bits/stdc++.h>
using namespace std;
bool vis_c[10], vis_r[16], vis_l[16];//vis_c[i]:第i列是否被占用 vis_l[i]:第i右上左下斜线是否被占用 vis_r[i]:第i左上右下斜线是否被占用 
int mp[10][10], n; 
//在位置x，y设置或拿开皇后后，对列、斜线占用情况的变化
void setVis(int x, int y, bool isSet)
{vis_c[y] = isSet;vis_r[x-y+8] = isSet;vis_l[x+y-1] = isSet;
}
//在第x行放皇后
void dfs(int x)
{for(int y = 1; y <= 8; ++y)//能否在第x行第y列放皇后{if(vis_c[y] == false && vis_r[x-y+8] == false && vis_l[x+y-1] == false)//如果(x,y)所在的列及斜线都没有被占用 {mp[x][y] = 1;setVis(x, y, true);//设置对列和斜线的占用 if(x == 8){cout << "No. " << ++n << endl;//输出编号 for(int j = 1; j <= 8; ++j)//输出mp矩阵的转置 {for(int i = 1; i <= 8; ++i)cout << mp[i][j] << ' ';cout << endl;}}elsedfs(x+1);setVis(x, y, false);//状态还原 mp[x][y] = 0;}}
}
int main()
{dfs(1);return 0;
}