3

重複の可能性:
Java の数独ソルバー、バックトラッキングと再帰を使用

再帰と総当たりを使用して数独を解くプログラムを作成しています。私の主な問題は、行き詰まったものを元に戻す方法を理解できないことです。

プログラムの一般的なアルゴリズムは次のとおりです。

  1. 数独のゼロの数を見つけます。

  2. 最初の 0 の位置に (getNextEmpty メソッドがこれを行います)、数字を挿入します (insertnumber は、値が数独ルールに準拠していることを確認し、準拠している場合は true を返します)。

  3. 次に、再帰呼び出しを行い、ゼロがなくなったら終了します (n はゼロの数です)。

  4. プログラムが動かなくなった場合は、後戻りして部分を変更する必要があります。しかし、これはどのように可能ですか？

Cell クラスは、調整するセルの位置を [row, column] 形式の配列で実際に保持します。そのセルに関連付けられた行、列、またはより小さいグリッドを返すメソッドがあります。

私は手持ちやすべてのコードを要求しているわけではありません。再帰を理解することに正当に興味があるので、正しい方向に微調整するだけで十分です。

public static int[][] getSolution(int[][] grid) {
    for (int i = 0; i < 9; i++) {
        System.arraycopy(grid[i], 0, SolveSudoku.grid[i], 0, 9);
    }// end for
    int n = getZeroes();
    return getSolution(n);
}//end getSolution

private static int[][] getSolution(int n) {
    if (n == 0) {
        return grid;        
    }//end if
    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break;
        }else {
            //I do not understand what I should do here
        }
    }//end for
    return getSolution(n - 1);
}//end getSolution
4

2 に答える 2

2

正しい方向へのナッジ。グリッドを解決するために必要なすべての情報を追跡しているわけではないため、アプローチを少し調整する必要があります。

private static int[][] getSolution(int n) {
    if (n == 0) {
       return grid;        
    }//end if

    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break; // means i fits in Cell
        } else {
            // i doesn't fit... try the next i
            // don't need to do anything
        }
    }//end for
    if (!fits) {
        // There are no numbers that fit in this Cell
        // What should happen?
        // Did I make a bad guess?
        // How do I BACKTRACK and correct a previous guess?
    }
    return getSolution(n - 1);
}//end getSolution
于 2012-03-01T00:31:58.793 に答える
1

通常、再帰的な総当りでは、以下のコードのような構文を使用します。これは、何らかのアクションを実行した後に数えることができるため、それが新しい「開始位置」です。したがって、これは次のようになります。

private void Guess(int[][] grid)
{
    if(/**grid is a solution **/)
        //signal success
    else
    {
        if(/*seed out any bad, unacceptable answers you may have missed*/)
            return;//this includes cases when there are no more zeros
        //for every possible move,
        //make a modified grid, with one move done, and call
        Guess(ModifiedGrid);//for every possible move, generally you can modify
        //grid itself, because its passed by value
    }
}
于 2012-03-01T00:27:59.107 に答える