
A constrained schedule can be written as a Boolean formula whose satisfying assignments represent valid complete schedules. For one frozen five-suite example, the formula has 17 variables and 53 clauses, and exhaustive enumeration finds exactly 19 models: one for each valid schedule in the original benchmark.
This is a worked encoding of one finite instance. It does not report how fast a SAT solver runs, establish a complexity result, or claim a new general encoding method.
From compatible assignments to Boolean variables
The benchmark assigns each of five suites, A through E, to a different one of five environment profiles. Its compatibility relation is:
| Suite | Compatible profiles |
|---|---|
| A | 1, 2, 3, 4, 5 |
| B | 1, 4, 5 |
| C | 1, 3, 5 |
| D | 1, 2, 4 |
| E | 2, 3, 5 |
Give each compatible suite–profile pair its own Boolean variable. There are 17 such edges. For each suite, a positive clause requires at least one compatible profile to be selected; pairwise negative clauses prevent selecting more than one. Apply the same construction to each profile so it is assigned to exactly one suite. Together, these constraints describe perfect matchings in this bipartite compatibility graph.
The resulting DIMACS formula has 53 clauses, maximum width 5, and no auxiliary variables. Each valid schedule sets its five corresponding edge variables to true. Conversely, every satisfying assignment selects one compatible profile for each suite without reusing a profile, so it decodes to a valid schedule.
What exhaustive checking adds
The accompanying standard-library Python verifier regenerates the clauses from the compatibility graph, checks the generated text against the DIMACS file byte for byte, then examines all (2^{17}=131072) assignments. It finds exactly 19 satisfying assignments and compares the decoded set against the benchmark's frozen list of 19 schedules.
That is a direct, reproducible check of this concrete finite formula and its mapping to the known schedule set. It is not a solver performance test: no external SAT solver is run and no timing or scaling comparison is reported. The count of 19 applies to this graph alone.
An established construction, made concrete
Using one variable per graph edge and pairwise exclusions between incident edges is an established matching encoding. Zulkoski, Ganesh and Czarnecki describe this pattern in §4 of their MATHCHECK paper. Requiring at least one selected edge at every vertex completes the perfect-matching constraint here. This article makes no novelty or priority claim for that method; the contribution is the explicit F38 instance, generated DIMACS file and exhaustive finite verification.
The commit-pinned Research Artifact Ledger package provides the formula, verifier and recorded output. It is an AI-assisted synthetic demonstration. A separate AI reviewer challenged the encoding and its failure cases; this is not human specialist review or peer review.
The underlying F38 benchmark compares sampling distributions for the same schedules. This encoding does not establish those earlier probability results or change their conclusions. It provides a checkable Boolean representation of the fixed schedule set, and nothing here evaluates a production QA system or uses private client data.



No published comments yet.