八皇后算法

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