为什么我的代码无休止地测试（n 皇后区问题 / java / 蓝色）

Question

所以我目前正在研究 n 皇后问题的算法，我想我已经完成了，但是当我运行一个 junit class 来测试代码时，它只是无休止地工作。

蓝色条从左到右不停地移动等等(https://prnt.sc/ruqjef)

我不太清楚为什么会这样。 junit class 正在测试 n=8 的代码。当我用 n=1 尝试它时它工作，当我用 n>=2 尝试它时它只是 loading/working.

我不知道为什么，所以我非常感谢您的帮助 c:

我的代码：

public class Damenproblem {

    /**
     * Datenstruktur für das Speichern der Damenpositionen
     * als Array-Attribut der Klasse
     */
    private boolean[][] damenFeld;

    /**
     * Gibt ein zweidimensionales boolean-Array zurueck. 
     * n ist die Schachbrettbreite. Auf den jeweiligen
     * Positionen des Arrays sind die Positionen der Damen (true = Dame, false =
     * keine Dame). Wenn sich das Problem nicht loesen laesst, wird eine
     * NoSolutionException geworfen.
     */
    public boolean[][] damen(int n) throws NoSolutionException{
        this.damenFeld = new boolean[n][n];
        if (setze(0)){
            return damenFeld;
        }
        else {
            throw new NoSolutionException();
        }
    }

    /**
     * Backtracking-Algorithmus
     * Parameter dameNr gibt die laufende Nummer der zu setzenden Dame an.
     */
    private boolean setze(int dameNr) {
        int zeile = 0;
        if(dameNr == damenFeld.length) {
            return true;
        } else {
        for(dameNr = 0; dameNr <= damenFeld.length; dameNr++) {

            if(erlaubt(dameNr, zeile)) {
                damenFeld[dameNr][zeile] = true;
                if(setze(dameNr+1)) {
                    return true;
                } else {
                    damenFeld[dameNr][zeile] = false;
                    zeile += 1;
                }
            }
        }
        return false;
    }
    }
    // DameNr ist die Spalte
    public boolean erlaubt(int spalte, int zeile) {
        // check horizontal and vertical
        int tempSpalte = spalte;
        int tempZeile = zeile;
        for(int i = 0; i < damenFeld.length; i++) {
            if(damenFeld[i][zeile] || damenFeld[spalte][i]) {
                return false;
            }
        }
        // check diagonal
        // to upper right
        while(spalte >= 0 && spalte <= damenFeld.length && zeile >= 0 && zeile <= damenFeld.length){
            spalte = tempSpalte;
            zeile = tempZeile;
            if(damenFeld[spalte][zeile]) {
                return false;
            }
            spalte += 1;
            zeile -= 1;
        }
        // check diagonal
        // to lower right
        while(spalte >= 0 && spalte <= damenFeld.length && zeile >= 0 && zeile <= damenFeld.length){
            spalte = tempSpalte;
            zeile = tempZeile;
            if(damenFeld[spalte][zeile]) {
                return false;
            }
            spalte += 1;
            zeile += 1;
        }
        // check diagonal
        // to lower left
        while(spalte >= 0 && spalte <= damenFeld.length && zeile >= 0 && zeile <= damenFeld.length){
            spalte = tempSpalte;
            zeile = tempZeile;
            if(damenFeld[spalte][zeile]) {
                return false;
            }
            spalte -= 1;
            zeile += 1;
        }
        // check diagonal
        // to upper left
        while(spalte >= 0 && spalte <= damenFeld.length && zeile >= 0 && zeile <= damenFeld.length){
            spalte = tempSpalte;
            zeile = tempZeile;
            if(damenFeld[spalte][zeile]) {
                return false;
            }
            spalte -= 1;
            zeile -= 1;
        }
        return true;
    }
}

Answer 1

为了不覆盖您的 dameNr 参数，您方法 setze() 中的 for 循环应该如下所示：

for(zeile = 0; zeile < damenFeld.length; zeile++)

你的 erlaubt() 检查是主要问题。我建议使用 for 而不是 while 循环，每个循环都定义新的临时参数。否则你会一遍又一遍地使用你传递的参数。

为什么我的代码无休止地测试（n 皇后区问题 / java / 蓝色）

why is my code endlessly testing (n queens problem / java / blue)

java

recursion

backtracking

bluej