Sudoku recursion with backtracking

Question

재귀 backtracking 알고리즘을 사용하여 주어진 sudoku 퍼즐을 풀려고합니다. 내 스도쿠 해결사에 두 가지 문제가 있습니다. 첫째로, 퍼즐을 해결하지만, 백업을 재발행하고 프로세스에서 언 솔트합니다 (약 4718 개의 재귀를 해결하고 다른 이유로 10000 개 정도를 백업합니다). 두 번째 문제는이 문제를 해결하려는 시도에서 비롯됩니다. 나는 그것을 발견하면 솔루션 나는이처럼 보이는 isSolved 방법을 사용하여 발견 검증 솔루션을 보유하는 글로벌 매트릭스를 사용

public static boolean isSolved(int[][]puzzle){ 
      for(int i = 0; i<9; i++){ //y rotation 
        for(int j = 0; j<8; j++){ 
          if(puzzle[i][j]==0){ 
            return false; 
          } 
        } 
      } 
      return true; 
    } 

경우, 내 퍼즐, 0에있는 블록 그것은 비어있는 것과 같습니다. 그러나 이것은 리셋이되는 것으로 보이지만 어디에서 리셋되고 있는지 찾을 수는 없습니다. 포인터 또는 제안이나 포인터 어디에서 봐야합니까? 여기

내 해결 방법, 내가 다시 시간 내 주셔서 감사 중요한 라인

public static int[][] solve(int[][]puzzle, int x, int y){ 
      System.out.println("RecrDepth: " + recDepth); 
      recDepth++; 
      //using backtracking for brute force power of the gods(norse cause they obviously most b.a. 
      ArrayList<Integer> list = new ArrayList<Integer>(); 
      //next for both x and y 
      int nextx = getNextx(x); 
      int nexty = getNexty(x, y); 
      while(puzzle[y][x] != 0){ //progress until blank space 
        x = nextx; 
        y = nexty; 
        if(isSolved(puzzle)){ 
          System.out.println("resetting solution improperly"); 
          solution = puzzle; 
          return puzzle; 
        } 
        nextx = getNextx(x); 
        nexty = getNexty(x, y); 
      } 
      for(int i = 1; i<10; i++){ 
        if(isTrue(puzzle, y, x, i)) //isTrue checks column, row and box so we dont go down unnecessary paths 
          list.add(i); 
      } 
      for(int i=0; i<list.size(); i++){ //iterating through options in open squre recursing for each one 
        puzzle[y][x]= list.get(i); 
        if(isSolved(puzzle)){ 
          System.out.println("Resetting Solution"); //appears to reset solution here but only once that I see in print out 
          solution = puzzle; 
          return puzzle; 
        } 
        System.out.print("="); 
        puzzle = solve(puzzle, nextx, nexty); 
        puzzle[y][x] = 0;//clear spot upon backtracking THIS WAS WHAT I WAS MISSIN 
      } 
      return puzzle; 
    } 

주석을 첨부하고, 전체 코드를 읽는데 파일 wechtera에서 GitHub의에/ssolverOO이는 ssolver.java 파일이고 읽기는 ssolverin.txt입니다.

Answer 1

코드를 올바르게 이해했다면 문제는 재귀가 잘 구현되지 않았다는 것을 의미합니다. 즉, 프로그램은 루프가 끝난 후에도 루프를 계속 반복한다는 의미입니다 정답을 찾았습니다.

첫 번째 빈 칸에서 올바른 숫자는 4라고 말하십시오. 그러나 프로그램에서 고려할 수있는 가능한 숫자 목록은 {2, 4, 6, 7}입니다. 이 경우, 실제로 일어날 것으로 보이는 것은 실제로 4에서 옳은 답을 찾을 것이고 올바른 결과를 낼 것입니다. 그러나 그것은 여전히 ​​6과 7을 점검 할 것입니다. 그리고 (물론) 어떤 대답을 찾지 못할 것이기 때문에 입력을 공백으로 두어 원래 보드를 돌려줍니다.

이제 실제 응답을 저장하기 위해 전역 변수를 설정하는 데 어느 정도 올바른 생각이 있어야한다고 생각합니다. 문제는 배열 복사본을 생성하지 않고 단순히 포인터 (참조)를 복사하는 것입니다.

실제로 전체 배열을 복사하는 복사 방법을 만들 수 있지만 정답을 생성하더라도 알고리즘은 불필요하게 반복되어 시간을 낭비합니다.

public static final int SIZE = 9; 

public static boolean solve(int[][] s) { 

    for (int i = 0; i < SIZE; i++) { 
     for (int j = 0; j < SIZE; j++) { 
      if (s[i][j] != 0) { 
       continue; 
      } 
      for (int num = 1; num <= SIZE; num++) { 
       if (isValid(num, i, j, s)) { 
        s[i][j] = num; 
        if (solve(s)) { 
         return true; 
        } else { 
         s[i][j] = 0; 
        } 
       } 
      } 
      return false; 
     } 
    } 
    return true; 
}