This page verifies a completed 9x9 Sudoku board in Python. The original sum-based solution is kept below; the added sections explain the constraint structure, show a correct and complete set-based checker, and extend it to a backtracking solver.
#!/usr/bin/env python
import pprint
# ----------------------------------------------------------------------------#
# Define a 9x9 matrix representing a Sudoku board
matrix1 = [
[7, 1, 8, 5, 3, 2, 9, 4, 6],
[5, 3, 2, 6, 9, 4, 1, 8, 7],
[6, 9, 4, 7, 1, 8, 3, 2, 5],
[1, 2, 7, 3, 4, 5, 8, 6, 9],
[9, 8, 6, 1, 2, 7, 4, 5, 3],
[3, 4, 5, 9, 8, 6, 2, 7, 1],
[4, 6, 3, 8, 7, 9, 5, 1, 2],
[8, 7, 9, 2, 5, 1, 6, 3, 4],
[2, 5, 1, 4, 6, 3, 7, 9, 8],
]
# ----------------------------------------------------------------------------#
def verify_sudoku_board(board, value):
"""
Verifies whether a given 9x9 Sudoku board is valid by checking that
each row, column, and 3x3 sub-grid (window) sums to a specified value.
Args:
board (list of list of int): The 9x9 Sudoku board represented as a list of lists.
value (int): The expected sum of each row, column, and 3x3 sub-grid.
Returns:
bool: True if the board is valid according to Sudoku rules, False otherwise.
"""
# Verify each row sums to the given value
for row in range(0, 9):
if sum(board[row]) != value:
return False
# Verify each column sums to the given value
for col in range(0, 9):
total = 0
for row in range(0, 9):
total += board[row][col]
# After finishing a column, check if the total sum matches the expected value
if row == 8:
if total != value:
return False
# Verify each 3x3 sub-grid (window) sums to the given value
for start in range(0, 9, 3):
total = 0
for col in range(start, start + 3):
for row in range(start, start + 3):
total += board[row][col]
if total != value:
return False
return True
# ----------------------------------------------------------------------------#
if __name__ == "__main__":
pp = pprint.PrettyPrinter()
pp.pprint(matrix1)
result = verify_sudoku_board(matrix1, 45)
print(result)
matrix1):This is a 9x9 matrix representing a completed Sudoku board. Each inner list represents a row in the Sudoku puzzle.
verify_sudoku_board(board, value):Purpose: This function checks if a given 9x9 Sudoku board is valid. It verifies that:
True if the board is valid according to the above conditions, otherwise False.
__main__):Purpose: To execute the script and verify the given Sudoku board.
Steps:
matrix1 using Python’s pprint module to make it easy to visualize.verify_sudoku_board function with the matrix and the expected sum (45).Given the provided Sudoku matrix, the function will check each row, column, and 3x3 sub-grid. If all checks pass (i.e., all sums equal 45), it will print True, indicating that the Sudoku board is valid.
Sudoku verification is a classic interview and warm-up problem because it tests careful indexing more than clever algorithms. A completed board is valid when every row, every column and every 3x3 box contains the digits 1 through 9 exactly once. The checker must examine 27 groups of nine cells. Done carefully, that is 243 cell reads, and for a general n x n board (with n a perfect square) the cost is O(n^2), linear in the number of cells. The interesting parts are computing which box a cell belongs to and choosing a check that is actually sufficient.
Rows and columns are direct indexes. Boxes need a small formula: the box row is r // 3, the box column is c // 3, and numbering boxes left to right, top to bottom gives b = 3 * (r // 3) + c // 3. Alternatively, iterate over box origins (br, bc) in steps of three and read the 3x3 block starting there. Either way, all nine boxes must be checked, not just the three on the diagonal.
The original function compares each group's sum with 45. That rejects many invalid boards but accepts some, because different multisets can share the same sum; a row of nine 5s sums to 45. Its box loop also walks row and col over the same start range, so it visits only boxes (0,0), (1,1) and (2,2). A sufficient test compares each group with the set of digits 1 to 9, which simultaneously checks range and uniqueness.
DIGITS = set(range(1, 10))
def is_valid_sudoku(board):
rows = [set(r) for r in board]
cols = [{board[r][c] for r in range(9)} for c in range(9)]
boxes = [{board[r][c] for r in range(br, br + 3) for c in range(bc, bc + 3)}
for br in (0, 3, 6) for bc in (0, 3, 6)]
return all(g == DIGITS for g in rows + cols + boxes)
def first_error(board):
"""Single pass that reports the first violation, useful for debugging."""
seen = set()
for r in range(9):
for c in range(9):
v = board[r][c]
if v not in DIGITS:
return f"bad value {v} at ({r},{c})"
for key in (("row", r, v), ("col", c, v), ("box", 3 * (r // 3) + c // 3, v)):
if key in seen:
return f"duplicate {v} in {key[0]} {key[1]} at ({r},{c})"
seen.add(key)
return None
bad = [row[:] for row in matrix1]
bad[0][0], bad[0][1] = bad[0][1], bad[0][0] # swap two cells in row 0
print(is_valid_sudoku(matrix1), is_valid_sudoku(bad)) # True False
print(first_error(bad))
Swapping two cells in a row keeps every row sum at 45 and keeps the row itself valid, but it breaks two columns, which the set-based checker catches and the single-pass version reports with a location.
def solve(board):
"""Fill zeros in place; return True if solved."""
for r in range(9):
for c in range(9):
if board[r][c] == 0:
used = set(board[r]) | {board[i][c] for i in range(9)} | {
board[i][j] for i in range(3*(r//3), 3*(r//3)+3) for j in range(3*(c//3), 3*(c//3)+3)}
for v in DIGITS - used:
board[r][c] = v
if solve(board):
return True
board[r][c] = 0 # undo and backtrack
return False
return True
puzzle = [row[:] for row in matrix1]
for r, c in [(0, 0), (4, 4), (8, 8), (2, 5)]:
puzzle[r][c] = 0
print(solve(puzzle), puzzle == matrix1) # True True
Backtracking treats Sudoku as a constraint satisfaction problem: choose an empty cell, try each digit consistent with its row, column and box, recurse, and undo on failure. Picking the cell with the fewest candidates first (the minimum-remaining-values heuristic) shrinks the search dramatically on hard puzzles.
| Approach | Time | Space | Correct? |
|---|---|---|---|
| Sum per group (original) | O(n^2) | O(1) | No: misses duplicates, checks 3 of 9 boxes |
| Set per group | O(n^2) | O(n) | Yes |
| Single pass with seen set | O(n^2) | O(n^2) | Yes, and reports the location |
| Bitmask per group | O(n^2) | O(n) | Yes, fastest in low-level languages |
| Backtracking solver | Exponential worst case | O(n^2) | Solves, not just verifies |