Namaran

Code daily. Without assist.

2026-10-06

solver.cpp

#include <algorithm>
#include <cstdlib>
#include <print>
#include <vector>

bool solve(const std::vector<std::vector<int>>& cnf, std::vector<int>& val, int var) {
    for (const auto& clause : cnf)
        if (std::ranges::all_of(clause, [&](int lit) { return val[std::abs(lit)] * lit < 0; }))
            return false;
    if (var == std::ssize(val)) return true;
    for (int v : {1, -1}) {
        val[var] = v;
        if (solve(cnf, val, var + 1)) return true;
    }
    return false;
}

int main() {
    std::vector<int> val(3);
    std::println("{}", solve({{1, 2}, {-1, -2}, {-1, 2}}, val, 1));
}

solve は、変数 x1, x2, … に真(1)と偽(-1)を順に割り当て、CNFの論理式を満たす組を探すつもりの関数です。val の添字は変数の番号で、まだ決めていない変数の値は 0 です。どれかの節のリテラルがすべて偽になった時点で、その枝を打ち切ります。引数も標準入力も使わず、式は (x1 ∨ x2) ∧ (¬x1 ∨ ¬x2) ∧ (¬x1 ∨ x2) です。いまは false が出ます。x1 を偽、x2 を真にすれば満たせるので、本来は true が出るはずです。

Answer

Wrong

    for (int v : {1, -1}) {
        val[var] = v;
        if (solve(cnf, val, var + 1)) return true;
    }
    return false;

x1 を真にした枝では、x2 を真にすると (¬x1 ∨ ¬x2) が、偽にすると (¬x1 ∨ x2) が偽になり、どちらも打ち切られます。この solve(cnf, val, 2) は false を返しますが、val[2] は最後に試した -1 のまま残ります。

呼び出し元に戻って x1 を偽にし、solve(cnf, val, 2) を呼び直すと、関数の先頭の枝刈りが、まだ決めていないはずの x2 を読みます。val は参照で共有されているので、そこには前の枝の -1 が残っています。x1 も x2 も偽と見なされて (x1 ∨ x2) が偽になり、x2 を試す前にこの枝も打ち切られます。満たせる式なのに、false が返ります。

Right

    for (int v : {1, -1}) {
        val[var] = v;
        if (solve(cnf, val, var + 1)) return true;
    }
    val[var] = 0;
    return false;

どちらの値でも失敗したら、戻る前に val[var] を 0 に戻します。これで solve(cnf, val, var) が呼ばれた時点では、var 以降の変数が必ず未定になり、枝刈りが読むのはいまの枝で決めた値だけです。x1 を偽にした枝で x2 を真にした割り当てまで進み、true が返ります1。

  1. val を値渡しにして枝ごとに複製しても直りますが、呼び出しのたびに配列を写すことになります。共有した状態を、戻るときに元に戻すのがバックトラックでよく使う形です。