[Prolog]十字型にライトをスイッチしてすべてのライトを点けるパズル | Codetter（こーどったー）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
% 0 = 点灯(on), 1 = 消灯(off)とする。
% 解答として、すべて点灯させるためにスイッチすべきライトの成分のリストを返す。
% リスト・行列に関する諸述語
append( [], List, List ).
append( [Head|Tail], List, [Head|TailR] ) :- append(Tail, List, TailR).
at( [Head|Tail], 0, Head ).
at( [Head|Tail], Idx, Val ) :- number(Idx), Idx > 0, Idx1 is Idx - 1, at( Tail, Idx1, Val ).
at( [Head|Tail], (0, Y), Val ) :- at(Head, Y, Val).
at( [Head|Tail], (X, Y), Val ) :- X > 0, X1 is X - 1, at( Tail, (X1, Y), Val ).
reverse( [], [] ).
reverse( [Head|Tail], Reversed ) :- reverse( Tail, Remains ), append( Remains, [Head], Reversed ).
zero_list([]).
zero_list([0|Tail]) :- zero_list(Tail).
zero_matrix([]).
zero_matrix([Head|Tail]) :- zero_list(Head), zero_matrix(Tail).
between(L, L, R) :- L < R.
between(N, L, R) :- L < R, L1 is L + 1, between(N, L1, R).
% マンハッタン距離
abs( X, A ) :- number(X), X >= 0 -> A is X ; A is -X.
manhattan_distance( (Ax, Ay), (Bx, By), D ) :-
    X is Ax - Bx, abs( X, Dx ),
    Y is Ay - By, abs( Y, Dy ),
    D is Dx + Dy.
    
% 成分の順序 (辞書式順序)
positionLess( (X1, _), (X2, _) ) :- X1 < X2.
positionLess( (X, Y1), (X, Y2) ) :- Y1 < Y2.
% パズル
light_switch_pazzle( Q, A ) :- light_switch_pazzle( Q, A, (0, 1000) ).  % 省略引数
light_switch_pazzle( Q, A, (MinLv, MaxLv) ) :-
    length(Q, M), Q = [QHead|_], length(QHead, N),
    between(Limit, MinLv, MaxLv),       % 反復深化
%   write(Limit), nl,
    light_switch_pazzle_acc( (0, Limit), Q, (M, N), ARev, [] ),
    reverse(ARev, A).
    
light_switch_pazzle_acc( (Limit, Limit), Board, _, Path, Path ) :-
    zero_matrix(Board).
light_switch_pazzle_acc( (Lv, Limit), Board1, (M, N), A, Path ) :-
    Lv < Limit, Lv1 is Lv + 1,
    between(X, 0, M),
    between(Y, 0, N),
    ( Path = [] ; Path = [PrevPath|_], positionLess( PrevPath, (X, Y) ) ),  % 順番違いの解を排除 (成分列を単調増加に限定する)
    light_switch( Board1, Board2, (X, Y) ),
    light_switch_pazzle_acc( (Lv1, Limit), Board2, (M, N), A, [(X, Y)|Path] ).
% 成分(X, Y)および上下左右(マンハッタン距離1以下)がスイッチした行列
light_switch( Board1, Board2, (X, Y) ) :-
    light_switch_matrix_( Board1, Board2, (X, Y), (0, 0) ).
    
light_switch_matrix_( [], [], _, _ ).
light_switch_matrix_( [Head1|Tail1], [Head2|Tail2], Point, (X, 0) ) :-
    light_switch_list_( Head1, Head2, Point, (X, 0) ),
    X1 is X + 1,
    light_switch_matrix_( Tail1, Tail2, Point, (X1, 0) ).
    
light_switch_list_( [], [], _, _ ).
light_switch_list_( [Head1|Tail1], [Head2|Tail2], Point, (X, Y) ) :-
    manhattan_distance( Point, (X, Y), D ),
    ( D =< 1 -> Head2 is (1 - Head1); Head1 = Head2 ),
    Y1 is Y + 1,
    light_switch_list_( Tail1, Tail2, Point, (X, Y1) ).
% 例題
% 問題文で「最短4手」と明言されているので、実際は4手の解を探すだけで十分。
?- light_switch_pazzle( [
    [ 1, 0, 1, 1 ],
    [ 0, 0, 1, 0 ],
    [ 1, 1, 0, 1 ],
    [ 1, 0, 1, 1 ] ], Answer ).
/*
Answer:
[(0,0),(0,2),(2,0),(3,3)]    % 最短
[(0,0),(0,3),(1,1),(2,1),(2,3),(3,1)]
[(0,0),(1,1),(1,2),(1,3),(3,0),(3,2)]
[(0,1),(1,1),(1,3),(2,0),(2,2),(2,3)]
[(0,2),(1,0),(1,1),(2,2),(3,1),(3,2)]
[(0,0),(0,1),(0,3),(1,0),(1,2),(2,1),(3,0),(3,3)]
[(0,0),(0,1),(1,0),(1,3),(2,3),(3,1),(3,2),(3,3)]
[(0,1),(0,2),(0,3),(1,3),(2,1),(2,2),(3,1),(3,3)]
[(0,1),(0,2),(1,2),(2,2),(2,3),(3,0),(3,2),(3,3)]
[(0,3),(1,0),(2,0),(2,1),(2,2),(2,3),(3,2),(3,3)]
[(1,0),(1,2),(1,3),(2,0),(2,2),(3,0),(3,1),(3,3)]
...
*/
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX