Go Problem Solving Log: Valid Sudoku – The Key Is Index Mapping

Today I tackled the "Valid Sudoku" algorithm problem in Go. The problem itself is straightforward; the focus is on choosing the right data structure and understanding index mapping.

func isValidSudoku(board [][]byte) bool {
    var rowMap, colMap, cellMap [9][9]bool
    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            val := board[r][c]
            if val == '.' {
                continue
            }
            idx := val - '1'
            cellLocation := r/3*3 + c/3
            if rowMap[r][idx] || colMap[c][idx] || cellMap[cellLocation][idx] {
                return false
            }
            rowMap[r][idx] = true
            colMap[c][idx] = true
            cellMap[cellLocation][idx] = true
        }
    }
    return true
}

Key Points of the Problem

1. Data‑Structure Choice: Array Beats Generic Map

Although I initially reached for a map, the Sudoku board has a fixed size (9 × 9) and only digits 1‑9 appear. With such a clear range, three 9 × 9 boolean arrays— rowMap, colMap, and cellMap —are sufficient to record whether a digit has already appeared in a row, column, or 3 × 3 sub‑grid.

This approach offers two advantages:

Direct access makes the algorithm faster.

It uses less memory because no hash‑table overhead is needed.

For algorithm problems, whenever an array can represent the state, prefer it over a map.

2. Character‑to‑Index Mapping

The board stores characters, not integers, so we need a simple conversion:

'1' → 0

'2' → 1

…

'9' → 8

idx := val - '1'

This idiom turns a character into a zero‑based array index and is useful in many counting‑or‑frequency problems.

3. Computing 3 × 3 Sub‑Grid Position

Mapping a cell to its sub‑grid (0‑8) is done with:

cellLocation := r/3*3 + c/3

Explanation: r/3 selects the sub‑grid row (0‑2). c/3 selects the sub‑grid column (0‑2).

Combining them as r/3*3 + c/3 yields the final sub‑grid index.

Examples: top‑left sub‑grid → 0, top‑middle → 1, top‑right → 2, middle‑left → 3, …, bottom‑right → 8.

4. Core Logic Is Simple

After the data structures and index mapping are set, the algorithm iterates the entire 9 × 9 board:

If the current cell is '.', skip it.

If it contains a digit, check whether that digit already appears in the corresponding row, column, or sub‑grid using the three boolean arrays.

If any conflict is found, return false immediately.

If the whole board is traversed without conflict, return true.

This is a classic "traverse‑and‑maintain‑state" pattern; the difficulty lies in correctly handling the three dimensions simultaneously.

Takeaways

1. Don’t default to a map. For problems with a small, fixed range, arrays provide more direct and efficient access.

2. Index mapping matters. Converting characters to array indices is a common technique that simplifies many logical problems.

3. Practice is more than just getting AC. Solving the problem revealed gaps in my handling of data‑structure selection and sub‑grid indexing, which I can now address in future challenges.

Conclusion

This post records a brief recap of solving the Valid Sudoku problem, reinforces my thinking process, and helps me become more comfortable with Go syntax and idioms. Feedback and alternative solutions are welcome.