C. 프로그램의 스도쿠 해 찾기가 특정 경우에 중지되고 이유를 모르겠 음

Question

나는 sudoku 퍼즐을 해결하는 클래스를 위해 C 프로그램을 작성 중입니다. 우리가 구현해야하는 세 가지 방법이 있습니다. 먼저, 가능한 한 선택할 수있는 올바른 사각형을 각 사각형에 배치하고 더 이상 찾을 수 없을 때까지 반복합니다. 다음으로 무차별 대입 (brute force)을 사용하여 가능한 한 가장 작은 수를 각 사각형에 배치합니다. 나는이 두 가지 방법을 사용하고있다. 마지막 방법은 무차별 함수 (brute force function)의 일부인 역 추적 (back tracking)을 통한 무차별 한 힘입니다. 그것은 일반적인 무차별 대항력과 같은 방식으로 작동합니다. 단, 숫자를 배치 할 수없는 사각형에 도달하면 이전 사각형으로 이동하고 그 다음으로 높은 숫자를 배치합니다. 이것이 구현되면 모든 주어진 스도쿠 퍼즐을 해결해야하지만, 이것이 내가 문제를 일으키는 곳입니다.

나는 세 가지 방법을 모두 구현했으며, 다른 예제 스도쿠 퍼즐이 주어졌습니다. 첫 번째 "단일 선택"방법 만 사용하여 해결할 수있는 것도 있고, "단일 선택"을 사용하여 해결할 수있는 것도 있습니다. "역 추적없는 무력"및 "단일 선택"과 "역 추적과 무차별 적"을 사용하는 다른 사람들. 내 프로그램은 "단일 선택"퍼즐과 "단일 선택"및 "역 추적없는 무차별 적"퍼즐 모두에서 작동합니다. 그러나 "단일 선택"과 "역 추적을 통한 무차별 대항"퍼즐에는 효과가 없습니다.

내가 이해하지 못하는 이상한 부분은, 역 추적 퍼즐의 경우, 무차별 대입 기능이 호출되기 전에 프로그램이 작동을 멈추는 것입니다.

가 여기 내 주요 기능입니다 : 프로그램이 작동을 멈 춥니 다 어디

#include <stdio.h> 
#include "sudokusolver.h" 
int main() 
{ 
    int puzzle[9][9], i, j, count, attempts=0, backTracks=0; 
    readSudoku(puzzle); 
    printf("a\n"); 
    do 
    { 
     count=0; 
     for(i=0;i<9;i++) 
     { 
     for(j=0;j<9;j++) 
     { 
      if(singleCandidate(puzzle, i, j)==1) 
       count++; 
     } 
     } 
    }while(count!=0); 
    bruteForce(puzzle, &attempts, &backTracks); 
    printSudoku(puzzle); 
    return 0; 
} 

내가 사용 "에서 printf ("는 \ n을 ")"표시합니다.

다음은 작동하는 출력의 예입니다. 이것은 "단일 선택"방법과 "역 추적없이 무차별 한"방법을 사용하여 작동하는 스도쿠 퍼즐의 예입니다. 제로의 숫자는 퍼즐의 빈 칸을 나타냅니다. :

Enter line 1: 010042000 
Enter line 2: 008053010 
Enter line 3: 900071560 
Enter line 4: 400700600 
Enter line 5: 067205130 
Enter line 6: 002004005 
Enter line 7: 080430001 
Enter line 8: 030120700 
Enter line 9: 000580090 
a 
315|642|987 
678|953|412 
924|871|563 
----------- 
453|718|629 
867|295|134 
192|364|875 
----------- 
786|439|251 
539|126|748 
241|587|396 

그리고 이것은 작동하지 않는 출력의 예입니다. 이 무한 루프와^C 인 경우, 상기 프로그램은 계속 실행

Enter line 1: 300910750 
Enter line 2: 100570009 
Enter line 3: 009000000 
Enter line 4: 020740090 
Enter line 5: 900000003 
Enter line 6: 010069020 
Enter line 7: 000000300 
Enter line 8: 700085006 
Enter line 9: 098034002 
^C 

날 종료있다 : 이것은 "단일 선택"및 "되돌아와 무력"을 사용하여 해결해야하는 예시 퍼즐 프로그램에서 보시다시피,이 프로그램은 심지어 스도쿠 퍼즐에서 읽는 곳 바로 아래의 printf ("a")에 도달하지도 않으며, 퍼즐이기 때문에 이상한 "역 추적과 함께 무차별 적"기능을 호출하기도 전에 작동하지 않는 역 추적으로 무차별 한 힘이 필요합니다.

는 여기가에 갇히지 될 것 같습니다 readSudoku 기능입니다 :

void readSudoku(int puzzle[][9]) 
{ 
    int i, j; 
    for(i=0;i<9;i++) 
    { 
     printf("Enter line %d: ", i+1); 
     for(j=0;j<9;j++) 
     { 
     scanf("%1d", &puzzle[i][j]); 
     } 
    } 
} 

그리고 여기이 전혀 의미가없는 아주 이상한 문제가

void bruteForce(int puzzle[][9], int *attempt, int *backtracks) 
{ 
    int stable[9][9], i, j, k, found=0, temp=0; 
    for(i=0;i<9;i++) 
    { 
     for(j=0;j<9;j++) 
     { 
     if(puzzle[i][j]==0) 
      stable[i][j]=0; 
     else 
      stable[i][j]=1; 
     } 
    } 
    for(i=0;i<9;i++) 
    { 
     for(j=0;j<9;j++) 
     { 
     for(k=0;k<9;k++) 
     { 
      if(checkValid(puzzle, i, j, k+1)==1) 
      { 
       puzzle[i][j]=k+1; 
       break; 
      } 
      if(k==8) 
       break; 
     } 

     while(puzzle[i][j]==0) 
     { 
      found=0; 
      temp=j-1; 
      for(j=temp;j>=0;j--) 
      { 
       if(stable[i][j]==0) 
       { 
        found=1; 
        break; 
       } 
      } 
      temp=i-1; 
      if(found==0) 
      { 
       for(i=temp;i>=0;i--) 
       { 
        for(j=8;j>=0;j--) 
        { 
        if(stable[i][j]==0) 
        { 
         found=1; 
         break; 
        } 
        } 
       if(found==1) 
        break; 
       } 
      } 
      found=0; 
      temp=puzzle[i][j]+1; 
      for(k=temp;k<9;k++) 
      { 
       if(checkValid(puzzle, i, j, k+1)==1) 
       { 
        found=1; 
        puzzle[i][j]=k+1; 
        break; 
       } 
      } 
      if(found==0) 
       puzzle[i][j]=0; 
     } 
     } 
    } 
} 

구현 되돌아와 bruteforce 기능입니다 나에게 도움이된다면.

Answer 1

나는 문제가 singleCandidate()에있는 것 같아요. 그 소스를 볼 수는 없지만, 퍼즐을 변경하지 않으면 1을 리턴하지 않는다는 것을 확인해야합니다. 그 이유는 퍼즐이 끝없이 반복되기 때문입니다.

입력이 잘못되었을 때 (예 : 스도쿠가 해결책이없는 경우) 어떻게 작동하는지 확인하십시오.당신의 bruteForce에서

Answer 2

, 당신은

/* No legal guess found, so backtrack */ 
while(puzzle[i][j]==0) 
{ 
    /* Find previous guessed position */ 
    /* the last guess was as puzzle[i][j] */ 
    temp=puzzle[i][j]+1; 
    for(k=temp;k<9;k++) 
    { 
     if(checkValid(puzzle, i, j, k+1)==1) 
     { 
      found=1; 
      puzzle[i][j]=k+1; 
      break; 
     } 
    } 
    if(found==0) 
     puzzle[i][j]=0; 
} 

그래서 이전 생각보다 큰 하나 k의 시작 값을 설정해야합니다. 그러나 셀을 k+1으로 설정하려고 시도하지 않으므로 old_guess + 1으로 설정하지 마십시오.

따라서 correct_value - 1을 추측 한 경우 결코 correct_value을 시도하지 마십시오. 역 추적을 필요로하는 퍼즐의 경우, 어떤 시점에서 상황이 발생할 가능성이 압도적으로 높습니다.

따라서 found == 0부터 puzzle[i][j] = 0을 설정하고 다음 추측 위치를 검색하여 백 트랙을 계속 진행하십시오.

하지만 당신은 이미 첫 번째 추측 위치에 당신이 다음 정의되지 않은 동작을 호출 puzzle[-1][-1], 액세스

found=0; 
temp=j-1; 
for(j=temp;j>=0;j--) 
{ 
    if(stable[i][j]==0) 
    { 
     found=1; 
     break; 
    } 
} 
// Here, j == -1 
temp=i-1; 
if(found==0) 
{ 
    // if i == 0 
    for(i=temp;i>=0;i--) 
    { 
    // i is set to -1 and the loop ends right now, with i == -1 and j == -1 
    // if i was > 0, j is decremented from 8 to -1 for all i down to 0 in the inner loop 
     for(j=8;j>=0;j--) 
     { 
      if(stable[i][j]==0) 
      { 
       found=1; 
       break; 
      } 
     } 
     if(found==1) 
      break; 
     // i is finally set to -1, with j still -1 
    } 
} 
found=0; 
temp=puzzle[i][j]+1; 

을 경우.

당신은 잘못된 메모리 액세스 충돌로 이어질하지 않는만큼 불운 경우 - 경우로 보인다 - 일부 k를 들어, 아마도 checkValid(-1,-1,k+1) 반환 1, 다음, 다시 퍼즐을 해결하기 위해 노력을 선도 시작 같은 루프. 터미널이 정상 버퍼링 모드로 설정되어있는 경우

인정 하듯이, printf("a\n");는 a를 인쇄한다,하지만 난 생각이 인쇄 버퍼가 readSudoku 마술 되돌아을 필요로하는 퍼즐을 감지하고 작업을 거부보다 ​​플러시되지 않습니다 것을 더 가능성 .