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 C2orR1 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
3 1.. ... ... 2 2 1 > 3 1 1 2 < 1 3
123 312 231
4 2..3 ..2. .4.. ...4 4 1 2 < 1 3 2 1 > 2 2 4 2 > 4 3 3 1 < 4 1
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")