tl;dr: Sometimes, the best way to solve a problem is to do exactly what it asks.

Brute Force Sudoku Validation: Simple Yet Smart

Sometimes, the best way to solve a problem is to do exactly what it asks.

Take Sudoku validation: you have a 9x9 grid, and you need to check if it’s valid. But what does “valid” mean?

No row can have duplicate numbers (1-9).
No column can have duplicate numbers.
No 3×3 box (subgrid) can have duplicate numbers.

How do we check that? Well, the most direct way is just to check each condition separately—one by one. This is a classic brute-force approach, but in this case, brute force isn’t dumb—it’s methodical.

🚀 Thought Process: Breaking Down the Problem

Whenever you face a validation problem like this, always break it down into independent parts:

Check rows → Each row should have unique numbers.
Check columns → Each column should have unique numbers.
Check 3×3 boxes → Each 3×3 grid should have unique numbers.

Each of these steps is independent, meaning we can solve them separately and combine the results.

🛠️ Approach 1: Brute Force (Three-Pass Method)

Step 1: Validating Rows

To check rows, we scan each row and use a hash set to track numbers. If a number appears twice, it’s invalid.

fun main() { fun isValidSudoku(board: Array<CharArray>): Boolean { // check rows for (i in 0..8) { val hashSet = HashSet<Char>() for (j in 0..8) { if (board[i][j] != '.' && !hashSet.add(board[i][j])) { return false } } } return true } }

Step 2: Validating Columns

The only change is flipping (i, j) → (j, i) to scan columns instead of rows.

fun main() { fun isValidSudoku(board: Array<CharArray>): Boolean { // check columns for (i in 0..8) { val hashSet = HashSet<Char>() for (j in 0..8) { if (board[j][i] != '.' && !hashSet.add(board[j][i])) { return false } } } return true } }

Step 3: Validating 3×3 Boxes

This is trickier because we’re not iterating row-wise or column-wise, but rather in small 3×3 blocks.

fun main() { fun isValidSudoku(board: Array<CharArray>): Boolean { // check boxes for (i in 0..2) { for (j in 0..2) { val hashSet = HashSet<Char>() for (k in 0..2) { for (l in 0..2) { val num = board[i * 3 + k][j * 3 + l] if (num != '.' && !hashSet.add(num)) { return false } } } } } return true } }

📌 Why i * 3 + k and j * 3 + l? This formula maps each box’s coordinates to the overall grid.

Box (i, j)	Mapped Grid Range
(0,0)	Rows 0-2, Cols 0-2
(0,1)	Rows 0-2, Cols 3-5
(1,0)	Rows 3-5, Cols 0-2
(2,2)	Rows 6-8, Cols 6-8

💡 So far, we have looped over the grid 3 times. Can we do better?

⚡ Optimized Approach: One-Pass Validation

Instead of looping three times, what if we check all three conditions simultaneously in a single pass?

We use three sets of hash sets:

rowSets[i] → For the i-th row
colSets[j] → For the j-th column
boxSets[boxIndex] → For the k-th 3×3 box

fun main() { fun isValidSudoku(board: Array<CharArray>): Boolean { val rowSets = Array(9) { HashSet<Char>() } val colSets = Array(9) { HashSet<Char>() } val boxSets = Array(9) { HashSet<Char>() } for (i in 0..8) { for (j in 0..8) { val num = board[i][j] if (num == '.') continue val boxIndex = (i / 3) * 3 + (j / 3) if (num in rowSets[i] || num in colSets[j] || num in boxSets[boxIndex]) { return false } rowSets[i].add(num) colSets[j].add(num) boxSets[boxIndex].add(num) } } return true } }

🚀 Why is this faster?
✅ Only one pass over the grid.
✅ No redundant iterations.
✅ Each lookup is O(1) in a set.

⏳ Time Complexity: O(1) (since it’s a fixed 9×9 grid).
📌 Space Complexity: O(1) (three sets of size 9 is negligible).

🚀 Ultimate Optimization: Boolean Arrays

Since Sudoku numbers are 1-9, we don’t need hash sets. A boolean array is faster!

fun main() { fun isValidSudoku(board: Array<CharArray>): Boolean { val rows = Array(9) { BooleanArray(9) } val cols = Array(9) { BooleanArray(9) } val boxes = Array(9) { BooleanArray(9) } for (i in 0..8) { for (j in 0..8) { val num = board[i][j] if (num != '.') { val index = num - '1' val boxIndex = (i / 3) * 3 + j / 3 if (rows[i][index] || cols[j][index] || boxes[boxIndex][index]) { return false } rows[i][index] = true cols[j][index] = true boxes[boxIndex][index] = true } } } return true } }

🚀 Boolean arrays are 2x faster than sets because:
✔ O(1) direct index access (vs. O(1) hash lookup with extra memory overhead).
✔ No hashing required (direct memory access).

📌 Final Thoughts: When to Use Each Approach?

Approach	Pros	Cons
Brute Force (3 loops)	Easy to understand, straightforward	Loops over the board 3 times
One-Pass HashSets	More efficient, single loop	Uses extra space for 3 sets
Boolean Arrays	Fastest, minimal memory	Slightly harder to read

💡 What’s Next?
📌 Can you modify this to solve the Sudoku instead of just validating it? Try it out! 🚀