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

% 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)]
...
*/