재귀 N-Queens : 누락 된 솔루션

Question

나는 C-c 체스 판과 함께 N-Queens 퍼즐의 자바 알고리즘을 작성했습니다. 내 재귀 적 방법의 코드는 다음과 같습니다.

모든 해결책을 찾지 못했습니다.

무엇을 내 기능

아이디어를 만들기 위해 주요 방법, 해결책까지 그것을 왕비의 최대 수를주는 내 함수에 대한 첫 번째 호출이 발견되고, 어떤 여왕 이러한 새없이 체스 판 -queen 좌표 : x = 0, y = 0.

이 기능은 체스 판을 통과합니다. 각 사각형에 대해 여왕 (0, 0)을 놓을 수 있는지 테스트합니다 (예 : 위협 없음). 여왕 (0; 0)은 놓을 수 있습니까? 자, 체스 판을 수정하고 함수 (재귀 호출)를 호출합니다. 이 재귀 호출은 "최대 퀸 - 1", 수정 된 체스 판 및 "new-queen 's y + 1"(조금 더 복잡함)으로 수행됩니다.

N 용액으로

실측치 = 4, C = 4 (존재 정상적으로 두 용액 ...!)

& & & Q

Q & & &

& & & Q

내 기능

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) { 
    if (nb_queens == 0) { // If there isn't any queen remaining, it means we found a solution 
     drawChessboard(chessboard); 
     solutions.add(chessboard); 
    } 

    for(int i = x; i < chessboard.size(); i++) { 
     for (int z = y; z < chessboard.get(i).size(); z++) { 
      if(!canBePlaced(i, z, chessboard)) { 
       chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait 
       setQueen(nb_queens-1, chessboard, i+1, 0, solutions); 
       chessboard.get(z).set(i, false); 
      } 
     } 
    } 

} 

이전 코드Q & &

최근 코드

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) { 
    if (nb_queens == 0) { 
     drawChessboard(chessboard); // Il n'y a plus de reine à placer => on dessine cette solution 
     solutions.add(chessboard); 
    } 

    for(int i = x; i < chessboard.size(); i++) { 
     for (int z = y; z < chessboard.get(i).size(); z++) { 
      if(!isAQueenAlreadyPresent(i, z, chessboard)) { 
       chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait 
       setQueen(nb_queens-1, chessboard, i, (z+1 >= WIDTH) ? 0 : z+1, solutions); 
       chessboard.get(z).set(i, false); 
      } 
     } 
    } 

} 

Answer 1

재귀 호출 방법, 당신의 setQueen(nb_queens-1, chessboard, i, z+1, solutions);을하고 있기 때문에 아 맞다, 그건. z+1 부분은 문제이며, 글로벌 보드에 배치 한 첫 번째 여왕 오른쪽의 해결책을 항상 발견 할 것입니다.

편집 : 예. 멋진 것을 발견했습니다.

따라서 문제는 for 루프가 에서 시작하므로 if(z>=y)으로 작동한다는 것입니다. i = x (첫 번째 줄을 읽었을 때)은 괜찮지만, i > x 일 때는 그렇지 않습니다. 그러므로 쉬운 수정은 for 루프 바로 뒤에 y = (i == x) ? y : 0을 넣는 것입니다.

전체 체스 판을 통과하기 위해 하나의 색인을 사용하는 것처럼 더 깨끗한 해결책이 있습니다.

매개 변수의 이름을 startX 및 startY로 변경하는 것이 좋습니다 (x 및 y 대신 x 및 y를 사용하여 더 명확하게 할 수 있음).

Edit2 : 게임의 규칙 때문에 같은 줄에 여왕이 없어 질 수 있으므로 setQueen(nb_queens-1, chessboard, i+1, 0, solutions); (다음 줄에서 직접 시작하기 때문에)과 같은 재귀 호출을 할 수 있습니다. 이 때문에 setQueen 메서드에서 int y 매개 변수를 제거하고 항상 z loop을 0에서 시작할 수도 있습니다.