要可以输出所有的摆放方法的那种,并且可以有一个变量来统计一共有多少种方法。
在网上看了很多都是输出一种方法就结束了。
要完整版的,而且麻烦看清楚是C++!其他语言不要贴出来。介绍书籍的也别来了。
求C++的八皇后完整代码
答案:1 悬赏:20 手机版
解决时间 2021-04-04 12:27
- 提问者网友:精神病院里
- 2021-04-03 19:46
最佳答案
- 五星知识达人网友:洎扰庸人
- 2021-04-03 20:50
// 首先你需要这些全局变量
// =====================================================================
// queen[i] = j 意思是第i个皇后在 (i,j),每行1个皇后
vector queen(8, 0);
string line; // 每个解法的每一行的排布
vector chessboard(0); // 每种解法的排布
vector > AlltheSolutions(0); // 装所有解法的容器
// ======================================================================
// show() 记录每个解法
void show(){
chessboard.clear();
for(int i = 0; i < 8; ++i){
// '.' 是空地, 'Q' 是皇后的位置: "...Q...." 皇后在该行第4个位置
line.assign(8, '.');
line[queen[i]]='Q';
chessboard.push_back(line);
}
AlltheSolutions.push_back(chessboard);
}
// 判断该位置是否能放皇后
bool PLACE(int n){
for(int i = 0; i < n; i++) {
// 查是否同列和对角线,同行不用查,因为设置的时候就默认一行一个
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
return false;
}
return true;
}
// 回溯算法, 一行一行的摆
void NQUEENS(int n){
for(int i= 0; i < 8; i++){
queen[n] = i;
if(PLACE(n)){
if(n == 7) show(); // 并且已经是最后一个皇后了,把排布记录下来
else NQUEENS(n + 1); // 不是就摆下一行
}
}
}
vector > solveNQueens() {
NQUEENS(0);
return AlltheSolutions;
}
// =================================================================
int main(){
vector > result = solveNQueens();
int num = 0;
cout << "Total number of solutions is: " << result.size() << endl;
cout << "which solution you want to look into? (No bigger than " << result.size() << ") \nSolution No.";
cin >> num;
for (int i = 0; i != result[num].size(); ++i){
cout << result[num][i] << endl;
}
system("pause");
return 0;
}
// =====================================================================
// queen[i] = j 意思是第i个皇后在 (i,j),每行1个皇后
vector
string line; // 每个解法的每一行的排布
vector
vector
// ======================================================================
// show() 记录每个解法
void show(){
chessboard.clear();
for(int i = 0; i < 8; ++i){
// '.' 是空地, 'Q' 是皇后的位置: "...Q...." 皇后在该行第4个位置
line.assign(8, '.');
line[queen[i]]='Q';
chessboard.push_back(line);
}
AlltheSolutions.push_back(chessboard);
}
// 判断该位置是否能放皇后
bool PLACE(int n){
for(int i = 0; i < n; i++) {
// 查是否同列和对角线,同行不用查,因为设置的时候就默认一行一个
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
return false;
}
return true;
}
// 回溯算法, 一行一行的摆
void NQUEENS(int n){
for(int i= 0; i < 8; i++){
queen[n] = i;
if(PLACE(n)){
if(n == 7) show(); // 并且已经是最后一个皇后了,把排布记录下来
else NQUEENS(n + 1); // 不是就摆下一行
}
}
}
vector
NQUEENS(0);
return AlltheSolutions;
}
// =================================================================
int main(){
vector
int num = 0;
cout << "Total number of solutions is: " << result.size() << endl;
cout << "which solution you want to look into? (No bigger than " << result.size() << ") \nSolution No.";
cin >> num;
for (int i = 0; i != result[num].size(); ++i){
cout << result[num][i] << endl;
}
system("pause");
return 0;
}
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯