3

以前にもこのような投稿がいくつかあったことは知っていますが、役に立ちません。数独を解くプログラムを書いています。ここでアルゴリズムを見つけました: http://www.heimetli.ch/ffh/simplifiedsudoku.html。私はJavaでそれを書き込もうとしており、コンソールベースのプログラムから始めています。止める方法はあるのですが、なぜか無限ループに陥ってしまいます。

package sudokuSolver;

public class Solver {
static int[][] board;   //teh board
static boolean solved;          //if the sudoku is solved

public static void main(String[] args) throws Exception 
{
    //establish temporary board for now
    final int[][] TUE24JAN = {{0,0,9,0,0,0,8,0,0},
                              {0,1,0,0,2,0,0,3,0},
                              {0,0,0,7,0,8,0,0,0},
                              {2,0,0,0,8,0,0,0,7},
                              {0,3,0,1,0,2,0,4,0},
                              {4,0,0,0,7,0,0,0,5},
                              {0,0,0,6,0,3,0,0,0},
                              {0,8,0,0,9,0,0,7,0},
                              {0,0,6,0,0,0,9,0,0},};

    final int[][] WED25JAN = {{2,5,0,0,0,0,4,0,0},
                              {0,0,3,1,0,0,7,0,0},
                              {0,0,0,0,8,4,0,6,0},
                              {4,0,0,0,0,0,0,8,0},
                              {7,0,0,0,1,0,0,0,4},
                              {0,3,0,0,0,0,0,0,9},
                              {0,9,0,6,5,0,0,0,0},
                              {0,0,1,0,0,9,2,0,0},
                              {0,0,2,0,0,0,0,4,3},};

    board = TUE24JAN;
    solved = false;
    printBoard();

    solve(0,0);
    System.out.println("\n");
    printBoard();
}

public static void solve(int x, int y) throws Exception
{
    //catches the end of the line
    if(y > 8)
    {
        y = 0;
        x++;
    }

    //catches the end of the board
    if(x > 8 || solved)
    {
        solved = true;
        return;
    }
    //put a number in the cell
    for(int i = 1; i < 10; i++)
    {
        if(!inRow(x, i) && !inCol(y, i) && !inBox(x, y, i) && !solved)
        {
            board[x][y] = i;
            solve(x, y+1);
            board[x][y] = 0;
        }
    }
}

//returns if the value is in the specified row
public static boolean inRow(int x, int val)
{
    for(int i = 0; i < 9; i++)
        if(board[x][i] == val)
            return true;
    return false;
}

//returns whether the value is in the specified column
public static boolean inCol(int y, int val)
{
    for(int i = 0; i < 9; i++)
        if(board[i][y] == val)
            return true;
    return false;
}

//returns whether the value fits based
public static boolean inBox(int x, int y, int val)
{
    int row = (x / 3) * 3;
    int col = (y / 3) * 3;
    for(int r = 0; r < 3; r++)
    for(int c = 0; c < 3; c++)
        if(board[row+r][col+c] == val)
            return true;
    return false;
}

public static void printBoard()
{

    for(int i = 0; i < 9; i++)
    {
        if( i % 3 == 0)
            System.out.println("----------------------");
        for(int j = 0; j < 9; j++)
        {
            if(j % 3 == 0)
                System.out.print("|");
            if(board[i][j] < 10 && board[i][j] > 0)
                System.out.print(board[i][j] + " ");
            else
                System.out.print("- ");
        }
        System.out.println("|");
    }
    System.out.print("----------------------\n");
}

}

編集：最終的に解決策に到達すると、解決されたものがtrueに変更され、値を変更しないことがわかるため、セルをクリアしないでください。スタック オーバーフロー エラーは発生しません。ただ実行し続けます。誤って 1 時間実行させてしまいましたが、まだ実行されていました。ある時点で繰り返し続け、解決済みの状態に到達せず、最初の再帰シーケンスに到達することもありませんでした。

ステップバイステップのデバッグに関しては、あなたはそれを行うことができますか? 私は Eclipse を使用していますが、行ごとに実行できる別の IDE があれば教えていただけますか?

4

1 に答える 1

1

solved上記のコード サンプルは、主にグローバル変数に対する再帰の可能性を十分に活用していません。私はゼロからソリューションを作成したのではなく、違いを確認できるように、提示されたものを修正しようとしました。ご不明な点がございましたらコメントください。デバッグはせずに、少しログを記録し、上記のいくつかの素晴らしいコメントを使用して、次のことを思いつきました。

package sudoku;

public class Solver {
    static int[][] board; //teh board
    static boolean solved; //if the sudoku is solved

    public static void main(String[] args) throws Exception {

        //establish temporary board for now
        final int[][] TUE24JAN =
            {
                {0, 0, 9, 0, 0, 0, 8, 0, 0},
                {0, 1, 0, 0, 2, 0, 0, 3, 0},
                {0, 0, 0, 7, 0, 8, 0, 0, 0},

                {2, 0, 0, 0, 8, 0, 0, 0, 7},
                {0, 3, 0, 1, 0, 2, 0, 4, 0},
                {4, 0, 0, 0, 7, 0, 0, 0, 5},

                {0, 0, 0, 6, 0, 3, 0, 0, 0},
                {0, 8, 0, 0, 9, 0, 0, 7, 0},
                {0, 0, 6, 0, 0, 0, 9, 0, 0},
            };

        final int[][] WED25JAN =
            {
                {2, 5, 0, 0, 0, 0, 4, 0, 0},
                {0, 0, 3, 1, 0, 0, 7, 0, 0},
                {0, 0, 0, 0, 8, 4, 0, 6, 0},
                {4, 0, 0, 0, 0, 0, 0, 8, 0},
                {7, 0, 0, 0, 1, 0, 0, 0, 4},
                {0, 3, 0, 0, 0, 0, 0, 0, 9},
                {0, 9, 0, 6, 5, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 9, 2, 0, 0},
                {0, 0, 2, 0, 0, 0, 0, 4, 3},
            };

        board = TUE24JAN;
        solved = false;
        printBoard();

        solve(0, 0);
        System.out.println("\n");
        printBoard();
    } // end method main

    public static void solve(int x, int y) throws Exception {

        //printBoard();
        System.out.println(x + " : " + y);

        //catches the end of the line
        if (y > 8) {
            y = 0;
            x++;
        }

        //catches the end of the board
        if ((x > 8) || solved) {
            solved = true;
            return;
        }

        //put a number in the cell
        for (int i = 1; i < 10; i++) {

            if ((board[x][y] == 0)) { // cell to be filled

                if (!inRow(x, i) && !inCol(y, i) && !inBox(x, y, i)) { // can use number

                    board[x][y] = i;

                    solve(x, y + 1);

                    if (solved) {
                        return;
                    }

                    board[x][y] = 0;

                }
            }
            else {
                solve(x, y + 1);

                return;

            }
        } // end for
    } // end method solve

    //returns if the value is in the specified row
    public static boolean inRow(int x, int val) {

        for (int i = 0; i < 9; i++) {

            if (board[x][i] == val) {
                return true;
            }
        }

        return false;
    }

    //returns whether the value is in the specified column
    public static boolean inCol(int y, int val) {

        for (int i = 0; i < 9; i++) {

            if (board[i][y] == val) {
                return true;
            }
        }

        return false;
    }

    //returns whether the value fits based
    public static boolean inBox(int x, int y, int val) {
        int row = (x / 3) * 3;
        int col = (y / 3) * 3;

        for (int r = 0; r < 3; r++) {

            for (int c = 0; c < 3; c++) {

                if (board[row + r][col + c] == val) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void printBoard() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 9; i++) {

            if ((i % 3) == 0) {
                sb.append("----------------------\n");
            }

            for (int j = 0; j < 9; j++) {

                if ((j % 3) == 0) {
                    sb.append("|");
                }

                if ((board[i][j] < 10) && (board[i][j] > 0)) {
                    sb.append(board[i][j] + " ");
                }
                else {
                    sb.append("- ");
                }
            }

            sb.append("|\n");
        }

        sb.append("----------------------\n");
        System.out.println(sb.toString());

        /*try {
            Thread.sleep(100);
        }
        catch (InterruptedException e) {

            // TODO Auto-generated catch block
            e.printStackTrace();
        }*/
    } // end method printBoard
} // end class Solver
于 2012-05-30T14:20:55.147 に答える