推理パズルをSugar制約ソルバーで解く


はじめに

Nikoliによる 推理パズルを Sugar制約ソルバー (A SAT-based Constraint Solver)で解いてみます.

例題

Nikoliによる 推理パズルの例題 です.
例題
 
         
         
         
         
    
    
    
    
(ヒント1)
明は白いのを買ったが糸じゃない.
(ヒント2)
青い紙を買った人がいるが,勇じゃない.
(ヒント3)
正は靴を買ったが赤じゃない.
推理パズルを 制約充足問題(CSP, Constraint Satisfaction Problem)として表すための 方法について考えていきます.
****************作成中****************

実行結果

すべての制約を記述したファイルを作成し, Sugarで実行すると以下のような結果が得られます.
s SATISFIABLE
a akira	1
a isamu	2
a tadashi	3
a hiroshi	4
a kasa	1
a kutsu	3
a kami	4
a ito	2
a red	2
a blue	4
a white	1
a black	3
a

やっぱり,変数名を日本語で書きたいですね. 次のバージョンでは,以下のように日本語の変数名を使えるようにしたいと思います.

(domain d 1 4)
(int 明 1)
(int 勇 2)
(int 正 3)
(int 洋 4)
(int 傘 d)
(int 靴 d)
(int 紙 d)
(int 糸 d)
(alldifferent 傘 靴 紙 糸)
(int 赤 d)
(int 青 d)
(int 白 d)
(int 黒 d)
(alldifferent 赤 青 白 黒)
(predicate (買った x y) (= x y))
(買った 明 白)
(not (買った 明 糸))
(int 誰か d)
(買った 誰か 紙)
(買った 誰か 青)
(!= 誰か 勇)
(買った 正 靴)
(not (買った 正 赤))

なお,推理パズルについては, さすがに自動的にCSPを生成するプログラムは書けません...

「パズルをSugar制約ソルバーで解く」に戻る


Naoyuki Tamura
( Last modified: Fri Jul 11 02:12:31 2008 JST ,   ?????  Since June 4, 2008 )