5

次のコード スニペットについて質問があります。これは、空のセルを埋めて数独パズルを解く数独ソルバーです。ソルバー メソッドの背後にあるロジックを実際に取得することはできません。k=1-9 を試した後に false を返し、すべてのセルをループした後に true を返すのはなぜですか。私が考えたのは、再帰的に solver() メソッドに入り、数独が完了すると、呼び出し順序として true が返され、最後に最初に呼び出された solver() が true を返すということです。上記の 2 つの「リターン」が発生するいくつかのシナリオを省略しなければならないと思います。なぜそれらの「リターン」が存在する必要があるのか​​ 誰かが私に説明できますか?

public class Solution {

public static void main(String[] args) {
    Solution s = new Solution();
    char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'},
                      {'5', '.', '.', '.', '7', '9', '.', '.', '4'},
                      {'3', '.', '.', '.', '1', '.', '.', '.', '.'},
                      {'6', '.', '.', '.', '.', '.', '8', '.', '7'},
                      {'.', '7', '5', '.', '2', '.', '.', '1', '.'},
                      {'.', '1', '.', '.', '.', '.', '4', '.', '.'},
                      {'.', '.', '.', '3', '.', '8', '9', '.', '2'},
                      {'7', '.', '.', '.', '6', '.', '.', '4', '.'},
                      {'.', '3', '.', '2', '.', '.', '1', '.', '.'}};

    s.solver(board);
}
public boolean solver(char[][] board) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (board[r][c] == '.') {
                for (int k = 1; k <= 9; k++) {
                    board[r][c] = (char) ('0' + k);
                    if (isValid(board, r, c) && solver(board)) {
                        return true;
                    } else {
                        board[r][c] = '.';
                    }
                 }
                return false;
             }
         }
     }
    return true;
}

public boolean isValid(char[][] board, int r, int c) {
    //check row
    boolean[] row = new boolean[9];
    for (int i = 0; i < 9; i++) {
        if (board[r][i] >= '1' && board[r][i] <= '9') {
            if (row[board[r][i] - '1'] == false) {
                row[board[r][i] - '1'] = true;
            } else {
                return false;
            }
        }
    }

    //check column
    boolean[] col = new boolean[9];
    for (int i = 0; i < 9; i++) {
        if (board[i][c] >= '1' && board[i][c] <= '9') {
            if (col[board[i][c] - '1'] == false) {
                col[board[i][c] - '1'] = true;
            } else {
                return false;
            }
        }
    }

    //check the 3*3 grid
    boolean[] grid = new boolean[9];
    for (int i = (r / 3) * 3; i < (r / 3) * 3 + 3; i++) {
        for (int j = (c / 3) * 3; j < (c / 3) * 3 + 3; j++) {
            if (board[i][j] >= '1' && board[i][j] <= '9') {
                if (grid[board[i][j] - '1'] == false) {
                    grid[board[i][j] - '1'] = true;
                } else {
                    return false;
                }
            }
         }
    }

    return true;
}
}
4

3 に答える 3

4

各再帰呼び出しは、最初の '.' を処理します。まだ取り扱い中。それは仮に数字に置き換えられます。変更が成功した (ボードを無効にしない) 場合は、再帰します (次の '.' を試行します)。それが失敗する場合は、ローカルで行われた変更を元に戻し、false を返します。これは、この検索ブランチで試行された数字が無効であるためです。これは、呼び出し元 (root まで) に次の選択を強制することを意味します。

于 2013-03-03T05:16:05.283 に答える
2

これは単純なブルート フォース ソルバーです。すべてのオープンスペースですべての数字を試すだけです。所定のスペースに数字を入力した後、ボードが「有効」(ゲームのルールに従っている) である場合、同じソルバー関数が再帰的に呼び出され、別の空白スポットが埋められ、ボードがまだ有効であるかどうかがテストされます。の上。

これは非常に効率の悪いソルバーですが、コーディングは簡単です。

于 2013-03-03T05:05:10.410 に答える
0

このコードは Sudoku をチェックします。正しい場合は check_sudoku() メソッドが true を返し、間違っている場合は重複した要素を持つ行と列の番号を表示します。

  public static void main(String[] args) {
    int array[][]={{9,6,3,1,7,4,2,5,8},
                   {1,7,8,3,2,5,6,4,9},
                   {2,5,4,6,8,9,7,3,1},
                   {8,2,1,4,3,7,5,9,6},
                   {4,9,6,8,5,2,3,1,7},
                   {7,3,5,9,6,1,8,2,4},
                   {5,8,9,7,1,3,4,6,2},
                   {3,1,7,2,4,6,9,8,5},
                   {6,4,2,5,9,8,1,7,3}};

    Sudoku sudoku=new Sudoku();
    if(sudoku.check_sudoku(array))
    {
        System.out.println("You won the game :)");
    }


}


public class Sudoku {

private int temp1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, temp2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private int data1, data2;

public boolean check_sudoku(int array[][]) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            data1 = array[i][j];
            data2 = array[j][i];
            if (data1 >= 10 || data2 >=10 || data1 <= 0 || data2 <= 0) {
                System.out.println("Invalid Solution because value must be in between 1 to 9");
                return false;
            } else if (temp1[data1 - 1] == 0 || temp2[data2 - 1] == 0) {
                System.out.println("Invalid Solution please check " + (i + 1) + " row " + (j + 1) + " column or " + (j + 1) + " row " + (i + 1) + " column");
                return false;
            } else {
                temp1[data1 - 1] = 0;
                temp2[data2 - 1] = 0;
            }
        }
        int check1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int check2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        temp1 = check1;
        temp2 = check2;
    }
    return true;
}

}

于 2017-08-19T20:27:07.140 に答える