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，这让它知道不再更改值。我没有收到堆栈溢出错误，它只是继续运行。我不小心让它运行了一个小时，它仍然在运行，它只是在某个点不断重复，从未达到解决状态，也从未达到第一个递归序列。

至于一步一步调试，你能做到吗？我使用 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 回答