-3

そこで、バックトラッキング アルゴリズムを使用して数独を実装しようとしました。私のコードが予期した出力を与えない理由がわかりません。

私がしたことは、数独の空のセル (0 で表される) をチェックするループを作成したことです。それが見つかると、その座標が possibleEntriescheck() という関数に渡されます。この関数は、possibleEntries[9] と呼ばれるグローバルに宣言された配列に、座標が最初に渡されるセルに入力できる可能性のある数字を書き込みます。

これらのビデオからこのアルゴリズムを学びました: https://www.youtube.com/watch?v=NuodN41aK3g https://www.youtube.com/watch?v=QI0diwmx3OY

予想される出力は、解かれた数独です。期待通りの性能を発揮しません。むしろ凍る。少しの助けが大きな意味を持つでしょう。ありがとうございました。

#include <stdio.h>
#include <stdlib.h>
int board[9][9] = {
                  {3, 0, 6, 5, 0, 8, 4, 0, 0},
                  {5, 2, 0, 0, 0, 0, 0, 0, 0},
                  {0, 8, 7, 0, 0, 0, 0, 3, 1},
                  {0, 0, 3, 0, 1, 0, 0, 8, 0},
                  {9, 0, 0, 8, 6, 3, 0, 0, 5},
                  {0, 5, 0, 0, 9, 0, 6, 0, 0},
                  {1, 3, 0, 0, 0, 0, 2, 5, 0},
                  {0, 0, 0, 0, 0, 0, 0, 7, 4},
                  {0, 0, 5, 2, 0, 6, 3, 0, 0},
                  };
int possibleEntries[9];
void possibleEntriescheck(int i, int j)
{
    int x,a=0,k,l,y;
    for(x=0;x<9;x++)
        possibleEntries[x]=0;
    for(x=0;x<9;x++)
    {
        if(board[i][x]!=0)
            possibleEntries[board[i][x]-1]=1;
    }

    for(x=0;x<9;x++)
    {
        if(board[x][j]!=0)
            possibleEntries[board[x][j]-1]=1;
    }

    if(i==0 || i==1 || i==2)
        k=0;
    else if(i==3 || i==4 || i==5)
        k=3;
    else
        k=6;

    if(j==0 || j==1 || j==2)
        l=0;
    else if(j==3 || j==4 || j==5)
        l=3;
    else
        l=6;

    for(x=k;x<k+3;x++)
    {
        for(y=l;y<l+3;y++)
            if(board[x][y]!=0)
                possibleEntries[board[x][y]-1]=1;
    }
    for(x=0;x<9;x++)
    {
        if(possibleEntries[x]==0)
            possibleEntries[x]=x+1;
        else
            possibleEntries[x]=0;
    }
}
int isFull()
{
    int i,j;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(board[i][j]==0)
                return 0;
        }
    }
    return 1;
}
void solveSudoku()
{
    int i,j,x,b=0,k;
    if(isFull())
    {
        printf("The sudoku board is:\n");
        for(i=0;i<9;i++)
        {   
            for(j=0;j<9;j++)
                printf("\t%d",board[i][j]);
            printf("\n");
        }
    }
    else
    {
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                if(board[i][j]==0)
                {
                    possibleEntriescheck(i,j);
                    for(x=0;x<9;x++)
                    {
                        if(possibleEntries[x]!=0)
                        {
                            board[i][j]=possibleEntries[x];
                            solveSudoku();
                            board[i][j]=0;
                        }
                    }   
                }
            }
        }
    }
    return;
}
int main()
{
    solveSudoku();
}
4

1 に答える 1

2

バックトラッキングを正しく実装していません。ビデオでも説明されているように、実際のアルゴリズムは次のようになります。

solve():
    if the sudoku is solved
        print field
        terminate

    x,y = the next vacant field

    for each possible value in that field
        assign value to x,y
        call solve() recursively to try with the assigned value

    clear vacant field

今、あなたのコードは何をしますか

solve():
    if the sudoku is solved
        print field
        return

    for each field in the sudoku
        if field is vacant
            for each possible value
                assign value
                solve recursively
                reset field to unassigned

これで実際に数独が解けます。しかし、このアプローチには 2 つの問題があります。
A : 数独を解くと終了しません。実はこの間違いは、動画で紹介したコードにもありました。シンプルなreturn再帰呼び出しは、現在の呼び出しでメソッドを終了し、「1 つ上の呼び出し」で再帰を続行します。したがって、基本的に、アルゴリズムは可能な限りあらゆる方法で数独を解決します (複数ある場合、それ以外の場合は、値を割り当てる可能な方法を試行するだけです)。
B：これはもっと深刻です。アルゴリズムは、考えられるすべての解を生成するだけでなく、見つけられる可能性のある値を割り当てる順序をすべて試行します。オーバーヘッドは巨大であり、コードが単純に終了しない理由です。数独を 1 回解くだけでもかなりの時間がかかりますが、あなたのコードは何十億回も解きます。

これらの問題を解決すると、残りの部分が正しく実装されていれば、コードは正常に動作するはずです。また、空のフィールドの検索とフィールドが空かどうかのテストの両方を最適化することをお勧めします。これらはかなり簡単に実行でき、速度が向上するためです。最初に空のフィールドのリストを生成し、それを繰り返し (再帰レベルごとに 1 つのフィールド)、リスト全体が処理されたら終了します。例えば：

solve(vacant, count):
    if count == 0
        print the field
        terminate

    x, y = vacant[count]
    count++

    for each possible value assignable to the field
        assign value to x, y
        call solve(vacant, count) recursively

    clear field

あなたが遭遇するもう一つの問題は、デバッグするのがかなり醜くなるでしょう、それはこの行のおかげです:

int possibleEntries[9];

再帰で使用および上書きされるグローバル変数は、控えめに言っても悪い考えです。次のようなプログラムの実行を想像してみてください (ident は再帰レベルを示し、ident はアクションがグローバルであることを意味します)。

solve
 |
 ---> board empty? Nope
      x,y <- next vacant field
possible values <- possible values for x, y
      field[x, y] <- first value from possible values
      solve
       |
       ---> board empty? Nope
            x, y <- next vacant field
possible values <- possible values for x, y (overwrites global variable!!!)
           field[x, y] <- first value from possible values
           solve
            |
            ---> ...
       <--- return
       field[x, y] <- second value from possible values (WRONG!!!)
       ...

最後の割り当ては、現在作業中のフィールドに対して生成された可能な値のリストを使用しませんが、戻る前に再帰のどこかで訪れた別の値のリストを使用します。これは、次の 2 つの方法で解決できます。

  • 1 から 9 まで繰り返し、フィールドに割り当てられるかどうかを各番号ごとに個別に確認します
  • 再帰のレベルごとに個別のリストを保持する
于 2018-02-20T18:08:29.303 に答える