题目描述
n 皇后
java 代码
解法一
import java.util.*;
import java.io.*;
class Main{
static int n;
static char[][] b;
static boolean[] c, gc,ugc;
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(b[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
for(int i = 0; i<n;i++){
// i是列 u 是行
//gc b = y+x ugc = y-x; + n是因为 y-x可能是负数.
if(!c[i] && !gc[i+u] && !ugc[i-u+n]){
b[u][i] = 'Q';
c[i] = true;
gc[i+u] = true;
ugc[i-u+n] = true;
dfs(u+1);
c[i] = false;
gc[i+u] = false;
ugc[i-u+n] = false;
b[u][i] = '.';
}
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
b = new char[n][n];
c = new boolean[20];
gc = new boolean[20];
ugc = new boolean[20];
for(int i = 0; i< n ; i++){
for(int j = 0;j<n; j++){
b[i][j] = '.';
}
}
dfs(0);
}
}
解法二
import java.util.*;
import java.io.*;
class Main{
static int n;
static char[][] b;
static boolean[] c,r, gc,ugc;
// s 是放了几个皇后
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(b[i][j]);
}
System.out.println();
}
System.out.println();
}
return;
}
//不放皇后.
dfs(x, y+1, s);
//放皇后
if(!r[x] && !c[y] && !gc[x+y] &&! ugc[x-y+n]){
r[x] = c[y] = gc[x+y] = ugc[x-y+n] = true;
b[x][y] = 'Q';
dfs(x, y+1, s+1);
r[x] = c[y] = gc[x+y] = ugc[x-y+n] = false;
b[x][y] = '.';
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
b = new char[n][n];
c = new boolean[20];
r = new boolean[20];
gc = new boolean[20];
ugc = new boolean[20];
for(int i = 0; i< n ; i++){
for(int j = 0;j<n; j++){
b[i][j] = '.';
}
}
dfs(0,0,0);
}
}