AcWing 1621. N 皇后问题
原题链接
简单
作者:
张妈
,
2024-01-14 13:53:13
,
所有人可见
,
阅读 30
样例
//
// Created by asdfsa on 2024/1/13.
//
//会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
//Input
//一个整数n( 1 < = n < = 10 )
//Output
//每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出“no solute!”
//Sample Input Copy
//4
//Sample Output Copy
//2 4 1 3
//3 1 4 2
//python 解法
//
/*
def solveNQueens(n):
def could_place(row, col):
return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])
def place_queen(row, col):
queens.add((row, col))
cols[col] = 1
hill_diagonals[row - col] = 1
dale_diagonals[row + col] = 1
def remove_queen(row, col):
queens.remove((row, col))
cols[col] = 0
hill_diagonals[row - col] = 0
dale_diagonals[row + col] = 0
def add_solution():
solution = []
for _, col in sorted(queens):
solution.append(str(col + 1))
output.append(" ".join(solution))
def backtrack(row = 0):
for col in range(n):
if could_place(row, col):
place_queen(row, col)
if row + 1 == n:
add_solution()
else:
backtrack(row + 1)
remove_queen(row, col)
cols = [0] * n
hill_diagonals = [0] * (2 * n - 1)
dale_diagonals = [0] * (2 * n - 1)
queens = set()
output = []
backtrack()
return output if output else ["no solution!"]
# Test the function with n = 4
print(solveNQueens(4))
* */
#include <bits/stdc++.h>
std::vector<int> cols, right_rx, left_rx;
std::vector<std::string> output;
std::map<int,int> queen;
int n=0;
// 置空集合里面的所有数组, 恢复放置八皇后的状态
int remove_queen (int row,int col) {
queen.erase(row);
cols[col]=0;
right_rx[row-col+n-1]=0;
left_rx[row+col]=0;
}
// 添加当前的最优解到output里面
int add_output (){
std::string bf;
for (int i = 0; i < n; ++i) {
bf+=(std::to_string(queen[i]+1) + ' ');
}
output.push_back(bf);
}
//放棋子
int place_queen (int row, int col) {
//放置状态
queen[row]=col;
// 设置 左上角到右下角的数组 右上角到左下角的数组 还有 一行
// 放上一个棋子都会被占用
cols[col] = 1;
right_rx[row-col+n-1]=1;
left_rx[row+col]=1;
}
int backtrack (int row) { // row 为 0
for (int col = 0; col < n; ++col) {
if (! (cols[col] || right_rx[row-col+n-1]/* 放置出现不好的情况*/ || left_rx[row+col])) { //判断这个位置可不可以放棋子 , 如果之和为0说明还是可以放棋子的,没放过棋子
//开始放棋子
place_queen(row, col);
if (row +1==n) {// 到达截至条件, 就是 row+1的情况 等于边长;说明遍历完了row
add_output();
} else {
backtrack(row+1);
}
remove_queen(row, col);
}
}
}
int main () {
std::cin >>n;
for (int i = 0; i <n; ++i) {
cols.push_back(0);
}
for (int i = 0; i < 2*n-1; ++i) {
right_rx.push_back(0);
left_rx.push_back(0);
}
backtrack(0);
std::cout << output[0] << std::endl;
}