Prolog Programming

●ライツアウト

今回はパズル「ライツアウト」を clpfd を使って解いてみましょう。パズルの説明は拙作のページ Prolog 入門: 整数の論理演算とビット操作 や Puzzle DE Programming: ライツアウトの解法 をお読みください。

下記 URL によると、ライツアウトの解法は連立一次方程式を解くことに帰着させることができるそうです。

• 驚異のライツアウト解法ロジック, (高橋謙一郎さん)
• ライツアウト(３カラーパズル)の計算解法, (高橋謙一郎さん)
• ライツアウト ＆ ８めくりパズル, (deepgreen さん)

具体的にいうと、5 行 5 列盤 N 色のライツアウトの解は、次に示す 25 本の連立方程式を解くことで求めることができます。

(Xij-1 + Xi-1j + Xij + Xi+1j + Xij+1 + Aij) mod N = 0, 0 < i <= 5, 0 < j <= 5

X_ij はボタン (i, j) を押す回数、A_ij はボタン (i, j) の状態 (色) を表します。たとえば、N = 2 でボタン (i, j) が点灯 (1) している場合、自身のボタンと周囲のボタンを押す回数が奇数回であれば、それを消灯することができます。逆に、消灯している場合であれば、ボタンを押す回数が偶数回であれば消灯したままになります。

clpfd を使えば連立方程式をプログラムするだけで、N 色のライツアウトの解を求めることができます。5 行 5 列盤専用になりますが、プログラムは次のようになります。

リスト : ライツアウト (5 行 5 列盤) の解法

:- use_module(library(clpfd)).

make_list(0, _, []).
make_list(N, X, [X | Xs]) :-
    N > 0, N1 is N - 1, make_list(N1, X, Xs).

lo25(As, N, Xs) :-
    As = [A11, A12, A13, A14, A15,
          A21, A22, A23, A24, A25,
          A31, A32, A33, A34, A35,
          A41, A42, A43, A44, A45,
          A51, A52, A53, A54, A55],
    Xs = [X11, X12, X13, X14, X15,
          X21, X22, X23, X24, X25,
          X31, X32, X33, X34, X35,
          X41, X42, X43, X44, X45,
          X51, X52, X53, X54, X55],
    (      X11 + X12 + X21 + A11) mod N #= 0,
    (X11 + X12 + X13 + X22 + A12) mod N #= 0,
    (X12 + X13 + X14 + X23 + A13) mod N #= 0,
    (X13 + X14 + X15 + X24 + A14) mod N #= 0,
    (X14 + X15       + X25 + A15) mod N #= 0,

    (X11       + X21 + X22 + X31 + A21) mod N #= 0,
    (X12 + X21 + X22 + X23 + X32 + A22) mod N #= 0,
    (X13 + X22 + X23 + X24 + X33 + A23) mod N #= 0,
    (X14 + X23 + X24 + X25 + X34 + A24) mod N #= 0,
    (X15 + X24 + X25       + X35 + A25) mod N #= 0,

    (X21       + X31 + X32 + X41 + A31) mod N #= 0,
    (X22 + X31 + X32 + X33 + X42 + A32) mod N #= 0,
    (X23 + X32 + X33 + X34 + X43 + A33) mod N #= 0,
    (X24 + X33 + X34 + X35 + X44 + A34) mod N #= 0,
    (X25 + X34 + X35       + X45 + A35) mod N #= 0,

    (X31       + X41 + X42 + X51 + A41) mod N #= 0,
    (X32 + X41 + X42 + X43 + X52 + A42) mod N #= 0,
    (X33 + X42 + X43 + X44 + X53 + A43) mod N #= 0,
    (X34 + X43 + X44 + X45 + X54 + A44) mod N #= 0,
    (X35 + X44 + X45       + X55 + A45) mod N #= 0,

    (      X51 + X52 + X41 + A51) mod N #= 0,
    (X51 + X52 + X53 + X42 + A52) mod N #= 0,
    (X52 + X53 + X54 + X43 + A53) mod N #= 0,
    (X53 + X54 + X55 + X44 + A54) mod N #= 0,
    (X54 + X55       + X45 + A55) mod N #= 0,

    M is N - 1,
    Xs ins 0 .. M,
    label(Xs).

solver(N, As) :-
    lo25(As, N, Xs), write(Xs), sum_list(Xs, M), write(M), nl, fail.

プログラムは簡単なので説明は割愛します。それでは実際に試してみましょう。すべてのボタンの色が N - 1 の状態で、ライトを消灯する場合の解は次のようになります。

?- make_list(25, 1, As), solver(2, As).
[0,0,0,1,1,1,1,0,1,1,1,1,1,0,0,0,1,1,1,0,1,0,1,1,0]15
[0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0]15
[1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,0,0,1,1]15
[1,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,1]15
false.

?- make_list(25, 2, As), solver(3, As).
[0,0,0,2,2,1,1,2,0,0,2,0,1,0,2,1,0,1,1,2,1,2,1,0,2]24
[0,0,1,2,0,1,0,1,1,2,0,2,1,1,1,1,1,2,0,0,2,1,0,1,0]21
[0,0,2,2,1,1,2,0,2,1,1,1,1,2,0,1,2,0,2,1,0,0,2,2,1]27
[0,1,0,1,2,0,0,2,1,1,1,1,1,2,0,2,1,1,0,1,0,2,1,0,0]21
[0,1,1,1,0,0,2,1,2,0,2,0,1,0,2,2,2,2,2,2,1,1,0,1,1]27
[0,1,2,1,1,0,1,0,0,2,0,2,1,1,1,2,0,0,1,0,2,0,2,2,2]24
[0,2,0,0,2,2,2,2,2,2,0,2,1,1,1,0,2,1,2,0,2,2,1,0,1]30
[0,2,1,0,0,2,1,1,0,1,1,1,1,2,0,0,0,2,1,1,0,1,0,1,2]21
[0,2,2,0,1,2,0,0,1,0,2,0,1,0,2,0,1,0,0,2,1,0,2,2,0]21
[1,0,0,2,1,0,0,2,1,1,0,2,1,1,1,2,1,1,0,1,1,1,1,1,2]24
[1,0,1,2,2,0,2,1,2,0,1,1,1,2,0,2,2,2,2,2,2,0,0,2,0]30
[1,0,2,2,0,0,1,0,0,2,2,0,1,0,2,2,0,0,1,0,0,2,2,0,1]21
[1,1,0,1,1,2,2,2,2,2,2,0,1,0,2,0,2,1,2,0,0,1,1,1,0]27
[1,1,1,1,2,2,1,1,0,1,0,2,1,1,1,0,0,2,1,1,1,0,0,2,1]24
[1,1,2,1,0,2,0,0,1,0,1,1,1,2,0,0,1,0,0,2,2,2,2,0,2]24
[1,2,0,0,1,1,1,2,0,0,1,1,1,2,0,1,0,1,1,2,2,1,1,1,1]24
[1,2,1,0,2,1,0,1,1,2,2,0,1,0,2,1,1,2,0,0,0,0,0,2,2]24
[1,2,2,0,0,1,2,0,2,1,0,2,1,1,1,1,2,0,2,1,1,2,2,0,0]27
[2,0,0,2,0,2,2,2,2,2,1,1,1,2,0,0,2,1,2,0,1,0,1,2,2]30
[2,0,1,2,1,2,1,1,0,1,2,0,1,0,2,0,0,2,1,1,2,2,0,0,0]24
[2,0,2,2,2,2,0,0,1,0,0,2,1,1,1,0,1,0,0,2,0,1,2,1,1]24
[2,1,0,1,0,1,1,2,0,0,0,2,1,1,1,1,0,1,1,2,0,0,1,2,0]21
[2,1,1,1,1,1,0,1,1,2,1,1,1,2,0,1,1,2,0,0,1,2,0,0,1]24
[2,1,2,1,2,1,2,0,2,1,2,0,1,0,2,1,2,0,2,1,2,1,2,1,2]33
[2,2,0,0,0,0,0,2,1,1,2,0,1,0,2,2,1,1,0,1,2,0,1,2,1]24
[2,2,1,0,1,0,2,1,2,0,0,2,1,1,1,2,2,2,2,2,0,2,0,0,2]30
[2,2,2,0,2,0,1,0,0,2,1,1,1,2,0,2,0,0,1,0,1,1,2,1,0]24
false.

?- make_list(25, 3, As), solver(4, As).
[0,0,2,1,3,1,3,2,3,1,1,3,3,2,2,0,3,3,3,0,1,0,1,1,0]39
[0,1,1,0,1,0,3,3,3,0,2,2,3,3,1,1,3,2,3,1,3,1,2,0,0]39
[0,2,0,3,3,3,3,0,3,3,3,1,3,0,0,2,3,1,3,2,1,2,3,3,0]47
[0,3,3,2,1,2,3,1,3,2,0,0,3,1,3,3,3,0,3,3,3,3,0,2,0]47
[1,0,1,1,0,0,3,3,3,0,1,3,3,2,2,1,3,2,3,1,0,0,2,1,3]39
[1,1,0,0,2,3,3,0,3,3,2,2,3,3,1,2,3,1,3,2,2,1,3,0,3]47
[1,2,3,3,0,2,3,1,3,2,3,1,3,0,0,3,3,0,3,3,0,2,0,3,3]47
[1,3,2,2,2,1,3,2,3,1,0,0,3,1,3,0,3,3,3,0,2,3,1,2,3]47
[2,0,0,1,1,3,3,0,3,3,1,3,3,2,2,2,3,1,3,2,3,0,3,1,2]47
[2,1,3,0,3,2,3,1,3,2,2,2,3,3,1,3,3,0,3,3,1,1,0,0,2]47
[2,2,2,3,1,1,3,2,3,1,3,1,3,0,0,0,3,3,3,0,3,2,1,3,2]47
[2,3,1,2,3,0,3,3,3,0,0,0,3,1,3,1,3,2,3,1,1,3,2,2,2]47
[3,0,3,1,2,2,3,1,3,2,1,3,3,2,2,3,3,0,3,3,2,0,0,1,1]47
[3,1,2,0,0,1,3,2,3,1,2,2,3,3,1,0,3,3,3,0,0,1,1,0,1]39
[3,2,1,3,2,0,3,3,3,0,3,1,3,0,0,1,3,2,3,1,2,2,2,3,1]47
[3,3,0,2,0,3,3,0,3,3,0,0,3,1,3,2,3,1,3,2,0,3,3,2,1]47
false.

解が存在する場合、その総数は 2 色で 4 通り、3 色で 27 通り、4 色で 16 通りあります。なお、色数を増やすと実行時間がかかることに注意してください。

●m 行 n 列盤の解法

次は、ライトの状態を消灯・点灯に限定して、盤面の大きさを変更してみましょう。この場合、連立方程式を生成するプログラムを作ったほうが簡単です。次のリストを見てください。

リスト : ライツアウト (m 行 n 列盤) の解法

:- use_module(library(clpfd)).

% 要素が X で個数が N のリストを生成する
make_list(0, _, []).
make_list(N, X, [X | Xs]) :-
    N > 0, N1 is N - 1, make_list(N1, X, Xs).

% 反転するボタンの位置を求める
reverse_buttons(_, _, _, _, [], []).
reverse_buttons(X, Y, L, C, [[Dx, Dy] | Ds], [Z | Zs]) :-
    X1 is X + Dx,
    Y1 is Y + Dy,
    X1 >= 0,
    X1 < C,
    Y1 >= 0,
    Y1 < L,
    Z is Y1 * C + X1,
    !,
    reverse_buttons(X, Y, L, C, Ds, Zs).
reverse_buttons(X, Y, L, C, [_ | Ds1], Zs) :- reverse_buttons(X, Y, L, C, Ds1, Zs).

% 式を組み立てる
make_expr(_, A, [], N) :- (N + A) mod 2 #= 0.
make_expr(Xs, A, [I | Is], N) :-
    nth0(I, Xs, V),
    N1 #= N + V,
    make_expr(Xs, A, Is, N1).

make_expr(Xs, A, [I | Is]) :-
    nth0(I, Xs, V),
    make_expr(Xs, A, Is, V).

% 規則 (連立方程式) を設定する
make_rule(N, L, C, _, _, _) :- N =:= L * C.
make_rule(N, L, C, Ds, Xs, [A | As]) :-
    X is N mod C,
    Y is N // C,
    reverse_buttons(X, Y, L, C, Ds, Is),
    make_expr(Xs, A, Is),
    N1 is N + 1,
    make_rule(N1, L, C, Ds, Xs, As).

% ライツアウトの解法
lo(L, C, As, Xs) :-
    K is L * C,
    length(Xs, K),
    make_rule(0, L, C, [[0,-1],[-1,0],[0,0],[1,0],[0,1]], Xs, As),
    Xs ins 0..1,
    label(Xs).

solver_lo(L,C) :-
    K is L * C,
    make_list(K, 1, Xs),
    lo(L, C, Xs, As),
    sum_list(As, N),
    write(As),
    write(N),
    nl,
    fail.

ライツアウトの解法は述語 lo(L, C, Xs, As) で行います。L が行数 (lines)、C が列数 (columns) です。Xs はボタンを表す変数を格納したリスト、As がボタンの状態 (0 or 1) を格納したリストです。最初に length で K 個の変数を生成し、述語 make_rule で連立方程式を設定します。第 4 引数はボタン (X, Y) と反転するボタンの差分を格納したリストです。差分から反転するボタンの位置を述語 reverse_buttons で求めます。そして、述語 make_expr でボタン (X, Y) の式を生成します。最後の solver_lo はすべてのボタンが点灯している状態の解を求める述語です。

それでは実際に試してみましょう。

?- solver_lo(3, 3).
[1,0,1,0,1,0,1,0,1]5
false.

?- solver_lo(4, 4).
[0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1]10
[0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1]6
[0,0,1,0,1,0,0,0,0,0,0,1,0,1,0,0]4
[0,0,1,1,1,0,1,1,0,1,0,0,1,0,1,0]8
[0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0]4
[0,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0]8
[0,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1]6
[0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1]10
[1,0,0,0,0,0,1,1,0,0,1,1,1,0,0,0]6
[1,0,0,1,0,0,0,0,0,1,1,0,0,1,1,0]6
[1,0,1,0,0,1,0,0,1,0,1,1,0,0,1,1]8
[1,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1]12
[1,1,0,0,1,1,0,1,0,0,1,0,0,1,0,1]8
[1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1]12
[1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0]10
[1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,0]10
false.

?- solver_lo(5, 5).
[0,0,0,1,1,1,1,0,1,1,1,1,1,0,0,0,1,1,1,0,1,0,1,1,0]15
[0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0]15
[1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,0,0,1,1]15
[1,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,1]15
false.

?- solver_lo(6, 6).
[1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,1]28
false.

?- solver_lo(7, 7).
[1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,0,1,0,0,1,0,0,1,0,1,1,0,1,1,0,1,
 1,1,0,1,1,1,1,1,0,1,0,1,1]33
false.

?- solver_lo(8, 8).
[1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,0,0,1,1,1,
 1,1,1,0,0,0,1,1,1,1,0,0,1,1,0,1,1,0,1,1,1,1,0,0,0,0,1,1]40
false.

?-

日月離反 - atobirabon によると、『どんなm×nライツアウトも，すべてのライトがonのときは必ず解ける．』 とのことです。ライツアウトの数学的な解析を公開されている作者様に感謝いたします。また、解が一つしかない場合はライトがどんなパターンでも解くことができ、複数ある場合は解けないパターンが存在します。たとえば 4 行 4 列盤の場合、パターンの総数は 2¹⁶ 通りありますが、16 通りの複数解があるので、解けるパターンは 65536 / 16 = 4096 通りしかありません。

なお、盤のサイズを大きくすると時間がかかるようになります。clpfd を使うと簡単にプログラムできますが、今回のプログラムの実行速度は遅いです。ご注意くださいませ。

●反転パターンの変更

次は拙作のページ Puzzle DE Programming: 変形版「ライツアウト」 で取り上げた、反転パターンを X にしてみましょう。プログラムは簡単です。次のリストを見てください。

リスト : 変形版ライツアウト

xlo(L, C, As, Xs) :-
    K is L * C,
    length(Xs, K),
    make_rule(0, L, C, [[-1,-1],[1,-1],[0,0],[-1,1],[1,1]], Xs, As),
    Xs ins 0..1,
    label(Xs).

solver_xlo(L,C) :-
    K is L * C,
    make_list(K, 1, Xs),
    xlo(L, C, Xs, As),
    sum_list(As, N),
    write(As),
    write(N),
    nl,
    fail.

述語 xlo で make_rule を呼び出すとき、反転するボタンの位置を X の形に修正するだけです。それでは実行してみましょう。

?- solver_xlo(3, 3).
[0,1,0,1,1,1,0,1,0]5
false.

?- solver_xlo(4, 4).
[0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,0]8
[0,0,0,1,1,1,0,0,1,0,1,0,1,1,1,0]8
[0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0]8
[0,0,1,1,1,1,0,1,0,0,1,0,1,0,1,0]8
[0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0]8
[0,1,0,1,0,1,0,0,1,0,1,1,1,1,0,0]8
[0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,0]8
[0,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0]8
[1,0,0,0,0,0,1,1,0,1,0,1,0,1,1,1]8
[1,0,0,1,1,0,0,1,0,0,0,0,1,1,1,1]8
[1,0,1,0,0,0,1,0,1,1,0,1,0,0,1,1]8
[1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1]8
[1,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1]8
[1,1,0,1,0,0,0,1,0,0,0,1,1,1,0,1]8
[1,1,1,0,1,0,1,0,1,1,0,0,0,0,0,1]8
[1,1,1,1,0,0,0,0,1,0,0,1,1,0,0,1]8
false.

?- solver_xlo(5, 5).
[0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,0,0,0,0,0,0,1]11
[0,0,0,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,0,1]11
[0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,0,0,1,0,0,1,0,1,0,1]11
[0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1]11
[0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,0,0,0,0,0,0,1,1]11
[0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1]19
[0,1,1,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,0,0,1,0,1,1,1]11
[0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,1]19
[1,0,0,0,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,0,0,0]11
[1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,1,1,1,0,0,0]11
[1,0,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,0,0,1,0,0]11
[1,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0]11
[1,1,0,0,0,0,0,0,1,1,1,0,1,0,1,1,0,0,1,0,1,0,0,1,0]11
[1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0]19
[1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,1,0,0,0,1,1,0]11
[1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0]19
false.

?- solver_xlo(6, 6).
[0,0,1,1,0,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,0,0,0,1,1,0,0]20
false.

?- solver_xlo(7, 7).
[1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,
 0,1,1,1,0,1,1,1,0,1,0,1,1]33
false.

?- solver_xlo(8, 8).
[0,0,1,0,0,1,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,1,
 1,1,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]34
[0,1,1,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,1,0,1,1,0,
 1,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,1]34
[1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,1,1,
 0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,0,1,1,1,0]34
[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,
 0,1,1,1,1,0,0,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,0,0,1,0,0]34
false.

?-

5 行 5 列盤の場合、変形版「ライツアウト」 の解析では、最長手数が 13 手で、解けるパターンは 2²⁵ / 16 = 2097152 通りありました。解が 16 通り見つかったので、この解析結果と一致しています。盤面のサイズを変えて試してみたところ、全点灯のパターンは解けるようですね。ただし、証明はしていないので、必ず解けると断定することはできません。興味のある方は証明にも挑戦してみてください。

●８めくりパズル

「８めくり」はライツアウトに類似のパズルです。ルールは簡単で、あるボタンを押すと周囲のボタンの状態が反転します。つまり、光っているボタンは消灯し、消えていたボタンは点灯します。次の図を見てください。

                      図 : 反転パターン

中央のボタン 4 を押すと、その周囲のボタン 8 個の状態が反転します。押したボタンの状態は反転しません。もう一度同じボタンを押すと、再度ボタンの状態が反転するので、元の状態に戻ります。隅のボタン 0 を押すと 3 個のボタンの状態が反転し、辺にあるボタン 1 を押すと 5 個のボタンの状態が反転します。

８めくりの解法プログラムも簡単に作ることができます。プログラムと実行結果を示します。

 リスト : ８めくりパズルの解法

turnover(L, C, As, Xs) :-
    K is L * C,
    length(Xs, K),
    make_rule(0, L, C, [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]], Xs, As),
    Xs ins 0..1,
    label(Xs).

solver_turnover(L,C) :-
    K is L * C,
    make_list(K, 1, Xs),
    turnover(L, C, Xs, As),
    sum_list(As, N),
    write(As),
    write(N),
    nl,
    fail.

?- solver_turnover(4, 4).
[0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1]6
[0,0,0,1,0,1,0,1,0,0,1,1,1,1,1,0]8
[0,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0]8
[0,0,1,1,1,0,1,1,1,0,1,1,0,0,1,1]10
[0,1,0,0,1,1,1,0,0,1,1,1,0,0,1,0]8
[0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1]6
[0,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1]10
[0,1,1,1,1,1,0,0,1,0,1,0,1,0,0,0]8
[1,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1]8
[1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0]6
[1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0]6
[1,0,1,1,1,0,0,0,0,0,0,1,1,1,0,1]8
[1,1,0,0,1,1,0,1,1,1,0,1,1,1,0,0]10
[1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1]8
[1,1,1,0,0,0,1,1,0,1,0,1,0,0,0,1]8
[1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,0]10
false.

?- solver_turnover(5, 5).
false.

?- solver_turnover(6, 6).
[1,0,0,0,0,1,
 0,1,1,1,1,0,
 0,1,0,0,1,0,
 0,1,0,0,1,0,
 0,1,1,1,1,0,
 1,0,0,0,0,1]16
false.

?- solver_turnover(7, 7).
false.

?- solver_turnover(8, 8).
[0,1,1,0,0,1,1,0,
 1,1,0,1,1,0,1,1,
 1,0,1,0,0,1,0,1,
 0,1,0,0,0,0,1,0,
 0,1,0,0,0,0,1,0,
 1,0,1,0,0,1,0,1,
 1,1,0,1,1,0,1,1,
 0,1,1,0,0,1,1,0]32
false.

?- solver_turnover(9, 9).
false.

?- solver_turnover(10, 10).
[1,0,1,1,1,1,1,1,0,1,
 0,1,0,1,0,0,1,0,1,0,
 1,0,0,1,1,1,1,0,0,1,
 1,1,1,0,0,0,0,1,1,1,
 1,0,1,0,1,1,0,1,0,1,
 1,0,1,0,1,1,0,1,0,1,
 1,1,1,0,0,0,0,1,1,1,
 1,0,0,1,1,1,1,0,0,1,
 0,1,0,1,0,0,1,0,1,0,
 1,0,1,1,1,1,1,1,0,1]60
false.

6 * 6 盤, 8 * 8 盤, 10 * 10 盤の結果は手作業で整形しています。ライツアウトと違って、盤のサイズによっては全点灯パターンが解けないこともあります。興味のある方はいろいろ試してみてください。

ところで、拙作のページ Scheme Programming: パズルに挑戦 ８めくりの解答 で最長手数を求めたことがあります。4 * 4 盤の場合、最長手数は 7 手で、局面の総数は全部のボタンが消灯した状態を含めて 4096 通りになりました。全局面の 1 / 16 しかありません。4 * 6 盤の場合、最長手数は 24 手で、全局面数は 2 ^ 24 = 16777216 通りになります。5 * 5 盤の場合、全消灯に到達できる局面は 2 ^ 25 / 2 = 16777216 通りあり、その中で最長手数は 20 手 (126 通り) になります。

なお、盤面のサイズを大きくすると、clpfd では時間がかかるようになります。deepgreen さん が作成されたプログラム (turnover3.exe) を使うと、32 * 32 盤でも 94 msec (Windows 10, Intel Core i5-6200U 2.30GHz) で解くことができます。ソースコードも公開されているので、興味のある方は deepgreen さんの Web ページをお読みください。deepgreen さんに感謝いたします。

●タクシー数

笹川さんの twitter に触発されて、M.Hiroi もタクシー数を求めるプログラムを書いてみました。タクシー数の説明は、拙作のページ Puzzle DE Programming: タクシー数 をお読みください。ここでは問題を簡単にして、次式を満たす異なる整数 a, b, c, d を列挙することにします。

a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 (= x)

x が昇順になるように出力する場合、SWI-Prolog の CLPFD を使うと簡単です。

?- use_module(library(clpfd)).
true.

?- A^3 + B^3 #= X, C^3 + D^3 #= X,
|    A #< B, C #< D, A #< C, D #< B,
|    [A, B, C, D] ins 1 .. 50,
|    labeling([min(X)], [A, B, C, D]),
|    write([X, A, B, C, D]),
|    nl,
|    fail.
[1729,1,12,9,10]
[4104,2,16,9,15]
[13832,2,24,18,20]
[20683,10,27,19,24]
[32832,4,32,18,30]
[39312,2,34,15,33]
[40033,9,34,16,33]
[46683,3,36,27,30]
[64232,17,39,26,36]
[65728,12,40,31,33]
[110656,4,48,36,40]
[110808,6,48,27,45]
false.

?-

labeling で min(X) を指定することで、最初に X が最小となる解を求めることができます。逆に、max(X) を指定すると最大値の解を求めることができます。このように簡単にプログラムできるのですが、SWI-Prolog の CLPFD は遅いので、ちょっと時間がかかるのが欠点です。他の処理系では、高速に解を求めることができるかもしれません。興味のある方は試してみてください。

ところで、整数 a, b, c, d の範囲を 1 から N として、条件を満たすものを列挙するだけでよければ、プログラムはぐっと簡単になります。たとえば、Prolog では次のようになります。

リスト : タクシー数

product(N, [X, A, B]) :-
    between(1, N, A),
    A1 is A + 1,
    between(A1, N, B),
    X is A ^ 3 + B ^ 3.

solver(N) :-
    assert(taxi(0 ,0, 0)),
    retractall(taxi(X, A, B)),
    product(N, [X, A, B]),
    assert(taxi(X, A, B)),
    findall([C, D], taxi(X, C, D), Zs),
    length(Zs, 2),
    write([X, Zs]),
    nl,
    fail.

product() で整数の組を生成し、assert() でそれと三乗和を記憶します。そして、findall() で三乗和 X と等しい整数の組を求め、それが 2 つあれば write() で出力します。とても簡単ですね。

それでは実際に試してみましょう。

?- solver(50).
[1729,[[1,12],[9,10]]]
[4104,[[2,16],[9,15]]]
[39312,[[2,34],[15,33]]]
[40033,[[9,34],[16,33]]]
[13832,[[2,24],[18,20]]]
[32832,[[4,32],[18,30]]]
[20683,[[10,27],[19,24]]]
[64232,[[17,39],[26,36]]]
[46683,[[3,36],[27,30]]]
[110808,[[6,48],[27,45]]]
[65728,[[12,40],[31,33]]]
[110656,[[4,48],[36,40]]]
false.

一瞬で 12 通りの解を求めることができました。solver(100) でも同様です。興味のある方は、いろいろなプログラミング言語で挑戦してみてください。