Preface

Topic constraint is the emergence of problems , It's also the key to solving the problem . Make good use of problem conditions and characteristics , Disassemble the problem and optimize the solution .
Solve Sudoku to complete the disassembly and optimization of difficult problems .

One 、 Solving Sudoku

classified ：Pre-hash Array + component-DFS Type questions .

Two 、hash by DFS Empower

1、Pre-hash Array + component-DFS

// Solving Sudoku 
public class SolveSudoku {
    
    /* target: In each case for · Fill in the box with 1-9 The number of , Make it meet the conditions of Sudoku .  Conditions for the establishment of Sudoku ：1- The number of each Jiugong grid is not repeated 1-9;2- Each row 9 The number is not repeated 1-9;3- Each column 9 The number is not repeated 1-9.  Problem analysis ： Then a position can be based on the Jiugong grid of that position 、 Line 、 In the column , Calculate the optional value of this position .  Get the optional value and start DFS,dfs Until the last space is completed, there is no return false, It shows that the scheme is successful . Otherwise, go back and re plan the route . M1： Set up three arrays to record the conditions of each grid hash Array , Then go on line by line DFS. The positions with points are filled with values , After backtracking, it should be assigned as point . */
    public void solveSudoku(char[][] board) {
    
        int[][] row = new int[9][9];
        int[][] col = new int[9][9];
        int[][][] grid = new int[3][3][9];
        // Set up hash The value of the array 
        setHash(board, row, col, grid);
        //DFS To traverse the 
        dfs(board, row, col, grid, 0, 0);
    }

    /** *  Simulate and solve  * * @param board * @param row * @param col * @param grid * @param i * @param j */
    private boolean dfs(char[][] board, int[][] row, int[][] col, int[][][] grid, int i, int j) {
    
        int m = board.length, n = board[0].length;
        // Filling succeeded 
        if (i == m - 1 && j == n) return true;
        // Judge whether the previous line has been traversed 
        if (j == n) {
    
            j = 0;
            i = i + 1;
        }
        // Fill in the value 
        // Non point situation 
        boolean flag = false;
        if (board[i][j] != '.') flag = dfs(board, row, col, grid, i, j + 1);
            // Yes. , The situation that needs to be filled in .
        else {
    
            // use 1-9 To fill in 
            for (int k = 0; k < 9; k++) {
    
                if (row[i][k] == 0 && col[j][k] == 0 && grid[i / 3][j / 3][k] == 0) {
    
                    board[i][j] = (char) (k + 1 + '0');
                    row[i][k] = 1;
                    col[j][k] = 1;
                    grid[i / 3][j / 3][k] = 1;
                    flag = dfs(board, row, col, grid, i, j + 1);
                    if (flag) return true;
                    // Restore 
                    board[i][j] = '.';
                    row[i][k] = 0;
                    col[j][k] = 0;
                    grid[i / 3][j / 3][k] = 0;
                }
            }
        }
        return flag;
    }

    /** *  Set up hash The value of the array  * * @param board * @param row * @param col * @param grid */
    private void setHash(char[][] board, int[][] row, int[][] col, int[][][] grid) {
    
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (board[i][j] != '.') {
    
                    row[i][board[i][j] - '1']++;
                    col[j][board[i][j] - '1']++;
                    grid[i / 3][j / 3][board[i][j] - '1']++;
                }
            }
        }
    }
}

2、1-9 Binary state compression

// use 9 Binary representation of bits 1-9 Have you ever .
class SolveSudoku2 {
    
    /* M2： State compression -- use 9 Binary representation of bits 1-9 Have you ever .  Left shift operation  +  Or operations   Get the binary . Judge by bit operation  +  And operation to determine whether the bit is 1, Indicates that it has appeared . */
    public void solveSudoku(char[][] board) {
    
        int[] row = new int[9];
        int[] col = new int[9];
        int[][] grid = new int[3][3];
        // Set up hash The value of the array 
        setHash(board, row, col, grid);
        //DFS To traverse the 
        dfs(board, row, col, grid, 0, 0);
    }

    /** *  Simulate and solve  * * @param board * @param row * @param col * @param grid * @param i * @param j */
    private boolean dfs(char[][] board, int[] row, int[] col, int[][] grid, int i, int j) {
    
        int m = board.length, n = board[0].length;
        // Filling succeeded 
        if (i == m - 1 && j == n) return true;
        // Judge whether the previous line has been traversed 
        if (j == n) {
    
            j = 0;
            i = i + 1;
        }
        // Fill in the value 
        // Non point situation 
        boolean flag = false;
        if (board[i][j] != '.') flag = dfs(board, row, col, grid, i, j + 1);
            // Yes. , The situation that needs to be filled in .
        else {
    
            // use 1-9 To fill in 
            for (int k = 0; k < 9; k++) {
    
                int val = 1 << k + 1;
                if ((row[i] & val) == 0 && (col[j] & val) == 0 && (grid[i / 3][j / 3] & val) == 0) {
    
                    board[i][j] = (char) (k + 1 + '0');
                    row[i] |= val;
                    col[j] |= val;
                    grid[i / 3][j / 3] |= val;
                    flag = dfs(board, row, col, grid, i, j + 1);
                    if (flag) return true;
                    // Restore 
                    board[i][j] = '.';
                    row[i] -= val;
                    col[j] -= val;
                    grid[i / 3][j / 3] -= val;
                }
            }
        }
        return flag;
    }

    /** *  Set up hash The value of the array  * * @param board * @param row * @param col * @param grid */
    private void setHash(char[][] board, int[] row, int[] col, int[][] grid) {
    
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (board[i][j] != '.') {
    
                    int val = 1 << board[i][j] - '0';
                    row[i] |= val;
                    col[j] |= val;
                    grid[i / 3][j / 3] |= val;
                }
            }
        }
    }
}

summary

1） Use the constraints and objectives of the problem to disassemble the problem .
2） Use the characteristics of the problem to complete the optimization of the problem solution .
3）hash Array 、DFS- Recursive backtracking exercise 、 Binary mode to compress the state （ Novel techniques ）.

reference

[1] LeetCode Solving Sudoku
[2] LeetCode Solving Sudoku – Official explanation – Method 2 – State compression