/**
* 如何判断是否是对角线，对应坐标相减结果绝对值相等则对角线: Math.abs(x1 - x2) == Math.abs(y1 - y2);
*/
N皇后第一版代码：性能较差，但是完全由自己写粗来的，基于此版本优化：
package com.javartisan.redpacket; import java.util.ArrayList; import java.util.HashSet; import java.util.List; /** * 如何判断是否是对角线，对应坐标相减结果绝对值相等则对角线: Math.abs(x1 - x2) == Math.abs(y1 - y2); */ class Solution { public static List<List<String>> solveNQueens(int n) { List<List<String>> ans = new ArrayList<>(); byte[][] mtx = new byte[n][n]; ArrayList<String> an = new ArrayList<>(); for (int i = 0; i < n; i++) { an.add(""); } trace(ans, an, n, n, mtx); HashSet<List<String>> set = new HashSet<>(ans); return new ArrayList<>(set); } public static void trace(List<List<String>> ans, ArrayList<String> an, int n, int cur, byte[][] mtx) { if (cur == 0) { ans.add((List<String>) an.clone()); return; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (check(mtx, i, j, n)) { mtx[i][j] = 1; StringBuilder sb = new StringBuilder(); for (int k = 0; k < n; k++) { if (k == j) { sb.append("Q"); } else { sb.append("."); } } an.set(i, sb.toString()); trace(ans, an, n, --cur, mtx); an.set(i, ""); mtx[i][j] = 0; cur++; } } } } public static boolean check(byte[][] mtx, int x, int y, int n) { boolean status = true; for (int i = 0; i < n && status; i++) { if (mtx[x][i] == 1) { status = false; break; } } for (int i = 0; i < n && status; i++) { if (mtx[i][y] == 1) { status = false; break; } } for (int i = x, j = y; i > 0 && j > 0 && status; i--, j--) { if (mtx[i - 1][j - 1] == 1) { status = false; break; } } for (int i = x, j = y; i < n - 1 && j < n - 1 && status; i++, j++) { if (mtx[i + 1][j + 1] == 1) { status = false; break; } } for (int i = x, j = y; i < n - 1 && j > 0 && status; i++, j--) { if (mtx[i + 1][j - 1] == 1) { status = false; break; } } for (int i = x, j = y; i > 0 && j < n - 1 && status; i--, j++) { if (mtx[i - 1][j + 1] == 1) { status = false; break; } } return status; } public static void main(String[] args) { byte[][] mtx = { {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, }; int n =7; long start = System.currentTimeMillis(); System.out.println(solveNQueens(n)); System.out.println(System.currentTimeMillis() - start); System.out.println(solveNQueens(n).size()); } }
简单优化版：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* 如何判断是否是对角线，对应坐标相减结果绝对值相等则对角线: Math.abs(x1 - x2) == Math.abs(y1 - y2);
*/
class Solution {
public static List<List<String>> solveNQueens(int n) {
byte[] x = new byte[n];
byte[] y = new byte[n];
List<List<String>> ans = new ArrayList<>();
byte[][] mtx = new byte[n][n];
ArrayList<String> an = new ArrayList<>();
for (int i = 0; i < n; i++) {
an.add("");
}
trace(ans, an, n, n, mtx, x, y);
HashSet<List<String>> set = new HashSet<>(ans);
return new ArrayList<>(set);
}
public static void trace(List<List<String>> ans, ArrayList<String> an, int n, int cur, byte[][] mtx, byte[] usedX, byte[] usedY) {
if (cur == 0) {
ans.add((List<String>) an.clone());
return;
}
for (int i = 0; i < n; i++) {
if (usedX[i] == 1) {
continue;
}
for (int j = 0; j < n; j++) {
if (usedY[j] != 1 && check(mtx, i, j, n)) {
mtx[i][j] = 1;
usedX[i] = 1;
usedY[j] = 1;
StringBuilder sb = new StringBuilder();
for (int k = 0; k < n; k++) {
if (k == j) {
sb.append("Q");
} else {
sb.append(".");
}
}
an.set(i, sb.toString());
trace(ans, an, n, --cur, mtx, usedX, usedY);
an.set(i, "");
mtx[i][j] = 0;
usedX[i] = 0;
usedY[j] = 0;
cur++;
}
}
}
}
public static boolean check(byte[][] mtx, int x, int y, int n) {
boolean status = true;
for (int i = 0; i < n && status; i++) {
if (mtx[x][i] == 1) {
status = false;
break;
}
}
for (int i = 0; i < n && status; i++) {
if (mtx[i][y] == 1) {
status = false;
break;
}
}
for (int i = x, j = y; i > 0 && j > 0 && status; i--, j--) {
if (mtx[i - 1][j - 1] == 1) {
status = false;
break;
}
}
for (int i = x, j = y; i < n - 1 && j < n - 1 && status; i++, j++) {
if (mtx[i + 1][j + 1] == 1) {
status = false;
break;
}
}
for (int i = x, j = y; i < n - 1 && j > 0 && status; i++, j--) {
if (mtx[i + 1][j - 1] == 1) {
status = false;
break;
}
}
for (int i = x, j = y; i > 0 && j < n - 1 && status; i--, j++) {
if (mtx[i - 1][j + 1] == 1) {
status = false;
break;
}
}
return status;
}
public static void main(String[] args) {
byte[][] mtx = {
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
};
System.out.println(solveNQueens(4).size());
int n = 7;
long start = System.currentTimeMillis();
System.out.println(solveNQueens(n));
System.out.println(System.currentTimeMillis() - start);
start = System.currentTimeMillis();
System.out.println(solveNQueens(8).size());
System.out.println(System.currentTimeMillis() - start);
}
}
优化第三版：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* 如何判断是否是对角线，对应坐标相减结果绝对值相等则对角线: Math.abs(x1 - x2) == Math.abs(y1 - y2);
*/
class Solution {
StringBuilder sb = null;
byte[] mx = null;
byte[] my = null;
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>(n);
byte[][] mtx = new byte[n][n];
ArrayList<String> an = new ArrayList<>(n);
sb=new StringBuilder(n);
for (int i = 0; i < n; i++) {
an.add("");
sb.append(".");
}
mx = new byte[n];
my = new byte[n];
trace(ans, an, n, n, mtx, 0);
return ans;
}
public void trace(List<List<String>> ans, ArrayList<String> an, int n, int cur, byte[][] mtx, int x) {
if (cur == 0) {
ans.add((List<String>) an.clone());
return;
}
for (int i = x; i < n; i++) {
if (mx[i] == 1) {
continue;
}
for (int j = 0; j < n; j++) {
if (my[j] != 1 && check(mtx, i, j, n)) {
mtx[i][j] = 1;
mx[i] = 1;
my[j] = 1;
StringBuilder builder = new StringBuilder(this.sb);
builder.setCharAt(j, 'Q');
an.set(i, builder.toString());
trace(ans, an, n, --cur, mtx, i+1);
an.set(i, "");
mtx[i][j] = 0;
mx[i] = 0;
my[j] = 0;
cur++;
}
}
}
}
public boolean check(byte[][] mtx, int x, int y, int n) {
for (int i = 0; i < n; i++) {
if (mtx[x][i] == 1) {
return false;
}
}
for (int i = 0; i < n; i++) {
if (mtx[i][y] == 1) {
return false;
}
}
for (int i = x, j = y; i > 0 && j > 0; i--, j--) {
if (mtx[i - 1][j - 1] == 1) {
return false;
}
}
for (int i = x, j = y; i < n - 1 && j < n - 1; i++, j++) {
if (mtx[i + 1][j + 1] == 1) {
return false;
}
}
for (int i = x, j = y; i < n - 1 && j > 0; i++, j--) {
if (mtx[i + 1][j - 1] == 1) {
return false;
}
}
for (int i = x, j = y; i > 0 && j < n - 1; i--, j++) {
if (mtx[i - 1][j + 1] == 1) {
return false;
}
}
return true;
}
public static void main(String[] args) {
byte[][] mtx = {
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
};
// System.out.println(check(mtx, 1, 3, 4));
//
// for (int i = 0; i < 4; i++) {
// for (int j = 0; j < 4; j++) {
// System.out.println("i = " + i + " j = " + j + " " + check(mtx, i, j, 4));
// }
// }
System.out.println(new Solution().solveNQueens(4));
}
}
不超时可以通过了。
优化第4版本，对于当前i,j判断当前行与列是否允许放皇后通过mx,my 单个坐标进行判断，而不是使用二维矩阵：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* 如何判断是否是对角线，对应坐标相减结果绝对值相等则对角线: Math.abs(x1 - x2) == Math.abs(y1 - y2);
*/
class Solution {
StringBuilder sb = null;
byte[] mx = null;
byte[] my = null;
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>(n);
byte[][] mtx = new byte[n][n];
ArrayList<String> an = new ArrayList<>(n);
sb=new StringBuilder(n);
for (int i = 0; i < n; i++) {
an.add("");
sb.append(".");
}
mx = new byte[n];
my = new byte[n];
trace(ans, an, n, n, mtx, 0);
return ans;
}
public void trace(List<List<String>> ans, ArrayList<String> an, int n, int cur, byte[][] mtx, int x) {
if (cur == 0) {
ans.add((List<String>) an.clone());
return;
}
for (int i = x; i < n; i++) {
if (mx[i] == 1) {
continue;
}
for (int j = 0; j < n; j++) {
if (my[j] != 1 && check(mtx, i, j, n)) {
mtx[i][j] = 1;
mx[i] = 1;
my[j] = 1;
StringBuilder builder = new StringBuilder(this.sb);
builder.setCharAt(j, 'Q');
an.set(i, builder.toString());
trace(ans, an, n, --cur, mtx, i+1);
an.set(i, "");
mtx[i][j] = 0;
mx[i] = 0;
my[j] = 0;
cur++;
}
}
}
}
public boolean check(byte[][] mtx, int x, int y, int n) {
/*
for (int i = 0; i < n; i++) {
if (mtx[x][i] == 1) {
return false;
}
}
for (int i = 0; i < n; i++) {
if (mtx[i][y] == 1) {
return false;
}
}
*/
for (int i = x, j = y; i > 0 && j > 0; i--, j--) {
if (mtx[i - 1][j - 1] == 1) {
return false;
}
}
for (int i = x, j = y; i < n - 1 && j < n - 1; i++, j++) {
if (mtx[i + 1][j + 1] == 1) {
return false;
}
}
for (int i = x, j = y; i < n - 1 && j > 0; i++, j--) {
if (mtx[i + 1][j - 1] == 1) {
return false;
}
}
for (int i = x, j = y; i > 0 && j < n - 1; i--, j++) {
if (mtx[i - 1][j + 1] == 1) {
return false;
}
}
return true;
}
public static void main(String[] args) {
byte[][] mtx = {
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
};
// System.out.println(check(mtx, 1, 3, 4));
//
// for (int i = 0; i < 4; i++) {
// for (int j = 0; j < 4; j++) {
// System.out.println("i = " + i + " j = " + j + " " + check(mtx, i, j, 4));
// }
// }
System.out.println(new Solution().solveNQueens(4));
}
}