n-queens, 유효한 보드를 확인하십시오

Question

그래서 n-queens 문제를 해결하려고합니다. 내가 유효한 backtracking 구현을 가지고 있다고 생각하지만, 보드가 유효한지 검사하는 나의 방법은 (물론 비효율적 일뿐만 아니라) 꺼져 있다고 생각하지만, 나는 그 이유를 알 수 없다. 누구든지 왜 볼 수 있습니까/더 나은 방법을 제공합니까? 대신 매우 비효율적 각 광장 (2^(n*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

, 각 행에 대해 가장 퀸에 배치하려고 두 번째 solveQueens 기능을 수정할 수 있습니다. 즉, 더 길어진 solveQueens 함수는 행마다 가능한 모든 열을 시도하고 다음 행으로 이동합니다.

다른 점은 두 번째 solveQueens 함수에 대한 변수가 실제로 수정되었으므로 실제로 반환하지 않아야한다는 것입니다. 대신 솔루션이 있는지를 나타 내기 위해 true 또는 false 값을 반환 할 수 있습니다. 각 행에 대해 모든 가능한 열

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 기능 및 시도 :

그래서 제 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에서 (i - k) == (j - l) 대신 (abs(i - k) == abs(j - l))을 사용해야합니다. 원래 코드가 실패하는 예제는 i = 0, j = 3, k = 3, l = 0 (여왕은 행 0 열 3에 있고 두 번째 여왕은 행 3 열 0에 있음)이므로 (i - k) == 0 - 3 == -3 및 (j - l) == 3 - 0 == 3이며이 2 명의 여왕 서로 대각선이므로, 가장 안쪽 인 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 기능을 잘해야한다.

희망 하시겠습니까?