另一種方法是使用SatisfiabilityInstances
,約束指定每行和每列必須是有效的單詞。下面的代碼需要40秒才能獲得使用200個三字母詞典的前5個解決方案。您可以用SatisfiabilityCount
替換SatisfiabilityInstances
以獲得這些填字遊戲的數量。
setupCrossword[wordStrings_] := (
m = Length[chars];
words = Characters /@ wordStrings;
chars = [email protected]@words;
wordMatch[vars_, word_] := And @@ (Thread[{vars, word}]);
validWord[vars_] := Or @@ (wordMatch[vars, #] & /@ words);
validCell[{i_, j_}] :=
BooleanCountingFunction[{1}, {{i, j}, #} & /@ chars];
row[i_] := {i, #} & /@ Range[n];
col[i_] := {#, i} & /@ Range[n];
cells = Flatten[row /@ Range[n], 1];
rowCons = validWord[row[#]] & /@ Range[n];
colCons = validWord[col[#]] & /@ Range[n];
cellCons = validCell /@ cells;
formula = And @@ (Join[rowCons, colCons, cellCons]);
vars =
Table[{{i, j}, c}, {i, 1, n}, {j, 1, n}, {c, chars}] //
Flatten[#, 2] &;
decodeInstance[instance_] := (
choices = Extract[vars, Position[instance, True]];
grid = Table[{i, j}, {i, 1, n}, {j, 1, n}] /. Rule @@@ choices
)
);
n = 3;
wordLimit = 200;
wordStrings =
Select[DictionaryLookup[],
StringLength[#] == n && LowerCaseQ[#] &];
setupCrossword[wordStrings[[;; wordLimit]]];
vals = SatisfiabilityInstances[formula, vars, 5];
[email protected]@[email protected]# & /@ vals
http://yaroslavvb.com/upload/save/crosswords.png
這種方法使用變量,如{{i,j},"c"}
指示細胞{i,j}
得到字母 「C」。每個單元格受約束只能得到一個字母BooleanCountingFunction
,每行和每列都被約束成一個有效的單詞。例如,約束第一行必須是「王牌」或「 - 」看起來像這樣
{{1,1},"a"}&&{{1,2},"c"}&&{{1,3},"e"}||{{1,1},"b"}&&{{1,2},"a"}&&{{1,3},"r"}
感謝您的努力!我以前從來沒有使用過** SatisfiabilityInstances **,雖然我看到你在過去發佈的那些很好的四面體問題中使用過它。我想這一個會花一些時間來咀嚼:D – 2011-02-01 22:58:38
好主意!我認爲模式匹配是一個死路一條:即使在調度表中,我也無法檢查每秒超過一百萬的候選人 - 這意味着整個問題超過一個小時。 – Janus 2011-02-02 04:06:07