이 응용 프로그램에서 재귀를 이해하는 데 문제가 있습니다.

Question

스도쿠 퍼즐에 대한 재귀 적 솔버를 작성했습니다. 내 프로그램이 더 쉽게 읽을 수 있도록 0으로 빈 자리를 저장합니다. 그리드를 더 잘 시각화하기 위해 아래 첨자 1부터 시작하여 원래의 퍼즐을 저장했습니다. 나는 재귀에 대한 완전한 이해를 가지고 있는지 확신 할 수 없다. 나는 그것이 퍼즐을 풀기 위해 궤도에있는 것처럼 보이는 출력을 얻고 있지만 거기에 있어서는 안되는 0을 남겨두고있다. 내 unsetSquare의 배치 또는 return 문과 관련이 있다고 생각합니다. 여기

는 그 후, 용액을 찾고 8로 진행 (9), (9)는 불법이고 그것이 가지고

************************************************** 
7 4 3 | 8 2 1 | 5 6 8 
2 6 8 | 0 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 9 
2 6 8 | 0 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 1 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 2 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 3 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 

통지 첫 번째 행의 끝에 ... 출력 샘플이며 for 루프의 끝 부분에 도달하여 0으로 바뀌고 계속됩니다. 보다 완벽한 솔루션을 얻으려면 첫 번째 행에서 다른 번호로 다시 시도하려면 어떻게해야합니까? 그것은해야

: 전체 보드가 해결되는 경우

는

if(board.isLegal()){ 
    if(addSquare(depth, outStream)) 
     return true; 
} 

수단은 롤백 여기

내가 문제를 볼 수 있습니다

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    for(int i = ONE; i <= NINE; ++i){ 
     for(int j = ONE; j <= NINE; ++j){ 
      if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){ 
       cout << i << "  " << j << endl; 
       return true; 
      } 
      //cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
      if(board.getSquare(i, j) == ZERO){ 
       //cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
       for(int k = ONE; k <= NINE; ++k){ 
        board.setSquare(i, j, k); 
        board.display(outStream); 
        if(board.isLegal()){ 
         return addSquare(depth, outStream); 
        } 
        else{ 
         board.unsetSquare(i, j); 

        } 
       } 
      } 

     } 
    } 
    board.display(outStream); 
    return false; 
} 

Answer 1

내가 잘못된 순서로 일도 있었고,하지 않을 권리 범위에. while 루프를 성공적으로 수행 한 후 for 루프를 사용하여 해결책을 찾았습니다.

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    for(int i = 1; i < 10; ++i){ 
     for(int j = 1; j < 10; ++j){ 
      if(board.getSquare(i, j) == 0){ 
       if(i == 10){ 
        return true; 
       } 
       for(int k = 1; k <= 9; ++k){ 
        board.setSquare(i, j, k); 
        if(board.isLegal() && addSquare(depth, outStream)){ 
         return true; 
        } 

       } 
       board.unsetSquare(i, j); 
       return false; 

      } 
     } 
    } 
} 

Answer 2

내 재귀 기능입니다 ... .

편집은 그것에 대해 생각 :

가 첫 번째 광장에 1을 넣어, 그것은 false를 반환합니다. 2 넣으려고하지 않으시겠습니까?

EDIT2 더 문제 :

if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){ 
      cout << i << "  " << j << endl; 
      return true; 
} 

이이 완료 체크 할 생각인가? 당신은 단지 1 개의 광장 만 확인합니다. 당신의 샘플에 가득 찼습니다! 더 0

EDIT3이 없음을 확인해야합니다 : 그것은 밝혀

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    //use flag to let you know if all completed 
    bool zeroFound = false; 
    for(int i = ONE; i <= NINE; ++i){ 
    for(int j = ONE; j <= NINE; ++j){ 
     //cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
     if(board.getSquare(i, j) == ZERO){ 
     zeroFound = true; 
     //cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
     for(int k = ONE; k <= NINE; ++k){ 
      board.setSquare(i, j, k); 
      board.display(outStream); 
      if(board.isLegal()){ 
      if(addSquare(depth, outStream)){ 
       return true; 
      } 
      else{ 
       board.unsetSquare(i, j); 
      } 
      } 
     } 
     } 
    } 
    } 
    board.display(outStream); 
    return !zeroFound; //true in case it is full! 
}