스도쿠 재귀 backtracking, 너무 일찍 unrecursing

Question

그래서 나는 스도쿠 솔버를 C++로 작성하고 약간의 걸림돌을 만났습니다. 아래에 내 보드 코드를 해결합니다. 그것은 퍼즐의 첫 번째 3 행에 대해서는 작동하지만 4 행의 끝에 도달 할 때 unrecurses. gdb의 코드를 살펴보면 4 번째 행의 끝 부분에 도달하고 6 번째 행으로 역 추적하여 끝까지 시도한 다음 다시 시도합니다.

코드에 대한 몇 가지 다른 점은 스도쿠 보드를 보유하고있는 행렬이 1,1,0,0에서 시작한다는 것입니다. 따라서 solveBoard가 처음 호출 될 때 매개 변수는 (1, 1, 0)입니다. 거기에 대한 더 많은 통찰을 위해 setCell 및 checkConflicts 함수를 첨부했습니다. 각 행, 열 또는 사각형 이미 배치 된 값을 저장할 세 벡터 rowConf, colConf 및 squConf 있습니다. 나는 이것을 몇 시간 동안 해왔고 3 행을 지나칠 수 없다. 모든 도움이 크게 설명됩니다. 감사!

편집 : 추가 clearCell는()

bool board::solveBoard(int i, int j, int count) 
{ 

    if (j > 9) 
    { 
     j = 1; 
     i++; 

     printBoard(); 
     if (isSolved()) 
     { 
      printBoard(); 
      cout <<"The Board has been solved!" <<endl 
       <<" The number of recursive calls was: " <<count <<endl; 
      return true; 
     } 
    } 

    if (isBlank(i, j)) 
    { 
     for (int n = 1; n < 10; n++) 
     { 
      if (setCell(i, j, (char)n + '0')) 
      { 
       if (solveBoard(i, j + 1, count + 1)) 
       { 
        return true; 
       } 
       } 
      } 
     } 
     else 
     { 
      return (solveBoard(i, j + 1, count + 1)); 
     } 

     clearCell(i, j); 
     return false; 
} 

bool board::setCell(int i, int j, char val) 
{ 
    int intVal; 

    intVal = atoi(&val); 

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize && 
     intVal >= 1 && intVal <= BoardSize) 
    { 
     if (!(checkConflicts(intVal, i, j, squareNumber(i, j)))) 
     { 
     return false; 
     } 

     value[i][j] = intVal; 

     // Set flags of the conflicts 
     rowConf[i][intVal] = true; 
     colConf[j][intVal] = true; 
     squConf[squareNumber(i, j)][intVal] = true; 

     return true; 
    } 
    else 
    { 
     throw rangeError("bad value in setCell"); 
    } 
} 

bool board::checkConflicts(int val, int i, int j, int k) 
{ 
    if (i < 1 && i > BoardSize && j < 1 && j > BoardSize && 
     k < 1 && k > BoardSize && val < 1 && val > BoardSize) 
    { 
     throw rangeError("bad value in checkConflicts()"); 
    } 

    if (rowConf[i][val] || colConf[j][val] || squConf[k][val]) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
} 

Initial Board: 
----------------------------- 
| 3  | 8 |   ----------------------------- 
|   | 7  |  5 ----------------------------- 
| 1  |   |   ----------------------------- 
----------------------------- 
|   |   | 3 6  ----------------------------- 
|  2 |  4 |   ----------------------------- 
| 7 |   |   ----------------------------- 
----------------------------- 
|   | 6 | 1 3  ----------------------------- 
| 4 5 | 2  |   ----------------------------- 
|   |   | 8  ----------------------------- 
----------------------------- 

Final Output: 
----------------------------- 
| 3 2 4 | 1 8 5 | 6 7 9 ----------------------------- 
| 6 8 9 | 7 2 3 | 4 1 5 ----------------------------- 
| 1 5 7 | 4 9 6 | 2 8 3 ----------------------------- 
----------------------------- 
|   |   | 3 6  ----------------------------- 
|  2 |  4 |   ----------------------------- 
| 7 |   |   ----------------------------- 
----------------------------- 
|   | 6 | 1 3  ----------------------------- 
| 4 5 | 2  |   ----------------------------- 
|   |   | 8  ----------------------------- 
----------------------------- 

void board::clearCell(int i, int j) 
{ 
    int intVal; 

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize) 
    { 
     if (value[i][j] != -1) 
     { 
      intVal = value[i][j]; 
      rowConf[i][intVal] = false; 
      colConf[j][intVal] = false; 
      squConf[squareNumber(i, j)][intVal] = false; 
      value[i][j] = -1; 
     } 
    } 
    else 
    { 
     throw rangeError("bad value in setCell"); 
    } 
} 

Answer 1

귀하의 문제는 대부분 여기에 있습니다 : 그것은이 else를 통과하지 않는 이유는이 섹션을 통해 것입니다 어떻게 든

if (isBlank(i, j)) 
{ 
    for (int n = 1; n < 10; n++) 
    { 
     if (setCell(i, j, (char)n + '0')) 
     { 
      if (solveBoard(i, j + 1, count + 1)) 
      { 
       return true; 
      } 
      } 
     } 
    } 

결국 그것은 돌아 오지 않았기 때문에 멈추게됩니다.

이 더 디버깅이 필요하지만 여기에 솔루션으로 이어질 수있는 생각이다 :

이

if (isBlank(i, j)) 
{ 
    for (int n = 1; n < 10; n++) 
    { 
     if (setCell(i, j, (char)n + '0')) 
     { 
      if (solveBoard(i, j + 1, count + 1)) 
      { 
       return true; 
      } else { 
       echo 'Looks like it ended on the farthest-level..'; 
      } 
     } else { 
      echo 'Looks like it ended on the second-farthest level.'; 
     } 
    } 

Answer 2

atoi 함수는 인수로 문자열을 기대하고, 그 문자 '\0' 종료 문자의 배열이다 , ASCII NUL. 매개 변수를 문자 (일부 arrray 문자)에 대한 포인터로 지정하지만 은 0이 종료됨을 보장하지 않습니다.|| 사업자 대신의 첫 번째 if에서 &&을 가져야한다 intVal = (int)val - '0';

그리고 당신의 checkConflicts으로 intVal = atoi(&val);을 교체하십시오.

이것은 아마도 오류의 원인이 아니지만 확실히 수정해야합니다.