首页 > 代码库 > 八皇后问题
八皇后问题
八皇后问题
题目描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。 给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入描述:
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)
输出描述:
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
输入例子:
2
1
92
输出例子:
15863724
84136275
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 7 int C[50]; 8 vector<string> res; 9 char s[10];10 int cnt = 0;11 void find(int row) {12 int i, j;13 if(row == 8) {14 res.push_back(s);15 } else for(i = 0; i < 8; i++) {16 int ok = 1;17 C[row] = i;18 for(j = 0; j < row; j++)19 if(C[row] == C[j] || row-C[row] == j-C[j] || row+C[row] == j+C[j]) {20 ok = 0;21 break;22 }23 if(ok) {24 s[row] = i+‘1‘;25 find(row+1);26 }27 }28 }29 30 int main() {31 find(0);32 int n;33 cin>>n;34 while(n--){35 int m;36 cin>>m;37 cout<<res[m-1]<<endl;38 }39 return 0;40 }
八皇后问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。