遞歸N皇后：缺少解決方案

Question

我寫了一個N皇后拼圖的Java小算法（用c * c棋盤）。你會發現我的遞歸方法的代碼。

它沒有找到所有的解決方案。

什麼我的功能

的想法是讓中的主要方法，我的功能的第一個電話給它王后的最大數量，直到找到解決方法，沒有任何女王和這些新的棋盤-queen的座標：x = 0，y = 0。

該功能將通過棋盤。對於每個方塊，它測試是否可以放置皇后（0; 0）（即：無威脅）。女王（0; 0）可以放置？那麼，我們這樣做（修改棋盤），我們稱之爲函數（遞歸調用）。這個遞歸調用是通過「最大數量的皇后-1」，修改後的棋盤和「新皇后的y + 1」（稍微複雜一些）完成的。

與N實測值溶液= 4和C = 4（通常有兩種解決方案...！）

& & Q &

Q & & &

& & & Q

& Q & &

我的功能

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) { 
    if (nb_queens == 0) { // If there isn't any queen remaining, it means we found a solution 
     drawChessboard(chessboard); 
     solutions.add(chessboard); 
    } 

    for(int i = x; i < chessboard.size(); i++) { 
     for (int z = y; z < chessboard.get(i).size(); z++) { 
      if(!canBePlaced(i, z, chessboard)) { 
       chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait 
       setQueen(nb_queens-1, chessboard, i+1, 0, solutions); 
       chessboard.get(z).set(i, false); 
      } 
     } 
    } 

} 

舊代碼的近期代碼

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) { 
    if (nb_queens == 0) { 
     drawChessboard(chessboard); // Il n'y a plus de reine à placer => on dessine cette solution 
     solutions.add(chessboard); 
    } 

    for(int i = x; i < chessboard.size(); i++) { 
     for (int z = y; z < chessboard.get(i).size(); z++) { 
      if(!isAQueenAlreadyPresent(i, z, chessboard)) { 
       chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait 
       setQueen(nb_queens-1, chessboard, i, (z+1 >= WIDTH) ? 0 : z+1, solutions); 
       chessboard.get(z).set(i, false); 
      } 
     } 
    } 

} 

Answer 1

哦，對了，那是因爲你怎麼稱呼遞歸，你做setQueen(nb_queens-1, chessboard, i, z+1, solutions);。 z+1部分是問題所在，它總是會在您放置在全局板上的第一個皇后右側找到解決方案。

編輯：啊你之前找到它了，很好。

因此，問題在於for循環充當if(z>=y)，因爲它起始於y。當i = x（閱讀第一行）時沒關係，但當i > x時沒有。所以一個簡單的解決方法是在第一個for循環之後放y = (i == x) ? y : 0。

甚至有更清潔的解決方案，就像使用單個索引遍歷整個棋盤一樣。

我還建議你重命名你的參數爲startX和startY（而不是x和y，你可以在循環中使用x和y來更清晰）。編輯2：由於遊戲規則，在同一行上永遠不會有女王，所以你可以進行遞歸調用，如setQueen(nb_queens-1, chessboard, i+1, 0, solutions);（i+1，因爲你直接從下一行開始）。因此，您甚至可以從setQueen方法中刪除int y參數，並始終以0開始z loop。