Yet another Java recursive solution, using bit operations (Beats 99%)


  • 1
    J

    The idea is to use bit sets to store used digits on rows, columns, and blocks.

    public class Solution {
        private boolean solver(int idx, char[][] board, ArrayList<Integer> list, int[] state) {
            if (idx == list.size()) return true;
            int n = list.get(idx);
            int y = n / 9;
            int x = n - y * 9;
            int v = 9 + x;
            int b = 18 + (y / 3 * 3 + x / 3);
            int available = ~state[y] & ~state[v] & ~state[b] & 0b111111111;
            while (available > 0) {
                int bit = available & -available;
                state[y] ^= bit;
                state[v] ^= bit;
                state[b] ^= bit;
                board[y][x] = (char)(Integer.numberOfTrailingZeros(bit) + '1');
                if (solver(idx + 1, board, list, state)) return true;
                state[y] ^= bit;
                state[v] ^= bit;
                state[b] ^= bit;
                // board[y][x] = '.';
                available &= available - 1;
            }
            return false;
        }
        public void solveSudoku(char[][] board) {
            ArrayList<Integer> list =  new ArrayList<>();
            int len = 0;
            int[] state = new int[27]; // 0 - 8 horizontal, 9 - 17 vertical, 18 - 26 block
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') list.add(i * 9 + j);
                    else {
                        state[i] ^= 1 << board[i][j] - '1';
                        state[9 + j] ^= 1 << board[i][j] - '1';
                        state[18 + (i / 3 * 3 + j / 3)] ^= 1 << board[i][j] - '1';
                    }
                }
            }
            solver(0, board, list, state);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.