2026-09-08
Dpll.hs
type Clause = [Int]
assign :: Int -> [Clause] -> [Clause]
assign l = map (filter (/= negate l)) . filter (notElem l)
solve :: [Clause] -> [[Int]]
solve [] = [[]]
solve cs@((v : _) : _) =
[l : ls | l <- [v, negate v], ls <- solve (assign l cs)]
solve _ = []
main :: IO ()
main = print (solve [[-1, 2], [1, 3], [2, 3]])
これは何を出力するでしょうか?
Answer
[[-1,3],[1,2]] です。
節は整数のリストで、k は k 番目の変数 xk が真、-k は偽を表すリテラルです。solve は、論理式を満たす割り当てを、真にしたリテラルの列として並べて返します。最初の節の先頭のリテラル v を選び、v を真にする場合と negate v を真にする場合をこの順に試します。assign l は、l を含む節を満たされたものとして取り除き、残った節から l の否定を消します。
最初の節は [-1, 2] なので v は -1 で、先に試すのは x1 を偽にする枝です。assign (-1) で [-1, 2] が消え、残りの節から 1 が消えて [[3], [2, 3]] になります。ここで 3 を真にすると節がすべて消えて solve [] に着き、[[]] が返ります。-3 の枝では [3] から 3 が消えて空の節が先頭に来るので、solve _ = [] が解なしを返します。この枝で得られる解は [-1,3] の1つです。
あとから試す x1 を真にする枝では、[[2], [2, 3]] が残ります。2 を真にすると節が尽きて [1,2] が得られ、-2 の枝は空の節が生じて解がありません。
この論理式を満たす x1, x2, x3 の真偽の組は4つありますが、出力されるのは2つです。solve [] が [[]] を返すのは、節が尽きた時点で残りの変数はどちらでもよいからで、[-1,3] の x2 と [1,2] の x3 は割り当てられないまま解になります。[[]] は「何も決めなくてよい解が1つある」、[] は「解がない」で、ここを取り違えて solve [] = [] と書くと、どの枝からも解が返らなくなります。