37. Sudoku Solver


Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

Example

Translation

编写一个程序,通过填充空单元格来解决数独谜题。 空单元格由字符’。’表示。

数独只有一个解

Ideas

使用3个二维数组,分别记录 每一行、每一列、每个小九宫格里已经出现的数字。下标代表数字,值代表是否出现过

然后使用 DSF。对每个需要填充的单元格进行递归。递归时根据之前统计的3个二维数组来判断应该填哪个数字

Accept Code


    public static boolean filling(char[][] board, int[][] row, int[][] col, int[][] square) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; k++) {
                        int sIndex = i / 3 * 3 + j / 3;
                        if (row[i][k] == 0 && col[j][k] == 0 && square[sIndex][k] == 0) {
                            board[i][j] = ((k + 1) + "").charAt(0);
                            row[i][k] = col[j][k] = square[sIndex][k] = 1;
                            if (filling(board, row, col, square)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                                row[i][k] = col[j][k] = square[sIndex][k] = 0;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public static void solveSudoku(char[][] board) {
        int[][] row = new int[9][9];
        int[][] col = new int[9][9];
        int[][] square = new int[9][9];
        //init array
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0' - 1;
                    //根据 i、j 计算属于第几个九宫格
                    int sIndex = i / 3 * 3 + j / 3;
                    row[i][num] = col[j][num] = square[sIndex][num] = 1;
                }
            }
        }
        filling(board, row, col, square);
    }

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
本文链接:https://zdran.com/20190321.html