2013年11月21日木曜日

制約論理プログラミングで数独を解く

GNU Prolog制約論理プログラミングで数独を解くプログラムを作ったところ、ほぼ数独のルールを記述するだけで出来てしまいました。

まずGNU Prologをインストールします。上のGNU Prologのサイトからソースをダウンロードしてインストールします。以下は1.4.4の場合です。

 $ tar zxf gprolog-1.4.4.tar.gz
 $ cd gprolog-1.4.4/src
 $ ./configure
 $ make
 $ sudo make install

次に以下のプログラム、


sudoku(Rows) :-
    Rows = [ % 引数の各行のリストをX11〜X99の変数に分解
        [X11, X12, X13, X14, X15, X16, X17, X18, X19],
        [X21, X22, X23, X24, X25, X26, X27, X28, X29],
        [X31, X32, X33, X34, X35, X36, X37, X38, X39],
        [X41, X42, X43, X44, X45, X46, X47, X48, X49],
        [X51, X52, X53, X54, X55, X56, X57, X58, X59],
        [X61, X62, X63, X64, X65, X66, X67, X68, X69],
        [X71, X72, X73, X74, X75, X76, X77, X78, X79],
        [X81, X82, X83, X84, X85, X86, X87, X88, X89],
        [X91, X92, X93, X94, X95, X96, X97, X98, X99]
    ],
    maplist(seigen, Rows), % 各行について値を制限

    Cols = [    % Colsを各列のリストとして定義
        [X11, X21, X31, X41, X51, X61, X71, X81, X91],
        [X12, X22, X32, X42, X52, X62, X72, X82, X92],
        [X13, X23, X33, X43, X53, X63, X73, X83, X93],
        [X14, X24, X34, X44, X54, X64, X74, X84, X94],
        [X15, X25, X35, X45, X55, X65, X75, X85, X95],
        [X16, X26, X36, X46, X56, X66, X76, X86, X96],
        [X17, X27, X37, X47, X57, X67, X77, X87, X97],
        [X18, X28, X38, X48, X58, X68, X78, X88, X98],
        [X19, X29, X39, X49, X59, X69, X79, X89, X99]
    ],
    maplist(seigen, Cols), % 各列について値を制限

    Blks = [ % Blksを各ブロックのリストとして定義
        [X11, X12, X13, X21, X22, X23, X31, X32, X33],
        [X14, X15, X16, X24, X25, X26, X34, X35, X36],
        [X17, X18, X19, X27, X28, X29, X37, X38, X39],
        [X41, X42, X43, X51, X52, X53, X61, X62, X63],
        [X44, X45, X46, X54, X55, X56, X64, X65, X66],
        [X47, X48, X49, X57, X58, X59, X67, X68, X69],
        [X71, X72, X73, X81, X82, X83, X91, X92, X93],
        [X74, X75, X76, X84, X85, X86, X94, X95, X96],
        [X77, X78, X79, X87, X88, X89, X97, X98, X99]
    ],
    maplist(seigen, Blks), % 各ブロックについて値を制限

    maplist(fd_labeling, Rows). % 各行の値を探索

% リストXの各値の取る値は1から9で、重複なし
seigen(X) :- fd_domain(X,1,9), fd_all_different(X).


をファイル(sudoku.pl)に保存して、以下のようにprologを起動します。

 $ gprolog --consult-file sudoku.pl

プロンプト(?-)が表示されたところで、以下のように問題データをセットして呼び出します。


Row1 = [8, _, _, _, _, _, _, _, _],
Row2 = [_, _, 3, 6, _, _, _, _, _],
Row3 = [_, 7, _, _, 9, _, 2, _, _],
Row4 = [_, 5, _, _, _, 7, _, _, _],
Row5 = [_, _, _, _, 4, 5, 7, _, _],
Row6 = [_, _, _, 1, _, _, _, 3, _],
Row7 = [_, _, 1, _, _, _, _, 6, 8],
Row8 = [_, _, 8, 5, _, _, _, 1, _],
Row9 = [_, 9, _, _, _, _, 4, _, _],
sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).


多分、瞬殺で解答が返ってくると思います。問題はこちらのサイトから世界一難しい数独問題を拝借しました。


Row1 = [8,1,2,7,5,3,6,4,9]
Row2 = [9,4,3,6,8,2,1,7,5]
Row3 = [6,7,5,4,9,1,2,8,3]
Row4 = [1,5,4,2,3,7,8,9,6]
Row5 = [3,6,9,8,4,5,7,2,1]
Row6 = [2,8,7,1,6,9,5,3,4]
Row7 = [5,2,1,9,7,4,3,6,8]
Row8 = [4,3,8,5,2,6,9,1,7]
Row9 = [7,9,6,3,1,8,4,5,2] ?


プログラム、というかルール記述は至って単純で、
 Rows = [[X11, ... , X19], ... [X91, ... , X99],
で引数で渡されたRowsの各行を変数X11〜X99に分解、
 maplist(seigen, Rows),
で数独による各行の値のルールを指定しています。maplistは2つ目の引数のリストの各要素について1つ目の引数の関数(Prologでは通常は関数と呼ばないようですが)を呼び出します。Rowsの各行についてseigenを呼び出していますが、これは最後の行で以下のように定義されています。
 seigen(X) :- fd_domain(X,1,9), fd_all_different(X).
fd_domainで各要素の値の取りうる値を1から9に制限し、fd_all_differentで各要素で重複する値を持つことがない、としています。
 Cols = [...

 Blks = [...
で各列と各ブロックのリストを構成する変数を定義し、同じようにseigenを呼び出しています。

以上、ここまでは文字通り数独のルール記述だけになっています。

 maplist(fd_labeling, Rows).

この行で各行のリストの持つ変数、すなわちX11〜X99すべてについて探索開始を指示しています。

問題を設定するところでわざわざRows1〜Rows9のリストとしているのは、結果の表示を見やすくするためです。

こんなに簡単にいけると思わかなった。。。

2013/11/21追記
 
以下が私の考える最短ソース。ここまで行くとProlog読めないと意味不明。
https://github.com/minetosh/sudoku/tree/master/prolog


sudoku(Rows) :-
    maplist(seigen, Rows), cols(Rows), blks(Rows),
    maplist(fd_labeling, Rows).

cols([[]|L]).
cols(L) :-
    maplist(nth(1), L, X), seigen(X), maplist(delete, L, X, NL), cols(NL).

blks([]).
blks([X, Y, Z|L]) :- blks2(X, Y, Z), blks(L).

blks2([],_,_).
blks2([X1, X2, X3|XL], [Y1, Y2, Y3|YL], [Z1, Z2, Z3|ZL]) :-
    seigen([X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3]), blks2(XL, YL, ZL).

seigen(X) :- fd_domain(X, 1, 9), fd_all_different(X).

2013年11月9日土曜日

Linuxで一つのネットワークインターフェースに複数IPアドレス設定する方法

CentOS6から複数IPアドレス設定の方法か変わったらしい、件で書いた、IPエイリアスを使わない方法はUbuntuでも行けました。しかもGUI上一つしか設定できないように見える8.04で。



# ip addr add 192.168.224.132/24 dev eth0

で設定できて、pingが通りました。ifconfigではやっぱり出て来ません。

全部試したわけじゃないけど、きっとLinux共通なんでしょーねー。
自分が知らなかっただけか。