我是递归和回溯的新手。我正在尝试完成 N-Queen 问题以打印所有解决方案而不仅仅是 1 并理解这些概念。我认为我已经部分正确地实现了算法，因为我得到了一些解决方案，但没有全部打印出来。我的代码是用 Java 编写的。对于 N = 4 的值，我得到 2 个解决方案 - 这是正确的对于 N = 5 的值，我得到 5 个解决方案 - 实际上有 10 个对于 N= 8 的值，我没有打印出来我无法弄清楚我犯了什么错误。我的想法是意识到第一个皇后必须在第一行，第二个在第二行等等。我必须弄清楚哪一列是合适的，显然要注意对角线来放置一个皇后。感谢您为我指明正确方向的任何帮助。我的代码在下面，我尝试添加注释以帮助理解。public class nQueens { static class Queen { public Queen( int row, int column) { this.row = row; this.column = column; } int row = -1; int column = -1; } static ArrayList<Queen> queens = new ArrayList<Queen>(); public static void main(String argv[]) { int n = 5; int[][] chessBoard = new int[n][n]; int placed = 0; solve(n, chessBoard, placed); } public static void solve(int n, int[][] chessBoard, int placed) { // this means that all the queens have been placed if (placed == n) { System.out.println("**** Solution *****"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(chessBoard[i][j] + " "); } System.out.println(); } } else { // we know that each queen can be placed on each row int i = placed; // iterate through the columns for (int j = 0; j < n; j++) { if (chessBoard[i][j] != 1) { if (isSafe(i, j)) { chessBoard[i][j] = 1;
2 回答
慕娘9325324
TA贡献1783条经验 获得超4个赞
问题是：
int slope = Math.abs((queens.get(i).row - row) / (queens.get(i).column - column));
if (slope == 1) {
return false;
}
您正在转换slope为整数。这意味着即使皇后实际上不在该对角线上，斜率1.5或1.3变为1并导致您返回。false
而是在除法之前转换为浮点数（请注意，java的除法是整数除法，因此您需要先将除数或被除数转换为浮点数以获得浮点输出）以允许浮点斜率：
float tmp = (queens.get(i).row - row);
float slope = Math.abs(tmp/ (queens.get(i).column - column));
if (slope == 1) {
return false;
}
慕勒3428872
TA贡献1848条经验 获得超6个赞
的替代解决方案isSafe()和class Queen
让棋盘成为一个跟踪状态的类
采取
克隆当前板子状态
设置女王并阻止她可以到达的所有领域
将克隆向下传递到下一行
记住每个皇后的每行列位置
placer以下是在闭包中传递的通用求解器。placeRook()通过使用该方法，可以很容易地对车 ( )、骑士 ( placeKnight()) 或主教 ( )使用相同的求解器placeBishop()。
请注意，我的解决方案是用 Groovy 编写的，它也在 JVM 上运行，并且非常接近 Java。所以将算法的多汁位翻译成Java应该没有问题。
class ChessBoard {
int N
int lastIndex
private boolean[][] board
int solutions
ChessBoard(int n) {
board = new boolean[n][n]
N = n
lastIndex = n - 1
solutions = 0
this.each { int row, int column -> board[row][column] = true }
}
ChessBoard(ChessBoard orig) {
N = orig.getN()
board = new boolean[N][N]
lastIndex = N - 1
solutions = 0
this.each { int row, int column -> board[row][column] = orig.getField(row, column) }
}
void each(Closure c) {
(0..lastIndex).each { row ->
(0..lastIndex).each { column -> c(row, column) }
}
}
void print() {
println " ${'-' * N}"
(0..lastIndex).each { row ->
print "|"
(0..lastIndex).each { column -> print "${board[row][column] ? ' ' : 'X'}" }
println "|"
}
println " ${'-' * N}"
}
int getN() { return N }
int getSolutions() { return solutions }
boolean getField(int row, int column) { return board[row][column] }
void blockField(int row, int column) {
if ((row < 0) || (row > lastIndex))
return
if ((column < 0) || (column > lastIndex))
return
board[row][column] = false
}
List<Integer> getFree(int row) {
(0..lastIndex).findResults { int column -> board[row][column] ? column : null }
}
void placeQueen(int row, int column, boolean all = true) {
if (all) {
(0..lastIndex).each { offset ->
blockField(row, offset) // row
blockField(offset, column) // column
blockField(row + offset, column + offset) // diagonals
blockField(row + offset, column - offset)
blockField(row - offset, column + offset)
blockField(row - offset, column - offset)
}
} else {
blockField(row, column)
}
}
// recursive solver
void solve(ChessBoard previous, List<Integer> columns, int row, Closure placer) {
List<Integer> free = previous.getFree(row)
if (row < lastIndex) {
// recurse
free.each { column ->
ChessBoard work = new ChessBoard(previous)
columns[row] = column
placer(work, row, column, true)
solve(work, columns, row + 1, placer)
}
} else {
// solutions
free.each { column ->
ChessBoard solution = new ChessBoard(N)
columns[row] = column
(0..lastIndex).each { placer(solution, it, columns[it], false) }
println "Solution #${++solutions}:"
solution.print()
}
}
}
// start recursion
void solve(Closure placer) {
List<Integer> columns = []
solve(this, columns, 0, placer)
}
}
board = new ChessBoard(8)
board.solve { ChessBoard work, int row, int column, boolean all -> work.placeQueen(row, column, all) }
println "Solutions: ${board.getSolutions()}"
测试运行：
Solution #1:
--------
|X |
| X |
| X|
| X |
| X |
| X |
| X |
| X |
--------
...
Solution #92:
--------
| X|
| X |
|X |
| X |
| X |
| X |
| X |
| X |
--------
Solutions: 92
如果我没记错的话，对于 8-Queen 问题来说，92 听起来确实是正确的。但是自从我在学校使用 Pascal 中的迭代方法解决这个问题以来已经超过 35 年了 :-)
更新改进的解决方案
将原始类拆分ChessBoard为跟踪状态和Solver算法
皇后、白嘴鸦、主教和骑士的砂矿
计算尺寸 1 到 8 的解决方案
为结果生成降价表
class ChessBoard {
private int N
private int lastIndex
private boolean[][] state
ChessBoard(int n) {
N = n
lastIndex = N - 1
state = new boolean[N][N]
(0..lastIndex).each { row ->
(0..lastIndex).each { column ->
setField(row, column, true)
}
}
}
ChessBoard(ChessBoard orig) {
N = orig.getN()
lastIndex = N - 1
state = new boolean[N][N]
(0..lastIndex).each { row ->
(0..lastIndex).each { column ->
setField(row, column, orig.getField(row, column))
}
}
}
int getN() {
return N
}
boolean getField(int row, int column) {
return state[row][column]
}
void setField(int row, int column, boolean free = false) {
if ((row < 0) || (row > lastIndex))
return
if ((column < 0) || (column > lastIndex))
return
state[row][column] = free
}
List<Integer> getFree(int row) {
(0..lastIndex)
.findResults { int column ->
getField(row, column) ? column : null
}
}
// for debugging only
void print() {
println " ${'-' * N}"
(0..lastIndex).each { row ->
print "|"
(0..lastIndex).each { column -> print "${getField(row, column) ? ' ' : 'X'}" }
println "|"
}
println " ${'-' * N}"
}
}
class Solver {
private int N
private int lastIndex
private int solutions
private int[] columns
Solver(int n) {
N = n
lastIndex = N - 1
solutions = 0
columns = new int[N]
}
void printSolution(String label) {
solutions++
if (!label)
return
println "${N}-${label} solution #${solutions}"
println " ${'-' * N}"
(0..lastIndex).each { row ->
int column = columns[row]
println "|${' ' * column}X${' ' * (lastIndex - column)}|"
}
println " ${'-' * N}"
}
int getSolutions() {
return solutions
}
void placeQueen(ChessBoard board, int row, int column) {
// only modify fields from (row+1) downwards
(1..(lastIndex - row)).each { offset ->
board.setField(row + offset, column) // column
board.setField(row + offset, column + offset) // diagonals
board.setField(row + offset, column - offset)
}
}
void placeRook(ChessBoard board, int row, int column) {
// only modify fields from (row+1) downwards
(1..(lastIndex - row)).each { offset ->
board.setField(row + offset, column) // column
}
}
void placeBishop(ChessBoard board, int row, int column) {
// only modify fields from (row+1) downwards
(1..(lastIndex - row)).each { offset ->
board.setField(row + offset, column + offset) // diagonals
board.setField(row + offset, column - offset)
}
}
static void placeKnight(ChessBoard board, int row, int column) {
// only modify fields from (row+1) downwards
board.setField(row + 1, column - 2)
board.setField(row + 1, column + 2)
board.setField(row + 2, column - 1)
board.setField(row + 2, column + 1)
}
// recursive solver
void solve(ChessBoard previous, int row, Closure placer, String label) {
List<Integer> free = previous.getFree(row)
if (row < lastIndex) {
// recurse
free.each { column ->
ChessBoard work = new ChessBoard(previous)
columns[row] = column
placer(this, work, row, column)
solve(work, row + 1, placer, label)
}
} else {
// solutions
free.each { column ->
columns[row] = column
printSolution(label)
}
}
}
// start recursion
int solve(Closure placer, String label = null) {
solve(new ChessBoard(N), 0, placer, label)
return solutions
}
}
Map<String, Closure> placers = [
'Queens': { Solver solver, ChessBoard board, int row, int column -> solver.placeQueen(board, row, column) },
'Rooks': { Solver solver, ChessBoard board, int row, int column -> solver.placeRook(board, row, column) },
'Bishops': { Solver solver, ChessBoard board, int row, int column -> solver.placeBishop(board, row, column) },
'Knights': { Solver solver, ChessBoard board, int row, int column -> solver.placeKnight(board, row, column) },
]
Map<String, List<Integer>> solutions = [:]
// generate solutions up to maxN
int maxN = 8
boolean print = false
placers
.keySet()
.each { String key ->
Closure placer = placers[key]
List<Integer> results = []
(1..maxN).each { N ->
results.push(new Solver(N).solve(placer, print ? key : null))
}
solutions[key] = results
}
// generate markdown table from solutions
List lines = []
(0..maxN).each { lines[it] = [it ?: 'Size'] }
[
'Queens',
'Rooks',
'Bishops',
'Knights',
].each { key ->
List<Integer> results = solutions[key]
lines[0].push(key)
(1..maxN).each { lines[it].push(results[it - 1]) }
}
lines.each { line -> println line.join('|') }
return
结果表：
| Size | Queens | Rooks | Bishops | Knights |
|------|--------|-------|---------|---------|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 2 | 2 | 4 |
| 3 | 0 | 6 | 5 | 9 |
| 4 | 2 | 24 | 24 | 52 |
| 5 | 10 | 120 | 125 | 451 |
| 6 | 4 | 720 | 796 | 4898 |
| 7 | 40 | 5040 | 5635 | 67381 |
| 8 | 92 | 40320 | 48042 | 1131382 |
|------|--------|-------|---------|---------|
添加回答
举报
0/150
提交
取消