n皇后，檢查有效的董事會

Question

所以我試圖解決n皇后問題。我認爲我有一個有效的回溯實現，但我認爲我的方法來檢查一個板是否有效是關閉的（以及非常低效），但我不明白爲什麼。任何人都可以看到爲什麼/提供更好的方法？

/** Given an N x N chess board, find placements for N queens on the board such that 
* none of them are attacking another queen (two queens are attacking each other if 
* they occupy the same row, column, or diagonal). 
* Print out the row, col coordinates for each queen on a separate line, where the 
* row and column numbers are separated by a single space. */ 
static void solveQueens(int n) { 
    boolean[][] board = new boolean[n][n]; 
    board = solveQueens(board, n); 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board.length; j++) { 
      if (board[i][j]) { 
       System.out.printf("%s %s\n", i, j); 
      } 
     } 
    } 
} 
/** Returns a solved board for the n-queens problem, given an empty board. */ 
static boolean[][] solveQueens(boolean[][] board, int queensLeft) { 
    if (queensLeft == 0) { 
     return board; 
    } 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board.length; j++) { 
      if (board[i][j]) { continue; } 
      board[i][j] = true; 
      if (isValid(board)) { 
       return solveQueens(board, queensLeft - 1); 
      } else { 
       board[i][j] = false; 
      } 
     } 
    } 
    return null; 
} 
/** True iff BOARD is a valid solution, with no queens attacking each other. */ 
static boolean isValid(boolean[][] board) { 
    boolean occupied = false; 
    //Horizontal 
    for (int i = 0; i < board.length; i++) { 
     for (boolean queen : board[i]) { 
      if (queen && occupied) { 
       return false; 
      } 
      if (queen) { 
       occupied = true; 
      } 
     } 
     occupied = false; 
    } 
    //Vertical 
    for (int i = 0; i < board.length; i++) { 
     for (int j = board.length - 1; j >= 0; j--) { 
      boolean queen = board[j][i]; 
      if (queen && occupied) { 
       return false; 
      } 
      if (queen) { 
       occupied = true; 
      } 
     } 
     occupied = false; 
    } 
    //Diagonals 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board.length; j++) { 
      if (board[i][j]) { 
       for (int k = 0; k < board.length; k++) { 
        for (int l = 0; l < board.length; l++) { 
         if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) { 
          return false; 
         } 
        } 
       } 
      } 
     } 
    } 
    return true; 
} 

Answer 1

，而不是試圖把每一個正方形，這是非常低效（2^(n*n)）女王，你可能要修改第二solveQueens功能嘗試最多一個女王將每一行。換句話說，較長的solveQueens函數將嘗試每行可能的每列，然後轉到下一行。

另一點是，board變量到第二個solveQueens函數被修改到位，所以我們實際上不必返回它。相反，我們可以簡單地返回true或false值來指示是否有解決方案。

所以第一solveQueens功能可以改爲：

static void solveQueens(int n) { 
    boolean[][] board = new boolean[n][n]; 
    // boolean return value from second solveQueens function 
    boolean solved = solveQueens(board, n); 
    if (solved) { 
     for (int i = 0; i < board.length; i++) { 
      for (int j = 0; j < board.length; j++) { 
       if (board[i][j]) { 
       System.out.printf("%s %s\n", i, j); 
      } 
     } 
    } else { 
     System.out.printf("No solution for board of size %d\n", n); 
    } 
} 

而第二個修改solveQueens功能，遞歸下降的每一行，並嘗試所有可能的列的每一行：

static boolean solveQueens(boolean[][] board, int row, int n) { 
    // we have a queen for each row, done 
    if (row >= n) { 
     return board; 
    } 
    // for the current row, try placing a queen at column 0 
    // if that fails, try placing a queen at column 1 
    // if that fails, try placing a queen at column 2, and so on 
    for (int j = 0; j < board.length; j++) { 
     board[row][j] = true; 
     if (isValid(board)) { 
      // placing at (row, j) is valid, try next row 
      boolean boardSolved = solveQueens(board, row + 1, n); 
      if (boardSolved) { 
       // board is solved, yay 
       return boardSolved; 
      } 
     } 
     // cannot place queen at (row, j) with current board configuration. 
     // set board[row][j] back to false 
     board[i][j] = false; 
    } 
    // tried every column in current row and still cant solve, return false 
    return false; 
} 

對於isValid功能的這部分：

//Diagonals 
for (int i = 0; i < board.length; i++) { 
    for (int j = 0; j < board.length; j++) { 
     if (board[i][j]) { 
      for (int k = 0; k < board.length; k++) { 
       for (int l = 0; l < board.length; l++) { 
        if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) { 
         return false; 
        } 
       } 
      } 
     } 
    } 
} 
return true; 

在最裏面的if，您將不得不使用(abs(i - k) == abs(j - l))而不是(i - k) == (j - l)。原始代碼將失敗的一個示例是當i = 0,j = 3,k = 3,l = 0（皇后位於第0行第3列，第二皇后位於第3行第0列），所以(i - k) == 0 - 3 == -3和(j - l) == 3 - 0 == 3，即使這兩個皇后是彼此對角的，最內層的if將無法​​檢測到它。使用abs(i - k) == abs(j - l)會將行距（i - k）和列距（j - l）變成絕對值，因此將起作用。

所以才改變這一行：

if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) { 

到：

if ((abs(i - k) == abs(j - l)) && board[k][l] && !(k == i && l == j)) { 

和isValid功能應該罰款。

希望有幫助！