A puzzle app lets people play sudoku on boards of different sizes. For a box side b, the board is an n x n grid with n = b * b, split into b x b boxes (a regular sudoku has b = 3, n = 9). Each cell holds 0 for empty, or a number from 1 to n.
Before saving a half-finished board, the app wants a quick sanity check. Write no_clashes(grid) -> bool that returns True if no number appears twice in the same row, the same column, or the same box, and False otherwise. Empty cells never clash, and you don't need to decide whether the board can actually be completed.
no_clashes([[1, 0, 0, 0],
[0, 0, 3, 0],
[0, 4, 0, 0],
[0, 0, 0, 2]]) # True
no_clashes([[1, 0, 0, 0],
[0, 1, 0, 0], # the two 1s share the top-left 2 x 2 box
[0, 0, 0, 0],
[0, 0, 0, 0]]) # False
no_clashes([[0, 2, 0, 2], # two 2s in the first row
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]) # False
no_clashes([[0]]) # True
Constraints:
n = b * bwith1 <= b <= 20, so the grid has up to 400 x 400 = 160,000 cells.- Every value is an integer in
[0, n].
Scanning the whole row, column and box again for every filled cell is O(n³), too slow for the largest boards. Aim for O(n²), a constant amount of work per cell.
Show hint
Visit every cell once. For each row, each column and each box, keep a record of the numbers already placed there, so a clash is detected the moment a number is seen a second time. The box of cell (r, c) can be identified by (r // b, c // b).