fixedpoint.jp

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
$

2009/02/24

畳を敷き詰めるには(再び)