c++ - 数独生成 : it goes in loop

Question

我正在尝试编写一个数独生成器算法，这是我的 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

你必须进一步回溯。第二行的最后一个单元格中没有有效条目。我不确定贪心算法能否用作数独生成器。我会尝试使用基于堆栈树的方法。