2009/02/20でやってみた畳を敷き詰める問題をしつこく考え直していたところ、余計な総当たりをしていたことに気がつきました。
結果としてコードを1行縮めることができ、listup/0 が瞬時に完了するようになりました。
:- 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,[[X,Y]|T]),
member(D,[tate,yoko]),
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.
実行例:
$ time pl -s tatami.pl -t 'listup,halt'
% tatami.pl compiled into tatami 0.00 sec, 4,824 bytes
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.52)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
[[0, 0, tate], [0, 2, tate], [0, 4, yoko], [1, 0, tate], [1, 2, tate], [2, 0, tate], [2, 2, tate], [2, 4, yoko], [3, 0, tate], [3, 2, tate]]
[[0, 0, tate], [0, 2, tate], [0, 4, yoko], [1, 0, tate], [1, 2, tate], [2, 0, tate], [2, 2, yoko], [2, 3, tate], [3, 0, tate], [3, 3, tate]]
(snip)
[[0, 0, yoko], [0, 1, yoko], [0, 2, yoko], [0, 3, yoko], [0, 4, yoko], [2, 0, yoko], [2, 1, yoko], [2, 2, yoko], [2, 3, yoko], [2, 4, yoko]]
real 0m0.068s
user 0m0.058s
sys 0m0.008s
$