37. Sudoku Solver

leetcode-cn Daily Challenge on September 15th, 2020.

Difficulty : Hard

Related Topics : HashTable、Backtracking

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character '.'.

You may assume that the given Sudoku puzzle will have a single unique solution.

The given board size is always 9x9.

Solution

mine

Java

HashTable & Backtracking Runtime: 22 ms, faster than 26.73%, Memory Usage: 39.2 MB, less than 20.80% of Java online submissions

boolean finish = false;
public void solveSudoku(char[][] board) {
    List<Set<Integer>> r = new ArrayList<>();
    List<Set<Integer>> c = new ArrayList<>();
    List<Set<Integer>> nine = new ArrayList<>();
    List<List<Integer>> missing = new ArrayList<>(9);
    for (int i = 0; i < 9; i++) {
        r.add(new HashSet<>());
        c.add(new HashSet<>());
        nine.add(new HashSet<>());
        missing.add(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)));
    }
    List<int[]> empty = new ArrayList<>();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                empty.add(new int[]{i, j});
                continue;
            }
            int t = board[i][j] - '0';
            missing.get(i / 3 * 3 + j / 3).remove((Object) t);
            nine.get(i / 3 * 3 + j / 3).add(t);
            r.get(i).add(t);
            c.get(j).add(t);
        }
    }

    dfs(r, c, nine, missing, empty, 0, board);
}

void dfs(List<Set<Integer>> r, List<Set<Integer>> c, List<Set<Integer>> nine, List<List<Integer>> missing,
         List<int[]> empty, int index, char[][] board) {
    if (index == empty.size()) {
        finish = true;
        return;
    }
    int[] pos = empty.get(index);
    int ii = pos[0] / 3 * 3 + pos[1] / 3;
    List<Integer> options = missing.get(ii);
    for (int i = 0; i < options.size(); i++) {
        if (finish) return;
        int v = options.get(i);
        if (r.get(pos[0]).contains(v) || c.get(pos[1]).contains(v) || nine.get(ii).contains(v))
            continue;

        r.get(pos[0]).add(v);
        c.get(pos[1]).add(v);
        nine.get(ii).add(v);
        board[pos[0]][pos[1]] = (char) ('0' + v);
        dfs(r, c, nine, missing, empty, index + 1, board);

        r.get(pos[0]).remove(v);
        c.get(pos[1]).remove(v);
        nine.get(ii).remove(v);

    }
}

Bit Manipulation Optimize Runtime: 5 ms, faster than 89.24%, Memory Usage: 39.1 MB, less than 25.69% of Java online submissions

boolean finish = false;
public void solveSudoku(char[][] board) {
    int[] r = new int[10], c = new int[10], nine = new int[10];
    List<int[]> empty = new ArrayList<>();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                empty.add(new int[]{i, j});
                continue;
            }
            int t = board[i][j] - '0';
            int ii = i / 3 * 3 + j / 3;
            nine[ii] += 1 << t;
            r[i] += 1 << t;
            c[j] += 1 << t;
        }
    }
    dfs(r, c, nine, empty, 0, board);
}

void dfs(int[] r, int[] c, int[] nine, List<int[]> empty, int index, char[][] board) {
    if (index == empty.size()) {
        finish = true;
        return;
    }
    int[] pos = empty.get(index);
    int ii = pos[0] / 3 * 3 + pos[1] / 3;
    for (int i = 1; i < 10; i++) {
        if (finish) return;
        int v = 1 << i;
        if ((r[pos[0]] & v) != 0 || (c[pos[1]] & v) != 0 || (nine[ii] & v) != 0)
            continue;

        r[pos[0]] += v;
        c[pos[1]] += v;
        nine[ii] += v;
        board[pos[0]][pos[1]] = (char) ('0' + i);
        dfs(r, c, nine, empty, index + 1, board);

        r[pos[0]] -= v;
        c[pos[1]] -= v;
        nine[ii] -= v;
    }
}

the most votes

Runtime: 17 ms, faster than 43.85%, Memory Usage: 36.9 MB, less than 74.75% of Java online submissions

public void solveSudoku(char[][] board) {
    if(board == null || board.length == 0)
        return;
    solve(board);
}

public boolean solve(char[][] board){
    for(int i = 0; i < board.length; i++){
        for(int j = 0; j < board[0].length; j++){
            if(board[i][j] == '.'){
                for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
                    if(isValid(board, i, j, c)){
                        board[i][j] = c; //Put c for this cell

                        if(solve(board))
                            return true; //If it's the solution return true
                        else
                            board[i][j] = '.'; //Otherwise go back
                    }
                }

                return false;
            }
        }
    }
    return true;
}

private boolean isValid(char[][] board, int row, int col, char c){
    for(int i = 0; i < 9; i++) {
        if(board[i][col] != '.' && board[i][col] == c) return false; //check row
        if(board[row][i] != '.' && board[row][i] == c) return false; //check column
        if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
           board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
    }
    return true;
}

leetcode Solution

Runtime: 1 ms, faster than 99.92%, Memory Usage: 37.1 MB, less than 55.40% of Java online submissions

private int[] line = new int[9];
private int[] column = new int[9];
private int[][] block = new int[3][3];
private boolean valid = false;
private List<int[]> spaces = new ArrayList<int[]>();

public void solveSudoku(char[][] board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                int digit = board[i][j] - '0' - 1;
                flip(i, j, digit);
            }
        }
    }

    while (true) {
        boolean modified = false;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                    if ((mask & (mask - 1)) == 0) {
                        int digit = Integer.bitCount(mask - 1);
                        flip(i, j, digit);
                        board[i][j] = (char) (digit + '0' + 1);
                        modified = true;
                    }
                }
            }
        }
        if (!modified) {
            break;
        }
    }

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                spaces.add(new int[]{i, j});
            }
        }
    }

    dfs(board, 0);
}

public void dfs(char[][] board, int pos) {
    if (pos == spaces.size()) {
        valid = true;
        return;
    }

    int[] space = spaces.get(pos);
    int i = space[0], j = space[1];
    int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
    for (; mask != 0 && !valid; mask &= (mask - 1)) {
        int digitMask = mask & (-mask);
        int digit = Integer.bitCount(digitMask - 1);
        flip(i, j, digit);
        board[i][j] = (char) (digit + '0' + 1);
        dfs(board, pos + 1);
        flip(i, j, digit);
    }
}

public void flip(int i, int j, int digit) {
    line[i] ^= (1 << digit);
    column[j] ^= (1 << digit);
    block[i / 3][j / 3] ^= (1 << digit);
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

37. Sudoku Solver.md

37. Sudoku Solver.md

37. Sudoku Solver

Note:

Solution

Files

37. Sudoku Solver.md

Latest commit

History

37. Sudoku Solver.md

File metadata and controls

37. Sudoku Solver

Note:

Solution