F2.2.1 Audit Three DPLL Runs

MediumDebug20 minRecorded formal evidenceReview the topic

Problem

Description

Three hand runs of DPLL are on the page. Two of them break a rule once. Find the step.

Three formulas are shown with a hand run of DPLL on each. Two runs break one rule once. Choose the broken rule for each run and select the first step that breaks it. A clean run takes its last step.

Pinned interface
PortDirectionBits
clkinput1
ainput1
binput1
cinput1
dinput1
einput1
satoutput1
Full specification

Each card shows a formula in clauses and a hand run of DPLL on it. The rules are fixed. A false clause is a conflict. A conflict undoes the run back to the most recent decision that still has an untried value, and flips it. Otherwise the lowest-numbered unit clause forces its free literal. Otherwise the first free variable in alphabetical order is decided as 1.

For every card, choose which rule the run breaks, or that it breaks none. Then select one line. For a broken rule, select the first step that breaks it. For a clean run, select its last step.

A run that breaks a rule can still end with a correct answer. Check each step against the rules, not only the result.

Recorded caseLocal contract
Run AThe recorded run is a cover of the formula as a circuit: the solver found a satisfying assignment. It may differ from the one in the hand run.
Run BThe recorded run is a cover of the formula as a circuit: the solver found a satisfying assignment. It may differ from the one in the hand run.
Run CThe recorded run is a cover of the formula as a circuit: the solver found no satisfying assignment.
Execution ruleMeaning
InterfaceUse the pinned port names, directions and bit widths shown above. Observed state and tracker outputs are not environment inputs.
SamplingOne positive edge of clk; binary values. Non-overlapping implication observes the next sample. Reset and initialization follow the source and contract above.
SubmissionSelect a cause and a numbered line for every recorded case. Checking these choices runs no engine.
How this is gradedThe cause and responsible line must agree with each recorded local contract. A timeout or induction candidate must not be diagnosed as a reachable RTL failure.

Run A

The recorded run is a cover of the formula as a circuit: the solver found a satisfying assignment. It may differ from the one in the hand run.

PASS · cover · depth 2 · 705 ms

Recorded solver trace
01clkfreeafreebfreecfreedfreeesat
Scroll horizontally ↔

Samples from the measured run. Free input lanes are shaded; the terminal VCD record is omitted.

Numbered source and task
  1  clause 1: (a ∨ b)
  2  clause 2: (¬a ∨ c)
  3  clause 3: (¬c ∨ ¬d)
  4  clause 4: (d ∨ e)
  5  clause 5: (¬e ∨ ¬b ∨ c)
  6  clause 6: (¬a ∨ ¬e ∨ b)
  7  --- hand run ---
  8  1. decide a = 1 (level 1)
  9  2. propagate c = 1: clause 2 (¬a ∨ c) has one free literal
 10  3. decide b = 1 (level 2)
 11  4. propagate d = 0: clause 3 (¬c ∨ ¬d) has one free literal
 12  5. propagate e = 1: clause 4 (d ∨ e) has one free literal
 13  6. every clause is true: SAT with a = 1, b = 1, c = 1, d = 0, e = 1

Run B

The recorded run is a cover of the formula as a circuit: the solver found a satisfying assignment. It may differ from the one in the hand run.

PASS · cover · depth 2 · 681 ms

Recorded solver trace
01clkfreeafreebfreecfreedfreeesat
Scroll horizontally ↔

Samples from the measured run. Free input lanes are shaded; the terminal VCD record is omitted.

Numbered source and task
  1  clause 1: (¬a ∨ b ∨ c)
  2  clause 2: (¬b ∨ d)
  3  clause 3: (¬c ∨ ¬d)
  4  clause 4: (¬b ∨ ¬c)
  5  clause 5: (a ∨ e)
  6  clause 6: (¬e ∨ c ∨ d)
  7  clause 7: (¬a ∨ ¬b ∨ ¬d)
  8  --- hand run ---
  9  1. decide a = 1 (level 1)
 10  2. decide b = 1 (level 2)
 11  3. propagate d = 1: clause 2 (¬b ∨ d) has one free literal
 12  4. conflict: clause 7 (¬a ∨ ¬b ∨ ¬d) is false
 13  5. backtrack: undo back to the decision on a, now a = 0
 14  6. propagate e = 1: clause 5 (a ∨ e) has one free literal
 15  7. decide b = 1 (level 2)
 16  8. propagate d = 1: clause 2 (¬b ∨ d) has one free literal
 17  9. propagate c = 0: clause 3 (¬c ∨ ¬d) has one free literal
 18  10. every clause is true: SAT with a = 0, b = 1, c = 0, d = 1, e = 1

Run C

The recorded run is a cover of the formula as a circuit: the solver found no satisfying assignment.

FAIL · cover · depth 2 · 560 ms

No witness was produced for this query.

Numbered source and task
  1  clause 1: (a ∨ b)
  2  clause 2: (a ∨ ¬b)
  3  clause 3: (¬a ∨ c)
  4  clause 4: (¬a ∨ ¬c ∨ d)
  5  clause 5: (¬c ∨ ¬d)
  6  --- hand run ---
  7  1. decide a = 1 (level 1)
  8  2. propagate c = 1: clause 3 (¬a ∨ c) has one free literal
  9  3. propagate d = 1: clause 4 (¬a ∨ ¬c ∨ d) has one free literal
 10  4. conflict: clause 5 (¬c ∨ ¬d) is false
 11  5. backtrack: undo back to the decision on a, now a = 0
 12  6. propagate b = 1: clause 1 (a ∨ b) has one free literal
 13  7. conflict: clause 2 (a ∨ ¬b) is false
 14  8. no decision is left to flip: UNSAT

Requirements

  • Use the published ports and widths. The checker and the DUT variants are owned by the judge.
  • Do not add assumptions unless the statement explicitly asks for one. A passing assertion without a reachable trigger is insufficient.

Hints

Hint 1

Before each decision, look for a clause with one free literal and no true literal.

Hint 2

At each conflict, list the open decisions in order. Only the last one may be flipped.

Hint 3

Use the three rules of the "DPLL by hand" section in F2.2.

Single clock, binary values, synchronous reset. The judge checks the pinned interface, reachability and the declared proof or bound. UNKNOWN, resource limits and timeouts remain inconclusive.

The recordings are fixed. Checking a diagnosis does not run an engine.

More problems on this topic

Report a problem with this page

Worked solution

Opening the solution ends an unsolved rated attempt. Solving it first costs nothing.

Your Diagnosis

Run A
Run B
Run C

Recorded evidence · no engine run

Recent Submissions