8 재발로 인한 비 공격 퀸즈 알고리즘

Question

8 퀸즈 문제를 코딩하는 데 문제가 있습니다. 내가 그것을 해결하는 데 도움이되는 수업을 코딩했는데, 어떤 이유로, 나는 잘못된 것을하고있다. 나는 어떤 일이 일어나기로되어 있는지 이해합니다.

또한 재귀를 사용하여 해결해야하지만 읽은 백 트랙킹을 사용하는 방법에 대한 단서가 없으므로 위치가 합법적인지 여부를 확인하는 데 메소드에서 사용했습니다.

내 보드는 8 행 8 열 등 String [] [] board = { { "O", "O"... 등입니다. 개념적으로 잘못된 것이 있거나 심각한 자바 실수를하는 경우 다음과 같이 말하십시오. D 감사!

public void solve() { 
    int Queens = NUM_Queens - 1; 
    while (Queens > 0) { 
     for (int col = 0; col < 8; col++) { 
      int row = -1; 
      boolean c = false; 
      while (c = false && row < 8) { 
       row ++; 
       c = checkPos (row, col); 
      } 
      if (c == true) { 
       board[row][col] = "Q"; 
       Queens--; 
      } 
      else 
       System.out.println("Error"); 
     } 
    } 
    printBoard(); 
} 

// printing the board 
public void printBoard() { 
    String ret = ""; 
    for (int i = 0; i < 8; i++) { 
     for (int a = 0; a < 8; a++) 
      ret += (board[i][a] + ", "); 
     ret += ("\n"); 
    } 
    System.out.print (ret); 
} 

// checking if a position is a legitimate location to put a Queen 
public boolean checkPos (int y, int x) { 
    boolean r = true, d = true, u = true, co = true; 
    r = checkPosR (y, 0); 
    co = checkPosC (0, x); 
    int col = x; 
    int row = y; 
    while (row != 0 && col != 0) { //setting up to check diagonally downwards 
     row--; 
     col--; 
    } 
    d = checkPosDD (row, col); 
    col = x; 
    row = y; 
    while (row != 7 && col != 0) { //setting up to check diagonally upwards 
     row++; 
     col--; 
    } 
    d = checkPosDU (row, col); 
    if (r = true && d = true && u = true && co = true) 
     return true; 
    else 
     return false; 
} 

// checking the row 
public boolean checkPosR (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
      return false; 
    else if (board[y][x].contentEquals("O") && x == 7) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y, x+1); 
} 

// checking the column 
public boolean checkPosC (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
      return false; 
    else if (board[y][x].contentEquals("O") && y == 7) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y+1, x); 
} 

// checking the diagonals from top left to bottom right 
public boolean checkPosDD (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
     return false; 
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 7)) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y+1, x+1); 
} 

// checking the diagonals from bottom left to up right 
public boolean checkPosDU (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
     return false; 
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 0)) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y-1, x+1); 
    } 
} 

Answer 1

당신은 어떤 종류의 무차별 공격을 시도하고 있습니다 만, 이미 언급했듯이 재귀가 없습니다. 프로그램은 여왕을 첫 번째 가능한 위치에 놓으려고합니다. 그러나 결국에는 해결책이 없습니다. 귀하의 첫 번째 가정 (귀하의 첫 번째 여왕의 위치)이 유효하지 않습니다. 로 가면로이 상태가됩니다. checkPos (x, y)가 참이 아니라 거짓이라고 가정해야합니다.

이제

몇 가지 힌트 :

1. NPE int[N] queens으로 앞서 언급 한 바와 같이보다 적절한 표현입니다.
2. 위치는 고유해야하므로 sum (queens)은 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이어야합니다.
3. 새 여왕의 위치 만 확인하는 대신 전체 상황을 점검 할 수 있습니다. queen (i) = j 인 N^2에있는 모든 (i, j) \에 대해 abs (ki) == abs (lj) 인 no (k, l)! =

Answer 2

이것은 숙제이므로 해결책은 있지만 코드에는 없습니다.

단일 열에서 발생해야하는 작업 만 처리하는 방법을 작성하십시오. 여기서 재귀를 사용해야합니다. 솔루션이 존재하는지 확인하고 그렇지 않은 경우 마지막 변경 사항을 취소 (즉, 여왕의 위치 변경)하고 다시 시도하여 역 추적하십시오. 문제의 한 부분 (한 열)에만 집중한다면, 동시에 모든 열을 생각하는 것보다 훨씬 쉽습니다.

Quetzalcoatl이 지적한대로 false을 첫 번째 루프의 변수에 할당합니다. 당신은 아마 그것을하고 싶지 않을 것입니다. 컴파일러 (-Xlint를 사용하여 javac를 실행)에서 항상 모든 경고를 활성화하고 수정해야합니다.