quick, neat and underused (half 1 of N) — The Coding Nest
Earlier than I began doing analysis for Intelligent Data Analysis (IDA) group at FEE CTU, I noticed SAT solvers as academically fascinating however did not assume that they’ve many sensible makes use of outdoors of different educational functions. After spending ~1.5 years working with them, I’ve to say that trendy SAT solvers are quick, neat and criminally underused by the business.
Introduction
Boolean satisfiability drawback (SAT) is the issue of deciding whether or not a formulation in boolean logic is satisfiable. A formulation is satisfiable when no less than one interpretation (an project of true and false values to logical variables) results in the formulation evaluating to true. If no such interpretation exists, the formulation is unsatisfiable.
What makes SAT fascinating is {that a} variant of it was the primary drawback to be confirmed NP-complete, which roughly implies that plenty of different issues might be translated into SAT in cheap time, and the answer to this translated drawback might be transformed again into an answer for the unique drawback.
For instance, the often-talked-about dependency administration drawback, can be NP-Full and thus interprets into SAT, and SAT may very well be translated into dependency supervisor. The issue our group labored on, producing key and lock cuttings based mostly on user-provided lock-chart and manufacturer-specified geometry, can be NP-complete.
I’ll possible write about master-key programs and our strategy in the direction of fixing them later, however to maintain this publish moderately quick, we are going to as an alternative use Sudoku for sensible examples.
Utilizing SAT solvers
Lately, SAT virtually at all times refers to CNF-SAT, a boolean satisfaction drawback for formulation in conjunctive normal form (CNF). Because of this your entire formulation is a conjunction (AND) of clauses, with every clause being a disjunction (OR) of literals. Some examples:
- $(A vee B) wedge (B vee C)$
- $(A vee B) wedge C$
- $A vee B$
- $A wedge C$
There are two methods to cross a formulation to a SAT solver: by utilizing a semi-standard file format often called DIMACS, or by utilizing the SAT solver as a library. In real-world functions, I desire utilizing SAT solver as a library (e.g. MiniSat for C++), however the DIMACS format helps you to prototype your software shortly, and shortly check the efficiency traits of various solvers in your drawback.
DIMACS format
DIMACS is a line oriented format, consisting of three completely different fundamental forms of traces.
- A remark line. Any line that begins with “c” is remark line.
- A abstract line. This line comprises details about the type and dimension of the issue inside the file. A abstract line begins with “p”, continues with the type of the issue (generally “cnf”), the variety of variables and the variety of clauses inside this drawback. Some DIMACS parsers anticipate this line to be the primary non-comment line, however some parsers can deal with the file with out it.
- A clause line. A clause line consists of space-separated numbers, ending with a 0. Every non-zero quantity denotes a literal, with adverse numbers being adverse literals of that variable, and 0 being the terminator of a line.
For instance, this formulation
$$(A vee B vee C) wedge (neg A vee B vee C) wedge (A vee neg B vee C) wedge (A vee B vee neg C)$$
can be transformed into DIMACS as
c An instance formulation
c
p cnf 3 4
1 2 3 0
-1 2 3 0
1 -2 3 0
1 2 -3 0
Minisat’s C++ interface
MiniSat is a reasonably easy and performant SAT solver that additionally offers a pleasant C++ interface and we maintain a modernised fork with CMake integration. The C++ interface to MiniSat makes use of 3 fundamental vocabulary sorts:
Minisat::Solver– Implementation of the core solver and its algorithms.Minisat::Var– Illustration of a variable.Minisat::Lit– Illustration of a concrete (constructive or adverse) literal of a variable.
The distinction between a variable and a literal is that the literal is a concrete “analysis” of a variable inside a clause. For instance, formulation $ (A vee B vee neg C) wedge (neg A vee neg B) $ comprises 3 variables, $A$, $B$ and $C$, however it comprises 5 literals, $A$, $neg A$, $B$, $neg B$ and $neg C$.
MiniSat’s interface additionally makes use of one utility sort: Minisat::vec<T>, a container much like std::vector, that’s used to cross clauses to the solver.
The next instance makes use of MiniSat’s C++ API to resolve the identical clause as we used within the DIMACS instance.
// fundamental.cpp:
#embody <minisat/core/Solver.h>
#embody <iostream>
int fundamental() {
utilizing Minisat::mkLit;
utilizing Minisat::lbool;
Minisat::Solver solver;
// Create variables
auto A = solver.newVar();
auto B = solver.newVar();
auto C = solver.newVar();
// Create the clauses
solver.addClause( mkLit(A), mkLit(B), mkLit(C));
solver.addClause(~mkLit(A), mkLit(B), mkLit(C));
solver.addClause( mkLit(A), ~mkLit(B), mkLit(C));
solver.addClause( mkLit(A), mkLit(B), ~mkLit(C));
// Test for resolution and retrieve mannequin if discovered
auto sat = solver.resolve();
if (sat) {
std::clog << "SATn"
<< "Mannequin discovered:n";
std::clog << "A := " << (solver.modelValue(A) == l_True) << 'n';
std::clog << "B := " << (solver.modelValue(B) == l_True) << 'n';
std::clog << "C := " << (solver.modelValue(C) == l_True) << 'n';
} else {
std::clog << "UNSATn";
return 1;
}
}
As a result of all of our clauses have size $le 3$, we will get away with simply utilizing utility overloads that MiniSat offers, and need not use Minisat::vec for the clauses.
We may even have to construct the binary. Assuming you have got put in our fork of MiniSat (both from GitHub, or from vcpkg), it offers correct CMake integration and writing the CMakeLists.txt is trivial:
cmake_minimum_required (VERSION 3.5)
challenge (minisat-example LANGUAGES CXX)
set(CMAKE_CXX_EXTENSIONS OFF)
find_package(MiniSat 2.2 REQUIRED)
add_executable(minisat-example
fundamental.cpp
)
target_link_libraries(minisat-example MiniSat::libminisat)
Constructing the instance and working it ought to offer you this output:
SAT
Mannequin discovered:
A := 0
B := 1
C := 1
Conversion to CNF
Only a few issues are naturally expressed as a logical formulation within the CNF format, which implies that after formulating an issue as a SAT, we frequently have to convert it into CNF. Probably the most fundamental strategy is to create an equal formulation utilizing De-Morgan legal guidelines, distributive legislation and the truth that two negations cancel out. This strategy has two benefits: one, it’s easy and clearly right. Two, it doesn’t introduce new variables. Nevertheless, it has one important drawback: some formulation result in exponentially giant CNF conversion.
The opposite strategy is to create an equisatisfiable CNF formulation, however we cannot be overlaying that on this publish.
Some frequent equivalencies are within the desk under.
| Authentic clause | Equal clause |
|---|---|
| $ neg neg alpha $ | $ alpha $ |
| $ alpha implies beta $ | $ neg alpha vee beta $ |
| $ neg ( alpha wedge beta ) $ | $ neg alpha vee neg beta $ |
| $ neg ( neg alpha wedge neg beta ) $ | $ alpha vee beta $ |
| $ (alpha wedge beta) vee gamma $ | $ (alpha vee gamma) wedge (beta vee gamma) $ |
| $ alpha iff beta $ | $ left(alpha implies beta proper) wedge left(alpha impliedby beta proper) $ |
Clearly, you do not have to recollect these identities, however understanding no less than a few of them (implication) is far sooner than deriving them from the reality tables each time.
Fixing Sudoku utilizing SAT
With this background, we will now take a look at how we may use a real-world drawback, similar to Sudoku, utilizing a SAT solver. First, we are going to go over the principles of Sudoku and the way they are often translated into (CNF-)SAT. Then we are going to go over implementing this converter in C++ and benchmarking the outcomes.
Fast overview of Sudoku
Sudoku is a puzzle the place it’s good to place numbers 1-9 right into a 9×9 grid consisting of 9 3×3 bins, following these guidelines:
- Every row comprises the entire numbers 1-9
- Every column comprises the entire numbers 1-9
- Every of the 3×3 bins comprises the entire numbers 1-9
We are able to additionally restate this guidelines as:
- No row comprises duplicate numbers
- No column comprises duplicate numbers
- No 3×3 field comprises duplicate numbers
As a result of these guidelines alone would not make for a very good puzzle, a number of the positions are prefilled by the puzzle setter, and a correct Sudoku puzzle ought to have just one attainable resolution.
Translating the principles
Step one in translating an issue to SAT is to determine what needs to be modelled by way of variables, and what needs to be modelled by way of clauses over these variables. With Sudoku, the pure factor to do is to mannequin positions as variables, however in SAT, every variable can solely have 2 values: “true” and “false”. This implies we can’t simply assign every place a variable, as an alternative we’ve got to assign every mixture of place and worth a variable. We are going to denote such variable as $x_{r, c}^{v}$. If variable $x_{r, c}^{v}$ is ready to “true”, then the quantity in $r$-th row and $c$-th column is $v$.
Utilizing this notation, let’s translate the Sudoku guidelines from the earlier part into SAT.
Rule 1 (No row comprises duplicate numbers)
[
forall (r, v) in (rows times values):
operatorname{exactly-one}(x_{r, 0}^{v}, x_{r, 1}^{v}, dots, x_{r, 8}^{v})
]
In plain phrases, for every row and every worth, we wish precisely one column in that row to have that worth. We do this by utilizing a helper referred to as $operatorname{exactly-one}$, that generates a set of clauses that be sure that precisely one of the passed-in literals consider to “true”.
We are going to see learn how to outline $operatorname{exactly-one}$ later. First, we are going to translate the opposite Sudoku guidelines into these pseudo-boolean formulation.
Rule 2 (No column comprises duplicate numbers)
[
forall (c, v) in (columns times values):
operatorname{exactly-one}(x_{0, c}^{v}, x_{1, c}^{v}, dots, x_{8, c}^{v})
]
This works analogically with Rule 1, in that for every column and every worth, we wish precisely one row to have that worth.
Rule 3 (Not one of the 3×3 bins comprise duplicate numbers)
This rule works precisely the identical approach as the primary two: for every field and every worth, we wish precisely one place within the field to have that worth.
[forall (box, value) in (boxes times values):
operatorname{exactly-one}(operatorname{literals-in-box}(box, value))
]
Despite the fact that it appears to be sufficient at first look, these 3 guidelines are in reality not sufficient to correctly specify Sudoku. It’s because an answer like this one:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | x | . | . | . | . | . | . | . | . |
| 1 | . | . | . | x | . | . | . | . | . |
| 2 | . | . | . | . | . | . | x | . | . |
| 3 | . | x | . | . | . | . | . | . | . |
| 4 | . | . | . | . | x | . | . | . | . |
| 5 | . | . | . | . | . | . | . | x | . |
| 6 | . | . | x | . | . | . | . | . | . |
| 7 | . | . | . | . | . | x | . | . | . |
| 8 | . | . | . | . | . | . | . | . | x |
the place “x” denotes a place the place all variables are set to “true” and “.” denotes a place the place no variables are set to “true”, is legitimate in keeping with the principles as given to the SAT solver.
It’s because we function with an unspoken assumption, that every place can comprise just one quantity. This makes excellent sense to a human, however the SAT solver doesn’t perceive the which means of the variables, it solely sees clauses it was given. We are able to repair this just by including yet another rule:
Rule 4 (Every place comprises precisely one quantity)
[forall (r, c) in (rows times columns): operatorname{exactly-one}(x_{r, c}^{1}, x_{r, c}^{2}, ldots, x_{r, c}^{9}))
]
With this rule in place, we’ve got totally translated the principles of Sudoku into SAT and may use a SAT solver to assist us resolve sudoku cases. However earlier than we do this, we have to outline the $operatorname{exactly-one}$ helper our description of Sudoku depends on.
exactly-one helper
There is no such thing as a strategy to encode numeric constraints natively in boolean logic, however usually you’ll be able to decompose these constraints into less complicated phrases and encode these. Many analysis papers have been written concerning the environment friendly encoding of particular constraints and different devices, however on this publish, we solely have to cope with the most typical and one of many easiest constraints attainable: “precisely one in all this set of literals has to judge to true”. Everybody who works with SAT usually can write this constraint from reminiscence, however we are going to derive it from first rules as a result of it exhibits how extra complicated constraints might be constructed.
Step one is to decompose the constraint $x == n$ into two components: $x ge n$ and $x le n$, or for our particular case, $x ge 1$ and $x le 1$, or, translated into the world of SAT, no less than 1 literal has to judge to “true”, and not more than 1 literal can consider to “true”. Forcing at least one literal to be true is straightforward, simply place all of them into one giant disjunction:
[bigvee_{lit in Literals} lit
]
Forcing at most one literal to be true appears tougher, however with a slight restating of the logic, it additionally turns into fairly straightforward. At most one literal is true when there isn’t a pair of literals the place each of the literals are true on the identical time.
[neg bigvee_{i in 1..n, j in 1..n, i neq j} lit_{i} wedge lit_{j}
]
This set of clauses says precisely that, however it has one drawback: it isn’t in CNF. To transform them into CNF, we’ve got to make use of some of the identities in the previous section on converting formulas to CNF. Particularly, the truth that negating a disjunction results in a conjunction of negations, and negating a conjunction results in a disjunction of negations. Utilizing these, we get the next CNF formulation:
[bigwedge_{i in 1..n, j in 1..n, i neq j} neg lit_{i} vee neg lit_{j}
]
We are able to additionally use the truth that each conjunction and disjunction are commutative (there isn’t a distinction between $x wedge y$ and $y wedge x$) to halve the variety of clauses we create, as we solely want to contemplate literal pairs the place $i < j$.
Now that we all know learn how to restrict the variety of “true” literals to each no less than 1 and at most 1, limiting the variety of “true” literals to precisely 1 is trivial; simply apply each constraints on the identical time by way of conjunction.
C++ implementation
Now that we all know learn how to describe Sudoku as a set of boolean clauses in CNF, we will implement a C++ code that makes use of this information to resolve arbitrary Sudoku. For brevity, this publish will solely comprise related excerpts, but you can find the entire resulting code on GitHub.
The very first thing we have to resolve is addressing variables, particularly changing a (row, column, worth) triple into a selected worth that represents it within the SAT solver. As a result of Sudoku is extremely common, we will get away with linearizing the three dimensions into one, and get the variety of variable similar to $x_{r, c}^{v}$ as r * 9 * 9 + c * 9 + v. We are able to additionally use the truth that Minisat::Varis only a plain int numbered from 0 to keep away from storing the variables in any respect as a result of we will at all times compute the corresponding variable on-demand:
Minisat::Var toVar(int row, int column, int worth) {
return row * columns * values + column * values + worth;
}
Now that we will shortly retrieve the SAT variable from a triplet of (row, column, worth), however earlier than we will use the variables, they should be allotted contained in the SAT solver:
void Solver::init_variables() {
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < columns; ++c) {
for (int v = 0; v < values; ++v) {
static_cast<void>(solver.newVar());
}
}
}
}
With the variables allotted, we will begin changing the SAT model of Sudoku guidelines into C++ code.
Rule 1 (No row comprises duplicate numbers)
for (int row = 0; row < rows; ++row) {
for (int worth = 0; worth < values; ++worth) {
Minisat::vec<Minisat::Lit> literals;
for (int column = 0; column < columns; ++column) {
literals.push(Minisat::mkLit(toVar(row, column, worth)));
}
exactly_one_true(literals);
}
}
Rule 2 (No column comprises duplicate numbers)
for (int column = 0; column < columns; ++column) {
for (int worth = 0; worth < values; ++worth) {
Minisat::vec<Minisat::Lit> literals;
for (int row = 0; row < rows; ++row) {
literals.push(Minisat::mkLit(toVar(row, column, worth)));
}
exactly_one_true(literals);
}
}
Rule 3 (Not one of the 3×3 bins comprise duplicate numbers)
This rule leads to essentially the most complicated code, because it requires two iterations — one to iterate over the entire bins and one to gather variables inside every field. Nevertheless, the ensuing code continues to be pretty trivial:
for (int r = 0; r < 9; r += 3) {
for (int c = 0; c < 9; c += 3) {
for (int worth = 0; worth < values; ++worth) {
Minisat::vec<Minisat::Lit> literals;
for (int rr = 0; rr < 3; ++rr) {
for (int cc = 0; cc < 3; ++cc) {
literals.push(Minisat::mkLit(toVar(r + rr, c + cc, worth)));
}
}
exactly_one_true(literals);
}
}
}
Rule 4 (Every place comprises precisely one quantity)
for (int row = 0; row < rows; ++row) {
for (int column = 0; column < columns; ++column) {
Minisat::vec<Minisat::Lit> literals;
for (int worth = 0; worth < values; ++worth) {
literals.push(Minisat::mkLit(toVar(row, column, worth)));
}
exactly_one_true(literals);
}
}
We additionally have to outline the exactly_one_true helper:
void Solver::exactly_one_true(Minisat::vec<Minisat::Lit> const& literals) {
solver.addClause(literals);
for (size_t i = 0; i < literals.dimension(); ++i) {
for (size_t j = i + 1; j < literals.dimension(); ++j) {
solver.addClause(~literals[i], ~literals[j]);
}
}
}
With these snippets, we’ve got outlined a mannequin of Sudoku as SAT. There are nonetheless 2 items of the solver lacking: a way to specify values within the pre-filled positions of the board and a way that extracts the discovered resolution to the puzzle.
Fixing the values in particular positions is straightforward, we will simply add a unary clause for every specified place:
bool Solver::apply_board(board const& b) {
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < columns; ++col) {
auto worth = b[row][col];
if (worth != 0) {
solver.addClause(Minisat::mkLit(toVar(row, col, worth - 1)));
}
}
}
return ret;
}
As a result of the one strategy to fulfill a unary clause is to set the suitable variable to the polarity of the contained literal, this forces the particular place to at all times comprise the specified worth.
To retrieve an answer, we want to have the ability to decide a place’s worth. As a result of solely one of many variables for any given place might be set to true, the worth similar to that particular variable is the worth of the given place:
board Solver::get_solution() const {
board b(rows, std::vector<int>(columns));
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < columns; ++col) {
for (int val = 0; val < values; ++val) {
if (solver.modelValue(toVar(row, col, val)).isTrue()) {
b[row][col] = val + 1;
break;
}
}
}
}
return b;
}
With the solver completed, we will go on to benchmarking its efficiency.
Benchmarks
So far as I may inform from a cursory search, there are not any commonplace check suites for benchmarking Sudoku solvers. I made a decision to observe Norvig’s blog post about his own Sudoku solver and use this set of 95 hard Sudokus for measuring the efficiency of my solver.
The measurements have been finished on PC with factory-clocked i5-6600K CPU @ 3.5 GHz, the code was compiled utilizing g++ below Home windows Subsystem for Linux, and every enter was run 10 occasions. After that, I took the imply of the outcomes for every drawback and put all of them right into a boxplot. Since I’m a proponent of LTO builds, I additionally compiled the entire thing, together with MiniSat, with LTO enabled, after which benchmarked the binary.
These are the outcomes:
As you’ll be able to see, the LTO construct carried out considerably higher, however not considerably so. What’s fascinating, is that the variety of outliers above the field, and the relative lengths of the whiskers, recommend that the underlying distribution of solver’s working time over the entire inputs is heavy-tailed. Because of this the longest-running inputs will want considerably longer to be solved than the others, and it’s a frequent attribute of solvers for NP-complete issues. It’s because a single fallacious resolution throughout the seek for an answer can lengthen the overall runtime considerably.
There’s yet another query to reply, specifically, how does this efficiency evaluate with high-performance Sudoku-specialized solvers? I picked 2, ZSolver and fsss2, and tried working them on the identical set of issues. Not too surprisingly, they each outperformed our SAT-based solver badly. The type of “changing” solver we wrote will at all times be slower than a well-tuned specialised solver, however they do have some benefits that may make them fascinating. For instance, I’ve no prior domain-specific data about fixing Sudokus, however I used to be in a position to write the SAT-based Sudoku solver in lower than 2 hours. Additionally it is far more readable and extendable.
That’s all for half 1, however I’ve far more I need to say about SAT solvers, so you’ll be able to anticipate extra posts about each utilizing them, and about their internals and the idea behind why are they so quick.
There are extra benchmarks in part 1.5, and part 2 shows how to implement a SAT-based solver for master-key systems.