用递归实现的8皇后问题解法

Question

我在编写8皇后问题的代码时遇到了困难。我编写了一个类来帮助我解决它，但由于某种原因，我做错了什么。我有点理解应该发生什么。

此外，我们必须使用递归来解决它，但我不知道如何使用我读过的回溯，所以我只在检查位置是否合法的方法中使用了它。

我的棋盘是String [] [] board = { { "O", "O"...等等，有8行8列。 如果我在概念上犯了任何错误或犯了严重的Java错误，请告诉我:D 谢谢！

public void solve () {
    int Queens = NUM_Queens - 1;
    while (Queens > 0) {
        for (int col = 0; col < 8; col++) {
            int row = -1;
            boolean c = false;
            while (c  = false && row < 8) {
                row ++;
                c = checkPos (row, col);
            }
            if (c == true) {
                board[row][col] = "Q";
                Queens--;
            }
            else 
                System.out.println("Error");
        }
    }
    printBoard ();
}

// printing the board
public void printBoard () {
    String ret = "";
    for (int i = 0; i < 8; i++) {
        for (int a = 0; a < 8; a++)
            ret += (board[i][a] + ", ");
        ret += ("\n");
    }
    System.out.print (ret);
}

// checking if a position is a legitimate location to put a Queen
public boolean checkPos (int y, int x) {
    boolean r = true, d = true, u = true, co = true;
    r = checkPosR (y, 0);
    co = checkPosC (0, x);
    int col = x;
    int row = y;
    while (row != 0 && col != 0 ) { //setting up to check diagonally downwards
        row--;
        col--;
    }
    d = checkPosDD (row, col);
    col = x;
    row = y;
    while (row != 7 && col != 0 ) { //setting up to check diagonally upwards
        row++;
        col--;
    }
    d = checkPosDU (row, col);
    if (r = true && d = true && u = true && co = true)
        return true;
    else
        return false;
}

// checking the row
public boolean checkPosR (int y, int x) {
    if (board[y][x].contentEquals("Q"))
            return false;
    else if (board[y][x].contentEquals("O") && x == 7)
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y, x+1);
}

// checking the column
public boolean checkPosC (int y, int x) {
    if (board[y][x].contentEquals("Q"))
            return false;
    else if (board[y][x].contentEquals("O") && y == 7)
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y+1, x);
}

// checking the diagonals from top left to bottom right
public boolean checkPosDD (int y, int x) {
    if (board[y][x].contentEquals("Q"))
        return false;
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 7))
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y+1, x+1);
}

 // checking the diagonals from bottom left to up right
public boolean checkPosDU (int y, int x) {
    if (board[y][x].contentEquals("Q"))
        return false;
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 0))
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y-1, x+1);
    }
}

- Tlazolteotl

---

因为每行只能有一个皇后，所以可以用int[8]来表示棋盘，其中每个元素代表该行皇后所在的列位置。这将大大简化问题。 - NPE

你得到了什么输出/错误？ - Aashray

你的代码遇到了什么问题？预期输出是什么，实际输出又是什么？ - Jayamohan

@Aashray 如果找不到皇后的位置，我会放置“错误”行，并且它会一直打印这个错误。因此，程序无法找到放置皇后的位置。@Jayamohan 问题在于我的程序找不到放置皇后的位置。 - Tlazolteotl

你的 while 循环将 c 赋值为 false，我想这不是你预期的行为。 - Quetzalcoatl

Answer 1

作为一份作业，这里提供的是解决方案，但不包含代码。

尝试编写一个仅处理单列所需操作的方法；这就是你应该使用递归的地方。通过检查是否存在解决方案来进行回溯，如果没有，则撤销上次更改（即更改皇后位置）并重试。如果只关注问题的一部分（一列），那么比同时考虑所有列要容易得多。

正如Quetzalcoatl所指出的那样，在第一个循环中将变量赋值为false。你可能不想这样做。你应该始终在编译器中启用所有警告（使用-Xlint运行javac）并修复它们。

- wds

Answer 2

你正在尝试某种暴力方法，但正如你已经提到的，你没有递归。

你的程序试图将皇后放在第一个可能的位置上。但最终没有找到解决方案。这意味着你的第一个假设（第一个皇后的位置）是无效的。你必须返回到这个状态。并且必须假设你的checkPos(x,y)为false而不是true。

现在给出一些提示：

1. 如NPE之前所述，int[N] queens是更合适的表示。
2. sum(queens)必须为0+1+2+3+4+5+6+7=28，因为位置必须是唯一的。
3. 你可以检查整个情况，而不仅仅是新皇后的位置。如果对于所有(i,j)∈N^2，其中queen(i)=j，则不存在(k,l)≠(i,j)，使得abs(k-i)==abs(l-j)，那么它就是有效的。

- gnod

---

我有点困惑你所说的检查整个情况是什么意思。你能否写一些代码让我了解一下？ - Tlazolteotl

抱歉，但从“没有解决方案”并不意味着第一个皇后的位置是错误的。 - Ingo

对的，如果要使其失效，您必须首先使最后一个假设无效。 - gnod