搜索方式1,耗时较高
import java.io.*;
import java.util.*;
class Main {
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static int n,cnt;
static char[][] p = new char[10][10];
static boolean[] row = new boolean[10];
static boolean[] col = new boolean[10];
static boolean[] fan = new boolean[20];
static boolean[] zheng = new boolean[20];
static void dfs(int x, int y) throws IOException {
if (cnt == n) {
for (int i = 1; i<=n; i++) {
for (int j = 1; j<=n; j++) out.write(p[i][j]);
out.write('\n');
}
out.write('\n');
return;
}
if (y>n) {y=1;x++;}
if (x>n) return;
if (!row[x] && !col[y] && !zheng[x+y] && !fan[y-x+n]) {
p[x][y] = 'Q';
row[x] = col[y] = zheng[x+y] = fan[y-x+n] = true;
cnt++;
dfs(x,y+1);
row[x] = col[y] = zheng[x+y] = fan[y-x+n] = false;
cnt--;
p[x][y] = '.';
}
//else //一开始这里多写了个else,导致出不来结果,写else的话意味着当前顶点可以放置就必须放置,实际逻辑应该是可以选择不放置
dfs(x,y+1);
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
n = in.nextInt();
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) p[i][j] = '.';
dfs(1,1);
out.flush();
out.close();
osw.close();
}
}
搜索方式2,优于第一种
import java.util.*;
import java.io.*;
class Main {
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static int n;
static char[][] g = new char[10][10];
static boolean[] col = new boolean[10];
static boolean[] dg = new boolean[20];
static boolean[] udg = new boolean[20];
static void dfs(int x) throws IOException {
if (x == n+1) {
for (int i = 1; i<=n; i++) {
for (int j = 1; j<=n; j++) out.write(g[i][j]);
out.write('\n');
}
out.write('\n');
return;
}
for (int y = 1; y<=n; y++) {
if (!col[y] && !dg[n+y-x] && !udg[x+y]) {
g[x][y] = 'Q';
col[y] = dg[n+y-x] = udg[x+y] = true;
dfs(x+1);
col[y] = dg[n+y-x] = udg[x+y] = false;
g[x][y] = '.';
}
}
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
n = in.nextInt();
in.close();
for (int i = 1; i<=n; i++)
for (int j = 1; j<=n; j++) g[i][j] = '.';
dfs(1);
out.flush();
out.close();
osw.close();
}
}