图-搜索-DFS-37. 解数独

2020-03-24 22:23:32

问题描述：

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

一个数独。

答案被标成红色。

提示:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

问题求解：

经典的DFS问题，可以使用回溯法解决。

    int[][] rows = new int[9][9];

    int[][] cols = new int[9][9];

    int[][] boxes = new int[9][9];

    public void solveSudoku(char[][] board) {

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

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

                char c = board[i][j];

                if (c == '.') continue;

                int k = c - '0';

                rows[i][k - 1] = 1;

                cols[j][k - 1] = 1;

                boxes[i / 3 * 3 + j / 3][k - 1] = 1;

            }

        }

        helper(board, 0, 0);

    }

    private boolean helper(char[][] board, int row, int col) {

        if (row >= 9) return true;

        int nr = row;

        int nc = col + 1;

        if (col == 8) {

            nr = nr + 1;

            nc = 0;

        }

        if (board[row][col] != '.') return helper(board, nr, nc);

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

            if (rows[row][i - 1] == 1 || cols[col][i - 1] == 1 || boxes[row / 3 * 3 + col / 3][i - 1] == 1) continue;

            rows[row][i - 1] = 1;

            cols[col][i - 1] = 1;

            boxes[row / 3 * 3 + col / 3][i - 1] = 1;

            board[row][col] = (char)(i + '0');

            if (helper(board, nr, nc)) return true;

            board[row][col] = '.';

            rows[row][i - 1] = 0;

            cols[col][i - 1] = 0;

            boxes[row / 3 * 3 + col / 3][i - 1] = 0;

        }

        return false;

    }

巴特西

图-搜索-DFS-37. 解数独

最新文章

热门文章