4x5 の部屋に畳を敷き詰める問題を教えてもらいました。畳は縦横比が 1:2 になっているものと考えます。こういう問題こそ Prolog 向きだと思ったので swi-prolog で解いてみました。
:- module(tatami,[tatami/2,listup/0]).
room(4,5).
count(N) :- room(W,H),!,N is W*H/2.
space(X,Y) :-
room(W,H),
W0 is W-1,
H0 is H-1,
between(0,W0,X),
between(0,H0,Y).
covered([X,Y,yoko],X1,Y) :- X1 is X+1,!.
covered([X,Y,tate],X,Y1) :- Y1 is Y+1,!.
tatami([],Spaces) :- setof([X,Y],space(X,Y),Spaces),!.
tatami([[X,Y,D]|Rest],U) :-
tatami(Rest,S),
member(D,[tate,yoko]),
select([X,Y],S,T),
covered([X,Y,D],A,B),
select([A,B],T,U).
:- dynamic answers/1.
listup :-
count(N),
length(A,N),
tatami(A,[]),
sort(A,B),
\+ answers(B),
assert(answers(B)),
write(B),
write('\n'),
fail.
実行例は以下のようになります:
$ pl -s tatami.pl -t 'listup,halt'
かなりコンパクトに書けたことにはなりましたが、ここまでたどり着くのに時間がかかりました。また手元のマシンだと全ての解をリストアップするのに2時間以上かかります。