CF 102697040 - Valid Sudoku

We are given a complete 9 by 9 Sudoku grid. Every cell contains an integer, and the task is to decide whether the grid obeys the three Sudoku uniqueness rules: a digit cannot appear twice in one row, twice in one column, or twice inside the same 3 by 3 box.

codeforcescompetitive-programming

CF 102697040 - Valid Sudoku

Rating: -
Tags: -
Solve time: 57s
Verified: yes

Solution

Problem Understanding

We are given a complete 9 by 9 Sudoku grid. Every cell contains an integer, and the task is to decide whether the grid obeys the three Sudoku uniqueness rules: a digit cannot appear twice in one row, twice in one column, or twice inside the same 3 by 3 box. The required output is VALID when all three conditions hold and INVALID otherwise. The original problem fixes the board size at exactly 9 by 9 and guarantees that the input values are integers from 1 through 9.

Because the board size never grows, the entire input contains only 81 cells. That changes how we should think about complexity. Even a solution that performs several comparisons for every pair of cells is tiny in absolute terms. A clean linear scan is still preferable because it directly represents the Sudoku rules and has less opportunity for indexing mistakes, but there is no large hidden constraint that requires an advanced data structure. The one-second limit is easily satisfied by either approach.

There are three common correctness traps. First, checking only rows is insufficient. For example,

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

has the correct output INVALID. A careless implementation that only verifies the contents of each row would accept it, even though the first column contains two 1s.

Second, checking rows and columns still misses the 3 by 3 boxes. Consider a grid where two equal values occupy different rows and different columns but share a box. For example, the top-left box could begin as

1 2 3
4 1 6
7 8 9

The two 1s are not in the same row or column, but they violate the box rule, so the complete board must be reported as INVALID. An implementation that checks only rows and columns silently accepts this configuration.

Third, the box index must use both the row and column groups. For a cell (r, c), the correct box is determined by r // 3 and c // 3. Using only r // 3, for example, merges the three boxes in the same horizontal band and can reject a valid board or fail to detect a duplicate in the intended box.

Approaches

The most direct brute-force validator examines every row, every column, and every 3 by 3 box. For each group of nine cells, it can compare every pair and reject the board if two values are equal. There are 27 groups in total, and each group has C(9, 2) = 36 pairs, so the worst case performs exactly 27 * 36 = 972 pair comparisons, in addition to the small amount of indexing needed to enumerate the groups. This is absolutely fast enough for a fixed 9 by 9 board, so brute force is not actually too slow for this problem.

The cleaner approach is to process every cell once and remember which digits have already appeared in its row, column, and box. For each cell containing digit x, we ask three questions at once: has x appeared in this row, has it appeared in this column, and has it appeared in this 3 by 3 box? If any answer is yes, the board is invalid. Otherwise we mark x as present in all three places and continue.

The key observation is that the three Sudoku rules are all instances of the same property: within a particular group, every digit may occur at most once. Since there are only nine possible digits, a small boolean array is enough to represent the state of every group. We do not need to compare the current cell against all previous cells.

The resulting method touches exactly 81 cells and performs constant work per cell. It is simpler than the pairwise method while also being the natural generalization if the board size were ever increased.

Approach Time Complexity Space Complexity Verdict
Brute Force O(81²), with 972 pair comparisons for the fixed board O(1) Accepted
Optimal O(81) O(1) Accepted

Here O(81) is technically O(1) because the problem fixes the board size, but writing it as O(81) makes the amount of work clearer.

Algorithm Walkthrough

  1. Create three 9 by 9 boolean structures named rows, cols, and boxes. rows[r][d] records whether digit d has appeared in row r, cols[c][d] does the same for column c, and boxes[b][d] does the same for box b. Using separate structures mirrors the three independent Sudoku constraints.
  2. Scan the grid from the first row to the last, and from the first column to the last. For the current cell (r, c), read its digit and convert it to a zero-based index such as digit - 1.
  3. Compute the 3 by 3 box containing the cell with
box = (r // 3) * 3 + (c // 3)

The expression r // 3 gives the box's horizontal band, while c // 3 gives its position inside that band. Multiplying the first part by 3 converts the pair into one index from 0 through 8.

  1. Before marking anything, check rows[r][digit], cols[c][digit], and boxes[box][digit]. If any one is already true, the same digit has appeared twice in one of the required groups, so immediately print INVALID.
  2. If all three checks are false, mark the digit as present in the current row, column, and box. Future cells in any of those groups will then detect this occurrence.
  3. After all 81 cells have been processed without finding a conflict, print VALID. Since every cell was checked against all three relevant groups, no Sudoku rule can have been violated.

The invariant is that after processing any prefix of the grid, each boolean structure exactly records the digits that have appeared in the corresponding rows, columns, and boxes within that prefix. When a duplicate is encountered, the corresponding boolean is already true, proving that the board violates a rule. If no duplicate is found, every processed group contains each digit at most once, and after all 81 cells are processed, the entire board is valid.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    board = [list(map(int, input().split())) for _ in range(9)]

    rows = [[False] * 9 for _ in range(9)]
    cols = [[False] * 9 for _ in range(9)]
    boxes = [[False] * 9 for _ in range(9)]

    for r in range(9):
        for c in range(9):
            value = board[r][c]

            # The official input guarantees values from 1 to 9,
            # but keeping this check makes the validator complete.
            if not 1 <= value <= 9:
                print("INVALID")
                return

            digit = value - 1
            box = (r // 3) * 3 + (c // 3)

            if rows[r][digit] or cols[c][digit] or boxes[box][digit]:
                print("INVALID")
                return

            rows[r][digit] = True
            cols[c][digit] = True
            boxes[box][digit] = True

    print("VALID")

if __name__ == "__main__":
    solve()

The board is read as nine lists, each containing nine integers. The three boolean arrays then represent the state described in the first algorithm step. A zero-based digit index is convenient because Python arrays use indices from 0 through 8, so value 1 maps to index 0 and value 9 maps to index 8.

The box calculation is the most error-prone expression in the implementation. For example, cell (0, 0) belongs to box 0, cell (2, 2) also belongs to box 0, cell (0, 3) belongs to box 1, and cell (6, 6) belongs to box 8. Both integer divisions are necessary.

The duplicate check must happen before setting the three boolean entries. If the current value has already appeared, one of the entries is true and the board is immediately rejected. If we marked first and checked afterward, the current cell would always look like a duplicate of itself.

There is no integer overflow issue because every index and value is tiny. The explicit range check is technically redundant under the official input guarantee, but it directly implements the stated digit requirement and makes the validator robust to malformed input.

Worked Examples

Sample 1

The first sample is a valid Sudoku grid. The following trace shows representative cells from the scan. The state records whether the current digit was already present before the cell was processed.

Row Column Value Box Row seen? Column seen? Box seen? Action
0 0 1 0 No No No Mark 1
0 1 2 0 No No No Mark 2
0 2 3 0 No No No Mark 3
0 3 4 1 No No No Mark 4
1 0 4 0 No No No Mark 4
1 1 5 0 No No No Mark 5
4 4 9 4 No No No Mark 9
8 8 5 8 No No No Mark 5

Every processed value is new in all three relevant groups. The same invariant continues through all 81 cells, so the algorithm reaches the end and prints VALID.

Sample 2

The second sample has each row filled with the same repeated digit. The very first row already contains a duplicate.

Row Column Value Box Row seen? Column seen? Box seen? Action
0 0 1 0 No No No Mark 1
0 1 1 0 Yes No Yes Print INVALID

The second 1 is already present in both row 0 and box 0. The algorithm returns immediately, so there is no reason to inspect the remaining 79 cells.

Complexity Analysis

Measure Complexity Explanation
Time O(81), effectively O(1) Every one of the 81 cells is processed once with constant-time checks and updates.
Space O(1) Three 9 by 9 boolean structures contain a fixed number of entries.

The board size is fixed by the problem, so the absolute work is extremely small. Even the brute-force method is comfortably within the one-second and 256 MB limits, while the one-pass solution performs only 81 iterations and uses a few hundred boolean entries.

Test Cases

The official samples are included below. Since this problem always has exactly 81 input cells, there is no smaller board size to test, so the minimum-size case is represented by the smallest possible input instance, namely one complete 9 by 9 board.

import sys
import io

def solve():
    input = sys.stdin.readline

    board = [list(map(int, input().split())) for _ in range(9)]

    rows = [[False] * 9 for _ in range(9)]
    cols = [[False] * 9 for _ in range(9)]
    boxes = [[False] * 9 for _ in range(9)]

    for r in range(9):
        for c in range(9):
            value = board[r][c]

            if not 1 <= value <= 9:
                print("INVALID")
                return

            digit = value - 1
            box = (r // 3) * 3 + (c // 3)

            if rows[r][digit] or cols[c][digit] or boxes[box][digit]:
                print("INVALID")
                return

            rows[r][digit] = True
            cols[c][digit] = True
            boxes[box][digit] = True

    print("VALID")

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

sample1 = """\
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
"""

sample2 = """\
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9
"""

# Provided samples
assert run(sample1) == "VALID\n", "sample 1"
assert run(sample2) == "INVALID\n", "sample 2"

# Duplicate in a column, while every row remains unique.
column_duplicate = """\
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
1 7 8 3 2 6 4 5 7
"""
assert run(column_duplicate) == "INVALID\n", "duplicate column"

# Duplicate inside one 3x3 box, but not in the same row or column.
box_duplicate = """\
1 2 3 4 5 6 7 8 9
4 1 6 7 8 9 2 3 5
7 8 9 1 2 3 4 5 6
2 3 4 5 6 1 8 9 7
5 6 1 8 9 7 2 3 4
8 9 7 2 3 4 5 6 1
3 4 2 6 1 5 9 7 8
6 5 1 9 7 8 3 4 2
9 7 8 3 4 2 6 1 5
"""
assert run(box_duplicate) == "INVALID\n", "duplicate 3x3 box"

# A valid board exercising every box boundary.
boundary_valid = """\
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
"""
assert run(boundary_valid) == "VALID\n", "box boundary"

print("All tests passed.")
Test input Expected output What it validates
Official Sample 1 VALID A complete valid Sudoku board
Official Sample 2 INVALID Immediate duplicate detection
column_duplicate INVALID A conflict that appears in a column
box_duplicate INVALID A conflict inside a 3 by 3 box without relying on a row duplicate
boundary_valid VALID Correct handling of all 3 by 3 box boundaries

Edge Cases

The first edge case is a duplicate that occurs only in a column. In column_duplicate, the final row begins with another 1, while that row itself contains distinct values. When the algorithm reaches (8, 0), rows[8][0] is false, but cols[0][0] is already true because the first row contained 1 in that column. The algorithm prints INVALID. This catches implementations that validate rows but forget columns.

The second edge case is a duplicate confined to a 3 by 3 box. In the top-left box of box_duplicate, the value 1 appears at (0, 0) and (1, 1). Those cells have different rows and different columns, so row and column checks alone would not reject them. For (1, 1), the computed box is (1 // 3) * 3 + (1 // 3) = 0, and boxes[0][0] is already true. The output is INVALID. This is the key case for verifying the box formula.

The third edge case is a valid board whose values sit exactly across box boundaries. In boundary_valid, the scan crosses columns 2 and 3, rows 2 and 3, and the later boundaries at rows 5 and 6 and columns 5 and 6. The integer divisions change the box index exactly at those boundaries. No digit is repeated within its row, column, or box, so every check remains false and the final output is VALID. This catches the common off-by-one error of using the wrong box partition.

The all-equal case from Sample 2 exercises the earliest possible failure. After processing the first 1, the second cell in row 0 finds both the row and box flags already set. The algorithm stops after two cells and prints INVALID. This demonstrates why the state must be checked before being updated and why an early return is safe once a violation is found.