스도쿠 세대 : 그것은 루프

Question

내가 스도쿠 생성기 알고리즘을 wiriting하기 위해 노력하고있어

을 간다, 이건 내 C++ 코드 :

void generateSudoku(num sudoku[][N]) 
{ int i,j,k; 
    int vett[N],n,old; 
    //clean the sudoku matrix filling it with -1 
    for(i=0;i<N;i++) 
     for(j=0;j<N;j++) 
      sudoku[i][j].val=-1; 
    //generate the sudoku 
    for(i=0;i<N;){ 
     for(j=0;j<N;){ 
      k=0; 
      clean(vett,N); //fills the vector with -1 
      old=sudoku[i][j].val; //saves the actual value 
      do{ 
       if(k<9){ 
        do{ 
         n=rand()%9+1; 
        }while(find(vett,N,n)); //generate n while it already exists in vett 
        vett[k++]=n; 
        if((!(exists(sudoku,i,j,n))) && (n!=old)){ //if it not exists on row, column and sub-matrix and it's different between the old value, it's OK 
         sudoku[i][j++].val=n; 
         if(j==N) i++; 
         k=10; 
         } 
       } 
       else{ 
        sudoku[i][j].val=-1; 
        if(j>0) j--; 
        else if(i>0){ 
         j=N-1; 
         i--; 
        } 
        k=10; 
       } 

      }while(k<=9); 
     } 
    } 
} 

그것은 루프에 간다 나는 이유를 알고

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

을

이 예제에서는 *가있는 곳에서 6-1과 1-6을 계속 생성하고 끝내지 않습니다. 그러나 그것이 왜 반복되는지를 이해하더라도, 나는 그것을 고치는 가장 좋은 방법을 모른다. 누군가 나를 도울 수 있습니까?

Answer 1

더 이상 역 추적해야합니다. 두 번째 행의 마지막 셀에는 유효한 항목이 없습니다. 나는 욕심 많은 알고리즘이 스도쿠 생성기로 작동 할 지 확신하지 못합니다. 대신 스택 트리 기반 접근 방식으로 시도 할 것입니다.

Answer 2

(테스트되지 않은) 도움이 될 수 있습니다 다음은

void restore(std::vector<int>& v) { 
    v.clear(); 
    for (int i = 0; i != 9; ++i) { 
     v.push_back(1 + i); 
    } 
} 

void generate(int (&sudoku)[9][9]) 
{ 
    std::vector<int> allowedSymbols[9][9]; 

    bool succeed = true; 
    for(int i = 0, j = 0; i != 9;) { 
     if (succeed) { 
      restore(allowedSymbols[i][j]); 
      succeed = false; 
     } 
     while (!allowedSymbols[i][j].empty()) { 
      int index = rand() % allowedSymbols[i][j].size(); 

      if (!exists(sudoku, i, j, allowedSymbols[i][j][index])) { //if it not exists on row, column and sub-matrix, it is OK 
       succeed = true; 
       break; 
      } 
      allowedSymbols[i][j].erase(allowedSymbols[i][j].begin() + index); 
     } 
     if (succeed) { 
      ++j; 
      if (j == 9) { 
       j = 0; 
       ++i; 
      } 
     } else { 
      // backtrack. 
      --j; 
      if (j == -1) { 
       j = 8; 
       --i; 
      } 
      allowedSymbols[i][j].erase(std::find(allowedSymbols[i][j].begin(), 
               allowedSymbols[i][j].end(), 
               sudoku[i][j])); 
     } 
    } 
}