题目描述
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数n。
输出格式
每个解决方案占n行,每行输出一个长度为n的字符串,用来表示完整的棋盘状态。
其中”.”表示某一个位置的方格状态为空,”Q”表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q..
…Q
Q…
..Q.
..Q.
Q…
…Q
.Q..
思路
1.利用全排列的方式,对于每一行,遍历的方式,选择某个列元素,使得列元素满足题目要求
2.利用贪心的方式, 对于每个格子,只有放下和不放下两种情况,对于放下皇后,又需要特判,
需要满足皇后放置的规则
对角公式:
斜对角线 有公式 y = x + b y = -x + b
利用截距b b = y - x b = y + x
来截距b标记在dg和udg中的唯一性。y-x可能为负数,视频中加n保证为正数,实际上加上n - 1 可以用变量记录两个对角的值,如下图
细节注释在代码中
java
import java.util.Scanner;
public class Main{
static int N = 20;
static int n;
static char[][] g = new char[N][N]; // 记录拜访皇后的地方
static boolean col[] = new boolean[N], dg[] = new boolean[N], udg[] = new boolean[N]; //检测列,对角线和斜对角线上是否有1
private static void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(g[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
/*
斜对角线 有公式 y = x + b y = -x + b
利用截距b b = y - x b = y + x
来标记在dg和udg中的唯一性。
*/
if (!col[i] && !dg[u + i] && !udg[u - i + n]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[u - i + n] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[u - i + n] = false;
g[u][i] = '.';
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
g[i][j] = '.';
}
}
dfs(0);
}
}
import java.util.Scanner;
public class Main{
static int N = 20;
static int n;
static char[][] g = new char[N][N]; // 记录拜访皇后的地方
static boolean row[] = new boolean[N], col[] = new boolean[N], dg[] = new boolean[N], udg[] = new boolean[N]; //检测列,对角线和斜对角线上是否有1
// 针对每一个格子,有放和不放, 从左上角(0,0) s记录皇后的数量
private static void dfs(int x, int y, int s) {
if (y == n) {
y = 0;
x ++;
}
if (x == n) {
if (s == n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(g[i][j]);
}
System.out.println();
}
System.out.println();
}
return;
}
// 不放则进入到同行的下一个格子
dfs(x, y + 1, s);
// 放
if (!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
dfs(x, y + 1, s + 1); // s在dfs代码块栈中,返回上一层的时候,s变回原有的数值,不需要再后续做s--
row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
g[x][y] = '.';
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
g[i][j] = '.';
}
}
dfs(0, 0, 0);
}
}
python
N = 20
g = [[0] * N for j in range(N)]
col, dg, udg = [False] * N , [False] * N, [False] * N
def dfs(u):
global n
if u == n:
for i in range(0, n):
for j in range(0, n):
print(g[i][j], end="")
print()
print()
return
for i in range(0, n):
if not col[i] and not dg[u + i] and not udg[u - i + n]:
g[u][i] = 'Q'
col[i] = dg[u + i] = udg[u - i + n] = True
dfs(u + 1)
col[i] = dg[u + i] = udg[u - i + n] = False
g[u][i] = '.'
def main():
global n
n = int(input())
for i in range(0, n):
for j in range(0, n):
g[i][j] = '.'
dfs(0)
if __name__ == '__main__':
main()
N = 20
g = [[0] * N for i in range(N)]
row, col, dg, udg = [False] * N, [False] * N, [False] * N, [False] * N
def dfs(x, y, s):
global n
if y == n:
y = 0
x += 1
if x == n:
if s == n:
for i in range(0, n):
for j in range(0, n):
print(g[i][j], end="")
print()
print()
return
# 不放
dfs(x, y + 1, s)
# 放
if not row[x] and not col[y] and not dg[x + y] and not udg[y - x + n]:
g[x][y] = 'Q'
row[x] = col[y] = dg[x + y] = udg[y - x + n] = True
dfs(x, y + 1, s + 1)
row[x] = col[y] = dg[x + y] = udg[y - x + n] = False
g[x][y] = '.'
def main():
global n
n = int(input())
for i in range(0, n):
for j in range(0, n):
g[i][j] = '.'
dfs(0, 0, 0)
if __name__ == '__main__':
main()
c++ 全排列
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N]; //检测列,对角线和斜对角线上是否有1
//全排列
void dfs(int u){
if(u == n){
for(int i = 0; i < n; i ++) puts(g[i]);
puts("");
return;
}
for(int i = 0; i < n; i ++){
/*
斜对角线 有公式 y = x + b y = -x + b
利用截距b b = y - x b = y + x
来截距b标记在dg和udg中的唯一性。y-x可能为负数,加n保证为正数
*/
if(!col[i] && !dg[u + i] && !udg[i - u + n]){ // u相当y i相当于x
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[i - u + n] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[i - u + n] = false;
g[u][i] = '.';
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
c++ 全排列
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; //检测列,对角线和斜对角线上是否有1
//贪心,对所有格子从左到右,从上到下的遍历,每个格子有两个状态,即放和不放皇后
void dfs(int x, int y, int s){ //(x,y)表示坐标位置,遍历每一个格子,s表示摆放Q的个数。
if(y == n) y = 0, x ++; //到了末尾,跳到下一行开头
if(x == n){
if(s == n){
for(int i = 0; i < n; i ++) puts(g[i]);
puts("");
}
return;
}
//不放皇后
dfs(x, y + 1, s); //跳过该格子
//放皇后
if(!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n]){
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
g[x][y] = '.';
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
g[i][j] = '.';
}
}
dfs(0, 0, 0);
return 0;
}