AI: Solve a Futoshiki puzzle

Combine constraint propagation and search to solve a logic puzzle.

What to build

A program that completes a Futoshiki grid: a Latin square with inequality signs between some pairs of cells.

Requirements

  • Fill the n × n grid with digits 1 to n so that each row and each column contains every digit once, the given digits stay, and every inequality R1 C1 < R2 C2 or R1 C1 > R2 C2 (rows and columns from 1) holds. The puzzle has at most one solution.
  • Print the grid, one row per line without spaces, or no solution.

Input

Line 1: n. Then n lines of digits and .. Then k and k inequality lines.

Output

n lines, or no solution.

Constraints

n ≤ 6.

Example

Input:

3
1..
...
...
2
2 1 > 3 1
1 2 < 1 3

Output:

123
312
231

Why it works

Propagation turns each given digit and inequality into removed values across rows and columns, so most cells are decided before any guessing, and search handles the rest.

Examples

Example 1 · Input
3
1..
...
...
2
2 1 > 3 1
1 2 < 1 3
Expected output
123
312
231
Example 2 · Input
4
2..3
..2.
.4..
...4
4
1 2 < 1 3
2 1 > 2 2
4 2 > 4 3
3 1 < 4 1
Expected output
2143
4321
1432
3214

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Each cell is a variable with domain 1..n (or its given digit); cells in the same row or column must differ, and each inequality is one more binary constraint.

Hint 2

Run AC-3 first, then backtrack on the cell with the smallest domain, running AC-3 again after each choice on a copy of the domains.

Solution

Show one correct solution (try it yourself first)
import copy

n = int(input())
rows = [input().strip() for _ in range(n)]
domains = {(r, c): ({int(rows[r][c])} if rows[r][c] != "." else set(range(1, n + 1))) for r in range(n) for c in range(n)}
arcs = {}


def add(a, b, test):
    arcs.setdefault((a, b), []).append(test)


for r in range(n):
    for c in range(n):
        for k in range(n):
            if k != c:
                add((r, c), (r, k), lambda x, y: x != y)
            if k != r:
                add((r, c), (k, c), lambda x, y: x != y)
for _ in range(int(input())):
    r1, c1, op, r2, c2 = input().split()
    a, b = (int(r1) - 1, int(c1) - 1), (int(r2) - 1, int(c2) - 1)
    if op == "<":
        add(a, b, lambda x, y: x < y)
        add(b, a, lambda x, y: x > y)
    else:
        add(a, b, lambda x, y: x > y)
        add(b, a, lambda x, y: x < y)
pointing = {}
for a, b in arcs:
    pointing.setdefault(b, []).append(a)


def ac3(doms):
    queue = list(arcs)
    queued = set(queue)
    while queue:
        x, y = queue.pop()
        queued.discard((x, y))
        removed = {vx for vx in doms[x] if not any(all(t(vx, vy) for t in arcs[(x, y)]) for vy in doms[y])}
        if removed:
            doms[x] -= removed
            if not doms[x]:
                return False
            for z in pointing[x]:
                if z != y and (z, x) not in queued:
                    queue.append((z, x))
                    queued.add((z, x))
    return True


def solve(doms):
    if not ac3(doms):
        return None
    open_cells = [cell for cell in doms if len(doms[cell]) > 1]
    if not open_cells:
        return doms
    cell = min(open_cells, key=lambda cell: (len(doms[cell]), cell))
    for value in sorted(doms[cell]):
        trial = copy.deepcopy(doms)
        trial[cell] = {value}
        found = solve(trial)
        if found:
            return found
    return None


answer = solve(domains)
if answer:
    for r in range(n):
        print("".join(str(next(iter(answer[(r, c)]))) for c in range(n)))
else:
    print("no solution")

Lesson: Constraint propagation and AC-3 →