나이트 투어 재귀가 해결책을 찾지 못했습니다

Question

나이트 투어가 이전에 요청되었지만 여전히 문제가 있습니다. 체스 판의 모든 셀을 방문하는 재귀를 시도하고 있지만 52 회 이상 방문을 할 수는 없습니다. 그 후에 그것은 역 추적하고 방문한 세포의 수는 아래로 센다.

public class Ch7E22_3 { 
    public static int[][] chess; 
    public static int[][] adjacent; 

    public static void main(String[] args) { 
     chess = new int[8][8]; 
     adjacent = new int[][] { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 }, 
       { -1, -2 } }; 
     initializeChess(); 
     move(1, 0, 0); 
    } 

    private static void move(int cnt, int row, int col) { 
     chess[row][col] = cnt; 
     if (cnt == (8 * 8)) { 
      System.out.println("You moved around all cells: " + cnt); 
     } else { 
      for (int i = 0; i < 8; i++) { 
       if (((row + adjacent[i][0] >= 0) && (row + adjacent[i][0]) < 8) 
         && ((col + adjacent[i][1] >= 0) && (col + adjacent[i][1] < 8))) { 
        if (chess[row + adjacent[i][0]][col + adjacent[i][1]] == 0) { 
         row = row + adjacent[i][0]; 
         col = col + adjacent[i][1]; 
         cnt++; 
         System.out.println(row + " " + col + " cnt = " + cnt); 
         move(cnt, row, col); 
        } 
       } 
      } 
     } 
     chess[row][col] = 0; 
    } 

    private static void initializeChess() { 
     for (int i = 0; i < 8; i++) { 
      for (int j = 0; j < 8; j++) { 
       chess[i][j] = 0; 
      } 
     } 
    } 
} 

Answer 1

첫 번째 문제는 여기에 있습니다 : :

for (int i = 0; i < 8; i++) { 

그래서, 당신은 for 루프를 가지고 여기 내 코드입니다. 먼저 당신이 당신의 재귀 호출을하고, 아마 안타 경우 바로 먼저 각 시간 : 당신이 51

에서 탄소 나노 튜브와 함께 입력 가정하자 이제

if (... some overly complicated condition ...) { 
    ... cnt++ 
    move(cnt, 

는 무엇 이제 어떻게해야합니다. 따라서 cnt를 늘리고 다시 호출하십시오. 그러므로 인쇄물은 cnt가 계속 증가하는 방법을 보여줍니다.

그러나 어떤 시점에서 재귀 은으로 끝납니다. if 조건이 더 이상 유효하지 않습니다. 따라서 재귀 적으로 호출 된 메소드 ...가 종료됩니다. 그러나 염두에 두십시오 : 당신은 그 방법을 ... 으로의 다른 호출에서 호출했습니다. 그리고 그 사람은 여전히 ​​반복 할 수 있습니다. 그리고 더 중요한 것은 그 move()는 자신의 cnt 버전입니다.

내가 무슨 뜻인지 알기 위해서 : 로컬 변수가 귀하의 보드와 비슷한 필드가되도록 변수 cnt를 변경하십시오! 당신이 그렇게 할 때, 당신은 당신의 코드가 실제로 인쇄 것을 발견 할 것이다 :

... 
3 7 cnt = 52 
2 4 cnt = 53 
... 
2 3 cnt = 64 
You moved around all cells: 64 
0 4 cnt = 65 
... 

실제로

4 0 cnt = 126 

의미로 나중에 중지 : CNT의 인쇄가 정말 작동하지 알고리즘의 단지 부작용 바르게!

마지막 : 나는 헤어 추천 할 것입니다 귀하의

private static isXyz(...) 

과 같은 작은 도우미 메서드의 집합에 조건이 그 내에서 이러한 메서드를 호출하는 경우 if 문 - 가독성에 크게 도움이 될 것이다!

Answer 2

역 추적이 올바르지 않습니다. 마지막 줄이 실행될 때까지 을 다시 0으로 설정하면 row과 col이 거의 확실하게 변경되었습니다.

row, col 및 cnt을 변경하지 말고 재귀 호출에만 새 값을 전달하는 것이 좋습니다.나는 당신의 논리의 나머지 부분을 확인하지 않은 있지만, 이런 식으로 뭔가가 :

for (int i = 0; i < 8; i++) { 
     int nextrow = row + adjacent[i][0]; 
     int nextcol = col + adjacent[i][1]; 
     if (nextrow >= 0 && nextrow < 8 && 
       nextcol >= 0 && nextcol < 8) { 
      if (chess[nextrow][nextcol] == 0) { 
       System.out.println(nextrow + " " + nextcol + " cnt = " + (cnt+1)); 
       move(cnt+1, nextrow, nextcol); 
      } 
     } 
    } 

당신은 단지 내에서 수정 결코 후속 재귀 호출로 아래로 전달되는 값을 수정하지 않으며,에 일관성을 보장하기 위해 메서드를 사용하면 매개 변수를 최종적으로 만들 수 있습니다.

private static void move(final int cnt, final int row, final int col) { 
    ... 
}