Valid Sudoku

Medium

The problem

You get a 9×9 Sudoku board (a [][]byte). Each cell holds a digit '1' to '9' or '.' for an empty cell. Return true if the digits already on the board follow the Sudoku rules: no digit repeats in any row, in any column, or in any of the nine 3×3 boxes. The board does not have to be solvable, and only the filled cells are checked.

Example 1
Input: board = ["53..7....", "6........", ".98......", ".........", ".........", ".........", ".........", ".........", "........."]
Output: true
No digit repeats in any row, column or 3×3 box. Each row is written as a string of 9 characters.
Example 2
Input: board = ["53.......", "6........", ".........", ".........", ".........", "5........", ".........", ".........", "........."]
Output: false
The digit 5 appears twice in column 0 (in row 0 and in row 5).
Example 3
Input: board = ["53.......", "..5......", ".........", ".........", ".........", ".........", ".........", ".........", "........."]
Output: false
The two 5's are in different rows and different columns, but both sit in the top-left 3×3 box.

Limits

board is 9 rows of 9 cells
Each cell is '1' to '9' or '.'

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Which three "places" must each digit be unique in? How do you name the 3×3 box a cell belongs to?

The idea

Keep sets for every row, column and box. The box id of (r,c) is (r/3, c/3). If a digit is already in any of its three sets, the board is invalid.

Target: O(81) = O(1) time

Go function shape

func isValidSudoku(board [][]byte) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// IsValidSudoku: a digit may appear once per row, once per column and once per 3x3 box.
func IsValidSudoku(board [][]byte) bool {
	var rows, cols, boxes [9][9]bool
	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if board[r][c] == '.' {
				continue
			}
			d := board[r][c] - '1'
			b := (r/3)*3 + c/3 // box number 0..8
			if rows[r][d] || cols[c][d] || boxes[b][d] {
				return false
			}
			rows[r][d], cols[c][d], boxes[b][d] = true, true, true
		}
	}
	return true
}

Read the lesson: Arrays & Hash Map