RSS

 

RSS


パ:scip情報

  • いわいまさか
  • at 2014/7/02 23:00:00

最近、パズルをプログラムで解いている。

ソルバー(といわれるもの)に興味を持ち、ガサガサとネット中を検索して。

数独、お絵かき19(いわいオリジナル)、シャカシャカが解けるところまでできた。

ネットの中をガサガサ検索したわけで、
scip    の他に調べたもの
sugar    という総合的な制約ソルバー
sat     充足可能性問題ソルバー
(用語の指し示す範囲がばらついているので注意)

今出来ているのは、

scipは整数計画ソルバーのひとつ。
scipのwindows版を取得できる。
http://scip.zib.de/

以下のPDFを参考に
数独など
http://www.is.titech.ac.jp/~okamoto/PDF/2007/puzzleip.pdf
シャカシャカ
http://www.alg.cei.uec.ac.jp/itohiro/Games/130301/130301-01.pdf


入力のフォーマットをLPということに決めて

そして、下のように、組みあげた。

全体の制御をC#で行い
パズル問題      -> C#   -> LPフォーマット問題
LPフォーマット問題 -> scip  -> 解答
解答          ->  C#   -> パズル解答
となるようにした。

・C#と書いてあるところはC#で書いたオリジナルのプログラム
・scipと書いてあるところはscipのexeそのまま(コマンドをうつ必要はあるが)

scipをインタフェースでC++から直接たたく方法もあって、それのサンプル(N-queen)を動かすところまでは試したみた。
LPを経由した方が「見とおしがよい」ので今はそれでやっている。



  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56096