NQueensパズル、女王は置いていない？

Question

NQueens問題の再帰プログラムを、指定されたボードサイズで作成しています。私の問題は、女王はボードに置かれていないと私はなぜわからないです。私はプログラムをトレースしようとしましたが、私はまだ私の問題を見ていません。助言がありますか？

public class Main { 


public static boolean[][] board; 

public static void main(String[] args) throws FileNotFoundException { 

    Scanner scan = new Scanner(System.in); 
    System.out.println("Enter size of board"); 
    int n = scan.nextInt(); 
    board = new boolean[n][n]; 

    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board[0].length; j++) { 

      board[i][j] = false; 
     } 
    } 

    NQueens(0); 
    printBoard(); 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board.length; j++) { 

      if (board[i][j] == true) { 

       System.out.println((i + 1) + " " + (j + 1)); 

      } 
     } 
    } 
} 

static boolean NQueens(int col) { 
    if (col >= board.length) 
     return true; 

    for (int i = 0; i < board.length; i++) { 
     if (checkNotBlocked(col, i)) { 
      board[col][i] = true; 
      if (NQueens(col + 1)) 
       return true; 

      board[col][i] = false; 
     } 
    } 
    return false; 
} 

static boolean checkNotBlocked(int col, int row) { 

    for (int i = 0; i < col; i++) { 
     if (board[i][row] == true) 
      return false; 
    } 

    for (int i = col; i >= 0; i--) { 
     for (int j = row; j >= 0; j--) { 
      if (board[i][j] == true) 
       return false; 
     } 
    } 
    for (int i = col; i >= 0; i--) { 
     for (int j = row; j < board.length; j++) { 

      if (board[i][j] == true) 
       return false; 
     } 
    } 

    return true; 
} 


static void printBoard() { 
    int i; 
    for (i = 0; i < board.length; i++) { 
     for (int j = 0; j < board.length; j++) { 
      if (board[i][j] == true) { 
       System.out.print("Q\t"); 
      } else { 
       System.out.print("_\t"); 
      } 
     } 
      System.out.println("\n"); 
    } 
} 

Answer 1

対角線のチェックが正しくありません。ネストされたループを使用しました。つまり、四角形の対角線だけでなく、四角形全体をチェックしています。 に女王がいて、境界ボックス内の他の行がの場合、次の女王の配置を拒否します。これは最初のクイーンが置かれた後に起こるので、2度目のクイーンを決してボードに置くことはありません。

注意あなたが持っているものから、論理の違い：

for (int i = col; i >= 0; i--) { 
    for (int j = row; j >= 0; j--) { 
     if (board[i][j] == true) 
      return false; 
    } 
} 

...すべてをチェック対... [0] [0]までの[COL] [列]からペアを命じた反復します対角線のみ：

for (int i = col, j = row; // My apologies if this isn't legal Java; 
    i >= 0 & j >= 0;  // I'm out of practice. 
    i--, j--) {    // i and j must decrement *together*. 

    if (board[i][j]) 
      return false; 
    } 
} 

反対の対角線についても同様です。