Theory: Solve SAT by brute force

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, or unsatisfiable after K tries with 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")

Lesson: P, NP and NP-completeness →