Valid Sudoku

Q: What is the time complexity of Valid Sudoku?

The board always has 81 cells, so both approaches run in O(1) time and use O(1) memory. For a general n × n Sudoku the one-pass check reads each of the n² cells once and keeps 3n² flags: O(n²) time and memory.

Q: Can Valid Sudoku be solved with bit masks?

Yes. Give each row, column and box one integer, where bit d means digit d+1 has been seen. For a filled cell, if 1 << d ANDs to nonzero with any of its three masks, the digit repeats; otherwise OR it into all three. That is 27 integers instead of 243 flags.

MediumHashing

+10

You get a 9 × 9 Sudoku board as board, a list of 9 strings with 9 characters each, one string per row. Each character is a digit from 1 to 9 or . for an empty cell. Return true if no digit appears twice in a row, a column or a 3 × 3 box, and false otherwise. Only the filled cells are checked: the board does not have to be solvable.

Function

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 strings of 9 characters, one per row, digits 1 to 9 and . for an empty cell
Returnsboolean: true if no row, column or 3 × 3 box repeats a digit, false otherwise

Constraints

board.length == 9 and board[i].length == 9
board[i][j] is a digit from 1 to 9 or .
The board may be impossible to complete; only repeats among the filled cells matter.

Examples

Input: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Output: true
Explanation: Row 4, counting from 0, .74..89.3, has 7, 4, 8, 9 and 3 once each, and none of the other 26 groups repeats a digit either.

Input: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Output: false
Explanation: Row 0 and row 7 both start with a 3, so column 0 holds two 3s. They share no row or box, so only the column check catches it.

Input: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Output: false
Explanation: The 5 at row 0, column 8 and the 5 at row 2, column 7 share no row or column, but both sit in the top-right box, so the answer is false.

Follow-up

How would you check a 16 × 16 board with 4 × 4 boxes and the symbols 1 to 9 and A to G? What does the box formula become?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every digit belongs to three groups: its row, its column and its 3 × 3 box. Rows and columns are direct to index; the box is where the bugs live. Number the boxes 0 to 8 with (r / 3) * 3 + c / 3, and one pass over the 81 cells checks all 27 groups.

Check each row, column and box on its own

Intuition

The rule names 27 groups: 9 rows, 9 columns and 9 boxes. Gather the nine cells of each and look for a repeated digit, ignoring dots. The board is valid exactly when no group has one.

A seen flag per digit finds a repeat among nine cells. Each of the 81 cells is read once for each of its three groups: 243 reads, a fixed amount of work. On an n × n board the same method costs O(n²).

Algorithm

For i from 0 to 8, collect row i, column i and box i.
Box i has its corner at row 3 * (i / 3), column 3 * (i % 3); its cell k is k / 3 rows down and k % 3 columns right of it.
Walk each group with fresh seen flags, skipping dots. If a digit is already flagged, return false.
After all 27 groups, return true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

One pass with a seen table per row, column and box

Intuition

Visit each cell once and ask all three questions together. Keep three 9 × 9 tables of flags: seenRow[r][d] says digit d+1 is already in row r, and seenCol and seenBox work the same way.

Cell (r, c) belongs to box (r / 3) * 3 + c / 3. The first part picks the band of three boxes, and c / 3 picks the box inside the band. Cell (4, 7) lands in box 1 * 3 + 2 = 5, the middle-right box.

A flag that is already set means the digit repeats in that group. Each cell is read once and the tables hold 243 flags: fixed time and memory here, O(n²) on an n × n board.

Algorithm

Create seenRow, seenCol and seenBox, each 9 × 9 and all false.
For every filled cell (r, c), let d be its digit minus 1 and b = (r / 3) * 3 + c / 3.
If seenRow[r][d], seenCol[c][d] or seenBox[b][d] is set, return false; otherwise set all three.
After the last cell, return true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Pitfalls and edge cases

Computing the box as r / 3 + c / 3. It gives 0 to 4 only, so (0, 3) and (3, 0) share a number though their boxes differ, and two 7s there are reported as a repeat.
Dividing with / in JavaScript, Python 3 or Lua, where 4 / 3 is 1.33. Round down.
Treating . as a value. An empty board, nine dots to a row, is valid.
Trying to solve the puzzle. A row 0 of 12345678. with a 9 lower in column 8 can never be finished, yet nothing repeats: true.
Skipping the boxes. A full grid where each row is the one above shifted left by one place repeats nothing in a row or column, while every box holds repeats.

Frequently asked questions3

What is the time complexity of Valid Sudoku?

The board always has 81 cells, so both approaches run in O(1) time and use O(1) memory. For a general n × n Sudoku the one-pass check reads each of the n² cells once and keeps 3n² flags: O(n²) time and memory.

Does a valid Sudoku board have to be solvable?

No. Valid here means only that no digit repeats in a row, a column or a 3 × 3 box among the filled cells. A board can pass that check and still have no solution. Deciding solvability needs a search such as backtracking, which is a different problem.

Can Valid Sudoku be solved with bit masks?

Yes. Give each row, column and box one integer, where bit d means digit d+1 has been seen. For a filled cell, if 1 << d ANDs to nonzero with any of its three masks, the digit repeats; otherwise OR it into all three. That is 27 integers instead of 243 flags.

def isValidSudoku(board):
    # Write code here

Test #1

Test #2

Test #3

Argument

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Expected Output

true