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); 
    } 
} 

Answer 1

你正在嘗試某種蠻力，但正如你已經提到的，你沒有遞歸。 您的程序會嘗試將女王放在第一個可能的位置。但最終沒有找到解決辦法。因此，你的第一個假設（你的第一個女王的位置）是無效的。你必須回到這個狀態。並且必須假設你的checkPos（x，y）是false而不是true。

現在一些提示：

1. 如NPE int[N] queens前面提到的是更合適的表示。
2. 總和（皇后）必須是0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28，因爲一個位置必須是唯一的。
3. 不是隻檢查新皇后的位置，你可以檢查整個情況。如果在女王（i）= j的N^2中對於所有（i，j）\，在abs（ki）= abs（lj）時不存在（k，l）！=

Answer 2

由於這是作業，解決方案，而不是代碼。

嘗試編寫一種方法，該方法只處理需要在單個列上發生的事情;這是你應該使用遞歸的地方。通過檢查是否存在解決方案來進行回溯，如果不存在，則撤消最後的更改（即更改女王位置）並重試。如果您只關注問題的一部分（一列），這比同時考慮所有列更容易。並且正如Quetzalcoatl指出的那樣，您在第一個循環中將變量false分配給您的變量。你可能不想這樣做。您應該始終在編譯器中啓用所有警告（使用-Xlint運行javac）並修復它們。