Java

Question

我有这个使用回溯法完成的数独代码，除了我要求解释的几行代码外，我什么都懂。这是全部代码。

public class Sudoku {


    static int N = 9;


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

    static class Cell {

        int row, col;

        public Cell(int row, int col) {
            super();
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {
            return "Cell [row=" + row + ", col=" + col + "]";
        }
    };



    static boolean isValid(Cell cell, int value) {

        if (grid[cell.row][cell.col] != 0) {
            throw new RuntimeException("Cannot call for cell which already has a value");
        }


        for (int c = 0; c < 9; c++) {
            if (grid[cell.row][c] == value)
                return false;
        }


        for (int r = 0; r < 9; r++) {
            if (grid[r][cell.col] == value)
                return false;
        }


        int x1 = 3 * (cell.row / 3);
        int y1 = 3 * (cell.col / 3);
        int x2 = x1 + 2;
        int y2 = y1 + 2;

        for (int x = x1; x <= x2; x++)
            for (int y = y1; y <= y2; y++)
                if (grid[x][y] == value)
                    return false;

        return true;
    }


    static Cell getNextCell(Cell cur) {

        int row = cur.row;
        int col = cur.col;


        col++;

        if (col > 8) {

            col = 0;
            row++;
        }


        if (row > 8)
            return null; 

        Cell next = new Cell(row, col);
        return next;
    }


    static boolean solve(Cell cur) {


        if (cur == null)
            return true;


        if (grid[cur.row][cur.col] != 0) {

            return solve(getNextCell(cur));
        }


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

            boolean valid = isValid(cur, i);

            if (!valid)
                continue;


            grid[cur.row][cur.col] = i;


            boolean solved = solve(getNextCell(cur));

            if (solved)
                return true;
            else
                grid[cur.row][cur.col] = 0; 

        }

        return false;
    }

    public static void main(String[] args) {
        boolean solved = solve(new Cell(0, 0));
        if (!solved) {
            System.out.println("SUDOKU cannot be solved.");
            return;
        }
        System.out.println("SOLUTION\n");
        printGrid(grid);
    }


    static void printGrid(int grid[][]) {
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++)
                System.out.print(grid[row][col]);
            System.out.println();
        }
    }
}

但是，如果你转到isValid方法，我就无法真正理解这部分。如果有人能详细解释这部分以及它到底做了什么，那就太好了。我在很多代码中看到了这一点，但我仍然无法理解。

        int x1 = 3 * (cell.row / 3);
        int y1 = 3 * (cell.col / 3);
        int x2 = x1 + 2;
        int y2 = y1 + 2;

        for (int x = x1; x <= x2; x++)
            for (int y = y1; y <= y2; y++)
                if (grid[x][y] == value)
                    return false;

        return true;

Answer 1

简单地说，isValid() 检查那些允许将另一个值放入新位置的条件。

例如：它查看了所有行above/below；列 left/right 并检查所提供的值是否已存在。

换句话说：在"adding"一个新号码之前需要满足各种条件，而这个方法只是检查具有该新号码的板是否仍然合法。

Answer 2

        int x1 = 3 * (cell.row / 3);
        int y1 = 3 * (cell.col / 3);
        int x2 = x1 + 2;
        int y2 = y1 + 2;

        for (int x = x1; x <= x2; x++)
            for (int y = y1; y <= y2; y++)
                if (grid[x][y] == value)
                    return false;

        return true;

此代码块定位包含您当前号码的 3x3 框。嵌套循环检查 3x3 框中是否存在给定数字。

如果你想知道为什么公式（除以 3 然后乘以 3）然后加上 2。看看：

如果当前行是0..8:

3 * (0 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)
3 * (1 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)
3 * (2 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)

3 * (3 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)
3 * (4 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)
3 * (5 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)

3 * (6 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)
3 * (7 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)
3 * (8 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)

Answer 3

假设注释对解释代码有用 -

/** your row and column index are based on 0, 
 * and you evaluate the start index or lower bound for the 3x3 grid */
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
/** with the upper bound or the end index for the 3x3 grid 
 * at postion = initial + 2 */
int x2 = x1 + 2;
int y2 = y1 + 2;

/** Iterate through the 3x3 to validate the same element is not present
 * twice in the 3x3 inner grid */
for (int x = x1; x <= x2; x++)
    for (int y = y1; y <= y2; y++)
        if (grid[x][y] == value)
            return false; // false if its already there

return true;

对于下限和上限值，考虑分组索引 0-2、3-5、6-8 在行和列中。

Java - 数独（回溯）“是有效的地方”方法需要解释。

Java - Sudoku (backtracking) ' is place valid' method explanation needed.

sudoku

backtracking