八皇后算法

Question

我剛纔問了一個關於使用Java解決八皇后問題的問題。 我得到了一個回溯算法來解決這個問題。

我試圖使用這種算法，但我不知道我的代碼有什麼問題。它只能放置7個皇后。

這裏是女王級：

public class Queen { 
    //Number of rows or columns 
    public static final int BOARD_SIZE = 8; 

    boolean[][] board; 
    //Indicate an empty square 
    public static final boolean EMPTY = false; 
    //Indicate a square which containing a queen 
    public static final boolean QUEEN = true; 
    //Number of moves 
    public static final int MOVES = 4; 
    //Horizontal moves 
    int[] horizontal; 
    //Vertical moves 
    int[] vertical; 

    public int queens = 0; 

    public Queen() { 
     //Constructor creates an empty board 
     board = new boolean[BOARD_SIZE][BOARD_SIZE]; 
     for (int row = 0; row < board.length; row++) { 
      for (int col = 0; col < board[row].length; col++) { 
       board[row][col] = EMPTY; 
      } 
     } 

     horizontal = new int[MOVES]; 
     vertical = new int[MOVES]; 
     // up right 
     horizontal[0] = -1; 
     vertical[0] = 1; 
     // down left 
     horizontal[1] = 1; 
     vertical[1] = -1; 
     // up left 
     horizontal[2] = -1; 
     vertical[2] = -1; 
     // down right 
     horizontal[3] = 1; 
     vertical[3] = 1; 
    } 

    public boolean placeQueens (int column) { 
     if (column > BOARD_SIZE) { 
      return true; 
     } 
     else { 
      boolean queenPlaced = false; 
      int row = 1; 

      while (!queenPlaced && row < BOARD_SIZE) { 
       if (isUnderAttack(row, column)) { 
        ++row; 
       }// end if 
       else{ 
        setQueen(row, column); 
        queenPlaced = placeQueens(column + 1); 
        if (!queenPlaced) { 
         removeQueen(row,column); 
         ++row; 
        }// end if 
       }// end else 
      }// end while 
      return queenPlaced; 
     }// end else 
    } 

    private void removeQueen(int row, int column) { 
     board[row][column] = EMPTY; 
     System.out.printf("queen REMOVED from [%d][%d]\n", row, column); 
    --queens; 
    } 

    private void setQueen(int row, int column) { 
     board[row][column] = QUEEN; 
     System.out.printf("queen PLACED in [%d][%d]\n", row, column); 
     ++queens; 
    } 

    public boolean isUnderAttack(int row, int col) { 
     boolean condition = false; 
     // check row 
     for (int column = 0; column < BOARD_SIZE; column++) { 
      if ((board[row][column] == true)) { 
       condition = true; 
      } 
     } 

     // check column 
     for (int row_ = 0; row_ < board.length; row_++) { 
      if (board[row_][col] == true) { 
         condition = true; 
      } 
     } 

     // check diagonal 
     for (int row_ = row, col_ = col; row_ >= 0 && col_ < 8; row_ += horizontal[0], col_ += vertical[0]) { 
      if (board[row_][col_] == true) { 
       condition = true; 
      } 
     } 
     for (int row_ = row, col_ = col; row_ < 8 && col_ >= 0; row_ += horizontal[1], col_ += vertical[1]) { 
      if (board[row_][col_] == true) { 
       condition = true; 
      } 
     } 
     for (int row_ = row, col_ = col; row_ >= 0 && col_ >= 0; row_ += horizontal[2], col_ += vertical[2]) { 
      if (board[row_][col_] == true) { 
       condition = true; 
      } 
     } 
     for (int row_ = row, col_ = col; row_ < 8 && col_ < 8; row_ += horizontal[3], col_ += vertical[3]) { 
      if (board[row_][col_] == true) { 
       condition = true; 
      } 
     } 

     return condition; 
    } 

    public void displayBoard() { 
     int counter = 0; 
     for (int row = 0; row < board.length; row++) { 
      for (int col = 0; col < board[row].length; col++) { 
       if (board[row][col] == true) { 
        System.out.printf("|%s|", "x"); 
        counter++; 
       } 
       else {    
        System.out.printf("|%s|", "o"); 
       } 
      } 
      System.out.println(); 
     } 

     System.out.printf("%d queens has been placed\n", counter); 
    } 
} 

Answer 1

在Java數組0-indexed，這意味着第一項爲索引0。你似乎還沒有完全掌握了這一關鍵事實，這導致在你編寫代碼很多off-by-one errors。

的一個問題是在這裏：

int row = 1; 

它應該是：

int row = 0; 

---

的第二個問題是在這裏：

if (column > BOARD_SIZE) { 
    return true; 
} 

它應該是這樣的：

if (column >= BOARD_SIZE) { 
    return true; 
} 

---

您還沒有貼出你的代碼的其餘部分，但我敢打賭，有在代碼中的第三個錯誤，當你調用placeQueens方法。如果我知道你是什麼樣的人，那麼你很可能這樣做：

queen.placeQueens(1); 

但它應該是這樣的：

queen.placeQueens(0); 

---

伴隨着這些變化它按預期工作。最終的結果是：

 
|x||o||o||o||o||o||o||o| 
|o||o||o||o||o||o||x||o| 
|o||o||o||o||x||o||o||o| 
|o||o||o||o||o||o||o||x| 
|o||x||o||o||o||o||o||o| 
|o||o||o||x||o||o||o||o| 
|o||o||o||o||o||x||o||o| 
|o||o||x||o||o||o||o||o| 
8 queens has been placed 

看到它聯機工作：ideone