Start learning free

LESSON 322 OF 573 · HASH TABLE

Valid Sudoku in Go: Hash Sets for Rows, Columns and Boxes

Practice O(81) Read the full explanation

A Sudoku board is a 9 x 9 grid of cells. Each cell holds a digit from '1' to '9', or '.' while it is empty. Rows 0-2, 3-5 and 6-8 and columns 0-2, 3-5 and 6-8 split the board into nine 3 x 3 boxes.

Given a partly filled board, return true if it is valid so far, and false otherwise. The board is valid when no digit appears twice:

  1. in the same row,
  2. in the same column,
  3. in the same 3 x 3 box.

Only the filled cells are checked; empty cells don't count. A valid board doesn't have to be solvable: you check the digits already on it, you don't solve the puzzle.

Rows are numbered from 0 at the top and columns from 0 at the left. In the examples, each line is one row of the board.

 

Example 1:



Input: board =
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: true
Explanation: No row, column or box holds the same digit twice.

Example 2:

Input: board =
83..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: false
Explanation: The board of Example 1 with an 8 instead of the 5 in the top left corner.
Column 0 now holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2.

Example 3:

Input: board =
12345678.
.........
.........
.........
........9
.........
.........
.........
.........
Output: true
Explanation: No digit repeats, so the board is valid, although it has no solution:
the last cell of row 0 can only be a 9, and column 8 already has a 9 in row 4.

 

Constraints:

  • The board has 9 rows, and each row has 9 cells.
  • Each cell holds a digit from '1' to '9' or '.'.

Note:

Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.

STEP 1 OF 14
    Ctrl + Enter to check

    GO · HASH TABLE

    Valid Sudoku in Go, explained

    Problem overview

    The function isValidSudoku receives board, a 9 x 9 grid stored as [][]byte. Each cell holds a digit character from '1' to '9', or '.' when it is empty. It returns true when no digit appears twice in the same row, the same column or the same 3 x 3 box, and false otherwise.

    Only the filled cells are checked. A board can be valid and still impossible to finish: the third example of the lesson has 1 to 8 in row 0 and a 9 at the end of row 4. The last cell of row 0 could only be a 9, but column 8 already has one. No digit repeats, so the function returns true. The function checks the digits that are on the board; it doesn't solve the puzzle.

    In the first example, no row, column or box repeats a digit, so the answer is true. In the second, the 5 in the top left corner is replaced by an 8. Column 0 then holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2, so the answer is false.

    Approach: remember what each row, column and box has seen

    A direct way is to scan the row, the column and the box of every filled cell again. On a 9 x 9 board that is fast enough, but it looks at each cell many times. A better way is to visit each cell once, and to keep a set of the digits seen so far for every row, every column and every box. When a digit is already in one of the three sets that its cell belongs to, the board is invalid. Otherwise, the digit goes into all three sets.

    That is 27 sets in all: 9 for rows, 9 for columns, 9 for boxes. Every cell belongs to exactly one row, one column and one box, so each cell is checked in constant time. The total work is proportional to the 81 cells, and the sets hold at most 81 digits per kind, which is O(81) time and space. Since the board size is fixed, this is the same as O(1), but the O(81) figure shows where the work goes.

    Numbering the boxes

    Rows and columns have natural numbers, and boxes need one too. The box that holds cell (r, c) is in box row r / 3 and box column c / 3, both 0, 1 or 2, because integer division drops the remainder. Numbering the boxes left to right, then top to bottom gives (r/3)*3 + c/3. For example:

    [0 0] 0
[4 7] 5
[8 8] 8
[2 3] 1
[3 2] 3

    Each line shows a cell and its box number. The cell in row 4, column 7 is in box 5, the right box of the middle band.

    Step by step

    1. Create the three slices of sets. Go has no set type, so a map[byte]bool is the usual stand-in. rows, cols and boxes are each made with make as a slice of 9 such maps.
    2. Fill every slot with an empty map. A new slice of maps holds nine nil maps, and writing to a nil map crashes the program with a panic. A loop sets rows[i], cols[i] and boxes[i] to map[byte]bool{}. Each row, column and box needs a map of its own.
    3. Visit every cell, row by row. Two nested for loops, with r and c from 0 to 8.
    4. Read the cell into digit. It is a byte, because the board is a slice of byte slices.
    5. Skip empty cells. If digit is '.', continue goes straight to the next cell. Empty cells never break a rule.
    6. Compute the box number with the formula above and store it in box.
    7. Look for a repeat. If rows[r][digit], cols[c][digit] or boxes[box][digit] is already true, return false. Each map holds the digits of the cells visited earlier in that row, column or box.
    8. Record the digit by setting all three entries to true, so later cells find it.
    9. Return true after both loops: every filled cell was checked against the earlier ones and nothing repeated.

    The solution in Go

    func isValidSudoku(board [][]byte) bool {
    rows := make([]map[byte]bool, 9)
    cols := make([]map[byte]bool, 9)
    boxes := make([]map[byte]bool, 9)
    for i := 0; i < 9; i++ {
        rows[i] = map[byte]bool{}
        cols[i] = map[byte]bool{}
        boxes[i] = map[byte]bool{}
    }
    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            digit := board[r][c]
            if digit == '.' {
                continue
            }
            box := (r/3)*3 + c/3
            if rows[r][digit] || cols[c][digit] || boxes[box][digit] {
                return false
            }
            rows[r][digit] = true
            cols[c][digit] = true
            boxes[box][digit] = true
        }
    }
    return true
}

    Go details worth knowing

    • Reading a missing key is safe. A map returns the zero value for a key it doesn't have, and the zero value of bool is false. So rows[r][digit] is false for a digit not seen yet, with no need for the two-value form v, ok := m[k]. Writing is different: a nil map panics with "assignment to entry in nil map", which is why the first loop creates every map. Reading from a nil map is fine, too.
    • The cell is a byte, not a string. board[r][c] is a byte holding the character's code. Comparing it with '.' works because a rune literal such as '.' is an untyped constant that converts to byte. For the digit '5' the byte value is 53, not 5. Nothing needs the digit's numeric value here, since the byte is only a key in the map.
    • Integer division truncates. r/3 and c/3 drop the remainder, so rows 0 to 2 all give 0, rows 3 to 5 give 1, and rows 6 to 8 give 2. The parentheses in (r/3)*3 are clearer than they are required.
    • Short-circuit ||. The three lookups run left to right and stop at the first true.
    • Maps in a slice. A []map[byte]bool stores references to maps, so rows[r][digit] = true changes the map inside the slice. No copy is made.

    Complexity

    Time: O(81). The loops visit each of the 81 cells once, and every lookup or insertion into a map takes constant time on average.

    Space: O(81). The 27 maps together hold at most three entries per filled cell, so at most 243 entries. They are small, and the board size doesn't change.

    Edge cases and common mistakes

    • Sharing one map. If all rows used the same map, a 5 in row 0 would make a 5 in row 7 look like a repeat. That is why each row, column and box gets its own.
    • Forgetting to skip '.'. Two empty cells in a row would look like a repeated digit. Without continue, the empty board would be reported as invalid.
    • Checking only rows and columns. A board with a 5 at (0, 0) and another at (1, 1) has no repeat in any row or column, but both are in box 0. It returns false only because of the box check.
    • A wrong box formula. r/3 + c/3 gives the same number to different boxes: boxes 1 and 3 would both be 1. The multiplication by 3 is what makes the numbers unique.
    • Trying to solve the puzzle. Valid doesn't mean solvable. The function must accept a board that has no solution, as long as nothing repeats.

    Testing

    • The first example of the lesson gives true.
    • The same board with an 8 in the top left corner gives false.
    • The unsolvable third example gives true.
    • An empty board (81 dots) gives true.
    • A board with a 5 in row 0, column 0 and another 5 in row 1, column 1 gives false: same box.
    • A board with a 5 in row 0, column 0 and another in row 3, column 0 gives false: same column.
    • A board with a 5 in row 0, column 0 and another in row 0, column 8 gives false: same row.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free