2026-10-06
brute_sat.cpp
#include <algorithm>
#include <cstdlib>
#include <print>
#include <vector>
int main() {
std::vector<std::vector<int>> cnf = {{1, 2}, {-1, 3}, {-2, -3}};
for (unsigned m = 0; m < 8; ++m) {
bool sat = std::ranges::all_of(cnf, [m](const auto& clause) {
return std::ranges::any_of(clause, [m](int lit) {
return (m >> (std::abs(lit) - 1) & 1) == (lit > 0);
});
});
if (sat) std::println("{}", m);
}
}
これは何を出力するでしょうか?
Answer
2 と 5 の2行です。
cnf の内側の配列が節、整数がリテラルで、1 は変数 x1、-1 は x1 の否定を表します。式全体は (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) です。any_of は節の中に真のリテラルが1つでもあるかを、all_of はそれがすべての節で成り立つかを調べます。
変数の値は m のビットから取ります。x1 は最下位ビット、x2 はその1つ上、x3 はさらに1つ上です。m >> (std::abs(lit) - 1) & 1 で取り出したビットが lit > 0 と等しければ、そのリテラルは真です。正のリテラルはビットが1のとき、負のリテラルはビットが0のときに真になります。
x1 を真にすると、2番目の節から x3 も真でなければならず、3番目の節から x2 は偽になります。x1 と x3 のビットが立った 0b101 で、5 です。x1 を偽にすると、1番目の節から x2 が真になり、3番目の節から x3 は偽になります。こちらは 0b010 の 2 です。m を小さい順に調べるので、2 が先に出ます。