AI: A Sudoku solver

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 solution if 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

Example 1 · Input
4
123.
3..2
2...
..21
Expected output
1234
3412
2143
4321
Example 2 · Input
4
11..
....
....
....
Expected output
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")

Lesson: Constraint satisfaction problems →