Solve Sudoku as a constraint satisfaction problem.
What to build
A program that solves a 4 × 4 or 9 × 9 Sudoku.
Requirements
- Every row, column and box (2 × 2 or 3 × 3) must contain each digit from 1 to n exactly once. The puzzle has exactly one solution, or none.
- Print the solved grid, one row per line with no spaces, or
no solutionif the givens break the rules or cannot be completed.
Input
Line 1: n (4 or 9). Then n lines of digits, with . for an empty cell.
Output
n lines, or no solution.
Constraints
Solutions must be found within the time limit, so plain trial of every cell in order may be too slow for hard 9 × 9 puzzles.
Example
Input:
4
123.
3..2
2...
..21
Output:
1234
3412
2143
4321
Why it works
Filling the most constrained cell first means a wrong guess shows up as an empty domain almost at once, so the search stays tiny.
Examples
4 123. 3..2 2... ..21
1234 3412 2143 4321
4 11.. .... .... ....
no solution
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Each empty cell is a variable whose domain is the digits not already in its row, column or box.
Hint 2
Always fill the empty cell with the fewest possible digits next (MRV); if it has none, back up.
Solution
Show one correct solution (try it yourself first)
n = int(input())
box = 2 if n == 4 else 3
grid = [[0 if ch == "." else int(ch) for ch in input().strip()] for _ in range(n)]
def options(r, c):
used = set(grid[r]) | {grid[i][c] for i in range(n)}
br, bc = r - r % box, c - c % box
used |= {grid[i][j] for i in range(br, br + box) for j in range(bc, bc + box)}
return [d for d in range(1, n + 1) if d not in used]
def givens_ok():
for r in range(n):
for c in range(n):
d = grid[r][c]
if d:
grid[r][c] = 0
ok = d in options(r, c)
grid[r][c] = d
if not ok:
return False
return True
def solve():
best = None
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
choices = options(r, c)
if best is None or len(choices) < len(best[2]):
best = (r, c, choices)
if best is None:
return True
r, c, choices = best
for d in choices:
grid[r][c] = d
if solve():
return True
grid[r][c] = 0
return False
if givens_ok() and solve():
for row in grid:
print("".join(map(str, row)))
else:
print("no solution")