C++ - 스도쿠 게임을 해결하십시오.

Question

저는 C++을 처음 사용하고 있으며 숙제를해야합니다 (스도쿠). 나는 문제에 붙어있다.

문제는 스도쿠를 해결하는 검색 기능을 구현하는 것입니다.

조작법 : 해결책을 찾으려면 재귀 적 검색이 다음과 같이 사용됩니다. 숫자가 아직 할당되지 않은 필드 (d1 .... dn) (n> 1)가 있다고 가정합니다. 그런 다음 먼저 필드를 d1에 할당하고 전파를 수행 한 다음 반복적으로 검색을 시도합니다. 전파가 실패하는 경우 (필드가 이 비어 있음) 발생할 수 있습니다. 이 경우 검색이 실패하고 필드 중 하나에서 다른 숫자를 시도해야합니다. 검색은 재귀 적이므로 마지막으로 고려한 필드의 다음 자릿수는 입니다. 숫자가 하나도 없으면 검색이 다시 실패합니다. 에서이 값은 이전 필드와 다른 숫자를 시도하는 등으로 이어집니다. 숫자 d를하기 전에

이 그것을 할 필드를 지정하여 시도되어, 현재 보드의 카피 인 새로운 보드를 생성 ( 복사 생성자를 사용하여 새와 힙에서 보드를 할당)해야합니다. 그런 다음 만 복사에 대한 지정을 수행하십시오. 회귀 호출 이 성공적으로 반환되지 않으면 다음 게시판에 대해 이 시도 된 새 보드를 만들 수 있습니다.

나는 시도했다 : 재귀 호출을 사용하는 경우

// Search for a solution, returns NULL if no solution found 
Board* Board::search(void) { 
    // create a copy of the cur. board 
    Board *copyBoard = new Board(*this); 
    Board b = *copyBoard; 

    for(int i = 0; i < 9; i++){ 
     for(int j = 0; j < 9; j++){ 

       // if the field has not been assigned, assign it with a digit 
      if(!b.fs[i][j].assigned()){ 
       digit d = 1; 

        // try another digit if failed to assign (1 to 9) 
       while (d <=9 && b.assign(i, j, d) == false){ 
         d++; 


         // if no digit matches, here is the problem, how to 
         // get back to the previous field and try another digit? 
         // and return null if there's no pervious field 
       if(d == 10){ 
         ... 
        return NULL; 
       } 
      } 
     } 
    } 
    return copyBoard; 
} 

또 다른 문제는? 어떤 팁? 고마워!

전체 명령 캔 여기에서 발견되었다 : http://www.kth.se/polopoly_fs/1.136980!/Menu/general/column-content/attachment/2-2.pdf

코드 : 코드에는 재귀가 없습니다 http://www.kth.se/polopoly_fs/1.136981!/Menu/general/column-content/attachment/2-2.zip

Answer 1

. 한 번만 각 필드를 방문하여 값을 할당 할 수는 없습니다. 문제는 당신이 필드 (3,4)에 5를 할당 할 수 있으며 필드 (6,4)에 도달했을 때만 5시 (3 , 4). 결국 (3,4)로 돌아와 다른 값을 시도 할 때까지 재귀에서 벗어나야합니다.

재귀를 사용하면 중첩 된 for 루프를 사용하여 필드를 방문하지 않고 다음 필드를 재귀 호출로 방문 할 수 있습니다. 마지막 필드에 도달했거나 모든 가능성을 시도한 다음 이전 필드로 돌아가는 기능을 그대로 두십시오.

---

(!) 참고는 : 확실히이 작업에 동적 메모리를 할당하지 않습니다

//Board *copyBoard = new Board(*this); 
Board copyBoard(*this); //if you need a copy in the first place 

Answer 2

기본적으로 당신이 시도 할 수 있습니다 것은이 (pseudocode'ish) 같은 것입니다

bool searchSolution(Board board) 
{ 
Square sq = getEmptySquare(board) 
if(sq == null) 
    return true; // no more empty squares means we solved the puzzle 

// otherwise brute force by trying all valid numbers 
foreach (valid nr for sq) 
{ 
    board.doMove(nr) 

    // recurse 
    if(searchSolution(board)) 
     return true 

    board.undoMove(nr) // backtrack if no solution found 
} 

// if we reach this point, no valid solution was found and the puzzle is unsolvable 
return false; 

} 

getEmptySquare (...) 함수는 무작위로 빈 사각형을 반환하거나 옵션 수가 가장 적은 사각형을 반환 할 수 있습니다. 후자를 사용하면 알고리즘이 훨씬 빠르게 수렴됩니다.