LeetCode Entry

37. Sudoku Solver

31.08.2025 hard 2025 kotlin

Solve sudoku

37. Sudoku Solver hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1098

Problem TLDR

Solve sudoku #hard #backtrack

Intuition

Brute-force DFS with pruning

Approach

• we don’t have to validate in the end; choose only available numbers
• there is a bitmask optimization
• we can prioritize rows, cols or subs with more numbers filled

Complexity

• Time complexity: \(O(9^81)\), however, 9 is smaller with pruning

• Space complexity: \(O(1)\)

Code

// 233ms
    fun solveSudoku(b: Array<CharArray>): Unit {
        val rows = Array(9) { b[it].toHashSet() }
        val cols = Array(9) { x -> (0..8).map { b[it][x] }.toHashSet() }
        val subs = Array(9) { i -> (0..8).map { j ->  b[i/3*3 + j/3][i%3*3 + j%3] }.toHashSet() }
        fun dfs(i: Int): Boolean {
            if (i == 81) return true
            val y = i / 9; val x = i % 9
            if (b[y][x] != '.') return dfs(i + 1)
            for (c in '1'..'9') if (c !in rows[y] && c !in cols[x] && c !in subs[y/3*3+x/3]) {
                b[y][x] = c; rows[y] += c; cols[x] += c; subs[y/3*3+x/3] +=c
                if (dfs(i + 1)) return true
                rows[y] -= c; cols[x] -= c; subs[y/3*3+x/3] -=c
            }
            b[y][x] = '.'; return false
        }
        dfs(0)
    }

// 79ms
    fun solveSudoku(b: Array<CharArray>): Unit {
        val s = Array(3) { IntArray(9) }
        for (y in 0..8) for (x in 0..8) if (b[y][x] != '.') {
            val c = 1 shl (b[y][x] - '0')
            s[0][y] = s[0][y] or c; s[1][x] = s[1][x] or c; s[2][y/3*3+x/3] = s[2][y/3*3+x/3] or c}
        fun dfs(i: Int): Boolean {
            if (i == 81) return true
            val y = i / 9; val x = i % 9
            if (b[y][x] != '.') return dfs(i + 1)
            for (n in 1..9) {
                val c = 1 shl n
                if ((c and s[0][y]) + (c and s[1][x]) + (c and s[2][y/3*3+x/3]) == 0) {
                s[0][y] = s[0][y] xor c; s[1][x] = s[1][x] xor c; s[2][y/3*3+x/3] = s[2][y/3*3+x/3] xor c
                b[y][x] = '0' + n; if (dfs(i + 1)) return true
                s[0][y] = s[0][y] xor c; s[1][x] = s[1][x] xor c; s[2][y/3*3+x/3] = s[2][y/3*3+x/3] xor c
            }}
            b[y][x] = '.'; return false
        }
        dfs(0)
    }