2

私は数独バックトラッキングソルバーを作成しましたが、それは問題なく動作しますが、たとえばこの数独が与えられた場合、それが無効であるために数独が解決できない場合はエラーを出したいです：

http://img5.imageshack.us/img5/2241/sudokugq.jpg

解決できない場合、解決方法でエラーが発生するようにするにはどうすればよいですか？私はいつもゼロで終わるか、ループで立ち往生しています。

    public void solve( int row, int col ) throws Exception
   {
      // Throw an exception to stop the process if the puzzle is solved
      if( row > 8 ){
        //Gelöst
      }
      // If the cell is not empty, continue with the next cell
      if( sudo[row][col] != 0 ){
         next( row, col ) ;
        }
      else
      {
         // Find a valid number for the empty cell
         for( int num = 1; num < 10; num++ )
         {
            if( checkHorizontal(row,num) == false && checkVertikal(col,num)== false&& checkBox(row,col,num)== false )
            {
               sudo[row][col] = num ;


               // Delegate work on the next cell to a resudosive call
               next( row, col ) ;
            }
         }

         // No valid number was found, clean up and return to caller
         sudo[row][col] = 0 ;
      }

   }

   //Ruft solve für das nächste Feld auf
   public void next( int row, int col ) throws Exception
   {
      if( col < 8 )
         solve( row, col + 1 ) ;
      else
         solve( row + 1, 0 ) ;
   }
4

1 に答える 1

0

コードにたどり着いたときsudo[row][col] = 0 ;は、四角形のすべての値を試してみたところ、それらのいずれにも解決策が見つかりませんでした。確かに、それはあなたが解決策のない状態であきらめることを決定するポイントです.

さらに考えてみると、私はほぼ正しいと思います。このコードをヒットし、これが最初に試したセル (つまり、最初に見つかった空のセル) である場合、それが失敗の瞬間です。

ところで-コメントで提案したように、例外を使用して解決策を示すのが良い考えかどうかはわかりません。

これで、投稿したボードが正しく拒否されるようになりました。最初の行に 2 つの「3」があるだけでなく、最初の列にも 2 つの「5」があることに注意してください。このコードは今私のために働くようです。不溶性のもので試してみるのもいいかもしれません。

public class Test {

    static final int S = 9;
    int[][] sudo;

    public Test() {
        // Just leave it empty.
        sudo = new int[S][S];
    }

    public Test(int[][] sudo) {
        this.sudo = sudo;
    }

    // This number should not appear anywhere in the row.
    public boolean checkHorizontal(int row, int num) {
        for (int i = 0; i < S; i++) {
            if (sudo[row][i] == num) {
                return false;
            }
        }
        return true;
    }

    // This number should not appear anywhere in the col.
    public boolean checkVertical(int col, int num) {
        for (int i = 0; i < S; i++) {
            if (sudo[i][col] == num) {
                return false;
            }
        }
        return true;
    }

    // This number should not appear anywhere in the box.
    private boolean checkBox(int row, int col, int num) {
        // Round down to nearest 3.
        int r = (row / 3) * 3;
        int c = (col / 3) * 3;
        for (int i = r; i < r + 3; i++) {
            for (int j = c; j < c + 3; j++) {
                if (sudo[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    boolean check(int row, int col, int num) {
        // All checks must pass.
        return checkHorizontal(row, num)
                && checkVertical(col, num)
                && checkBox(row, col, num);
    }

    public boolean solve(int row, int col) {
        // Got to the end?
        if (row >= S) {
            //Gelöst
            return true;
        }
        // If the cell is empty
        if (sudo[row][col] == 0) {
            // Find a valid number for the empty cell
            for (int num = 1; num < 10; num++) {
                // Can this number be put there?
                if (check(row, col, num)) {
                    // Yes!
                    sudo[row][col] = num;
                    // Try that.
                    if (next(row, col)) {
                        return true;
                    }
                }
            }
            // Clean up.
            sudo[row][col] = 0;
        } else {
            // Move on.
            if (next(row, col)) {
                return true;
            }
        }
        // Failed to find a solution.
        return false;
    }

    //Ruft solve für das nächste Feld auf
    public boolean next(int row, int col) {
        if (col < S - 1) {
            // Step right.
            return solve(row, col + 1);
        } else {
            // Step down.
            return solve(row + 1, 0);
        }
    }

    public boolean boardOk() {
        // Initial test to ensure it is a valid array.
        // Must have that many rows.
        boolean ok = sudo.length == S;
        for (int row = 0; ok && row < S; row++) {
            // Each row must be that long.
            ok &= sudo[row].length == S;
            for (int col = 0; ok && col < S; col++) {
                // Each filled square must be valid.
                if (sudo[row][col] != 0) {
                    int num = sudo[row][col];
                    // Remove it.
                    sudo[row][col] = 0;
                    // Check it can be added.
                    ok &= check(row, col, num);
                    // Put it back.
                    sudo[row][col] = num;
                }
            }
        }
        return ok;
    }

    void solve() {

        if (boardOk()) {
            boolean solved = solve(0, 0);
            if (solved) {
                System.out.println("Solved!");
                print();
            }
        } else {
            System.out.println("Insoluble!");
            print();
        }
    }

    public void print() {
        for (int i = 0; i < sudo.length; i++) {
            System.out.println(Arrays.toString(sudo[i]));
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new Test().solve();
        int[][] test = {
            {0, 0, 6, 5, 8, 3, 3, 2, 7},
            {0, 0, 0, 0, 9, 0, 0, 5, 0},
            {5, 8, 0, 0, 0, 0, 0, 0, 3},
            {0, 3, 1, 0, 4, 0, 5, 0, 0},
            {0, 0, 0, 9, 2, 0, 3, 0, 6},
            {0, 0, 0, 0, 0, 0, 0, 0, 1},
            {3, 4, 2, 0, 0, 6, 9, 1, 5},
            {5, 0, 5, 4, 0, 9, 0, 3, 2},
            {0, 1, 0, 0, 0, 0, 0, 0, 4},};
        new Test(test).solve();
    }
}
于 2013-02-27T22:59:46.557 に答える