fixedpoint.jp


2009/02/20

畳を敷き詰めるには

以下のコードにはまずい点があります。2009/02/24で改善したものを挙げています。

4x5 の部屋に畳を敷き詰める問題を教えてもらいました。畳は縦横比が 1:2 になっているものと考えます。こういう問題こそ Prolog 向きだと思ったので swi-prolog で解いてみました。

tatami.pl
:- 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時間以上かかります。


© 2006-2023 fixedpoint.jp