Search all 2ⁿ assignments, and see how the work grows.
What to build
A program that finds the first satisfying assignment in counting order, or reports that none exists.
Requirements
- Try assignments in the order product([0, 1], repeat=n) gives (x1 changes slowest).
- Print
satisfiable: v1 … vn after K tries, orunsatisfiable after K trieswith K = 2ⁿ.
Input
Line 1: n and m. Then m clauses, each a line of literals (k or −k).
Output
One line.
Constraints
n ≤ 16; m ≤ 60.
Example
Input:
3 2
1 -2
2 3
Output:
satisfiable: 0 0 1 after 2 tries
Why it works
Without a clever idea, finding an assignment means trying up to 2ⁿ of them, while checking each one is fast: the gap between NP and what we know how to solve.
Examples
Example 1 · Input
3 2 1 -2 2 3
Expected output
satisfiable: 0 0 1 after 2 tries
Example 2 · Input
1 2 1 -1
Expected output
unsatisfiable after 2 tries
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
itertools.product([0, 1], repeat=n) gives every assignment, x1 first, in counting order.
Hint 2
Count the assignments you try, including the one that works.
Solution
Show one correct solution (try it yourself first)
from itertools import product
n, m = map(int, input().split())
clauses = [list(map(int, input().split())) for _ in range(m)]
tries = 0
for values in product([0, 1], repeat=n):
tries += 1
if all(any((values[abs(l) - 1] == 1) == (l > 0) for l in clause) for clause in clauses):
print("satisfiable:", *values, f"after {tries} tries")
break
else:
print(f"unsatisfiable after {tries} tries")