問題はこちら->http://nabetani.sakura.ne.jp/hena/orde28sqst/
隣接を判定するのに座標を用いる以外思いつきませんでした。
続けて割り算を用いて座標を求めると、誤差が出たり、差が検出できなくなりそうですので、
新しい部屋の長さが整数になるように、新しい部屋数に元の矩形の長さをかけたり、
最小公倍数を求めたりする方法がありますが、
前者だと簡単ですが数が大きくなりすぎる可能性がありますので最小公倍数を使いました。
まず準備として、calc/3で、元の矩形の長さと加える部屋の数との最小公倍数を一辺、
それに元の矩形の長さを最大公約数で割った値を加えたものをもう一辺とする新しい矩形を作り、
それを繰り返して最終的な矩形の座標(0,W,0,H)を作っておきます。
次に入力の逆順で、adju/14で、矩形の該当の辺の長さを部屋数で割ったものを部屋の一辺(S)とし、
それを用いてfindallで部屋の座標を決め、また残りの矩形の座標(NFX等)もSを加減して作ります。
その後、solve/3のselect/1で泊まる部屋の座標を求めfindallで隣接する部屋を求めています。
adju/14はほとんど同じようなコードが並んで綺麗でないのですが、
加減も逆になったりしてまとめるのが面倒そうなのでそのままにしています。
%swi-Prolog version 7.4.2
%start.
%:-initialization(start). %for ideone
gcd(0, B, B):-!.
gcd(A, B, R):-C is B mod A, gcd(C, A, R).
adju('E',N,M,XF,XT,YF,YT,L,NM,NXF,NXT,NYF,NYT,R):-
S is (YT-YF) div N,NXF=XF,NXT is XT-S,NYF=YF,NYT=YT,
findall(C,(between(1,N,X),Xl=NXT,Xr=XT,Yt is NYF+S*X,Yb is Yt-S,
Rn is M+1-X,C=[Xl,Xr,Yb,Yt]-Rn),L2),
NM is M-N,R=[L|L2].
adju('W',N,M,XF,XT,YF,YT,L,NM,NXF,NXT,NYF,NYT,R):-
S is (YT-YF) div N,NXF is XF+S,NXT=XT,NYF=YF,NYT=YT,
findall(C,(between(1,N,X),Xl=XF,Xr=NXF,Yt is NYF+S*X,Yb is Yt-S,
Rn is M+1-X,C=[Xl,Xr,Yb,Yt]-Rn),L2),
NM is M-N,R=[L|L2].
adju('N',N,M,XF,XT,YF,YT,L,NM,NXF,NXT,NYF,NYT,R):-
S is (XT-XF) div N,NXF=XF,NXT=XT,NYF=YF,NYT is YT-S,
findall(C,(between(1,N,X),Xr is XF+S*X,Xl is Xr-S,Yb=NYT,Yt=YT,
Rn is M-N+X,C=[Xl,Xr,Yb,Yt]-Rn),L2),
NM is M-N,R=[L|L2].
adju('S',N,M,XF,XT,YF,YT,L,NM,NXF,NXT,NYF,NYT,R):-
S is (XT-XF) div N,NXF=XF,NXT=XT,NYF is YF+S,NYT is YT,
findall(C,(between(1,N,X),Xr is XF+S*X,Xl is Xr-S,Yb=YF,Yt=NYF,
Rn is M-N+X,C=[Xl,Xr,Yb,Yt]-Rn),L2),
NM is M-N,R=[L|L2].
calc(D-N,(X,Y,F),(X1,Y1,S)):-
S is F+N,((D=='N';D=='S')->calc1(N,X,Y,X1,Y1);calc1(N,Y,X,Y1,X1)).
calc1(N,A,B,A1,B1):-gcd(N,A,V),A1 is (N div V)*A,B1 is B*(N div V)+(A div V).
solve1([],M,XF,XT,YF,YT,L,R):-
R=[[XF,XT,YF,YT]-M|L].
solve1([D-N|T],M,XF,XT,YF,YT,L,R):-
adju(D,N,M,XF,XT,YF,YT,L,NM,NXF,NXT,NYF,NYT,L1),solve1(T,NM,NXF,NXT,NYF,NYT,L1,R).
solve(N,L,R):-
foldl(calc,L,(1,1,1),(W,H,M)),reverse(L,L1),solve1(L1,M,0,W,0,H,[],R1),
flatten(R1,R2),select([FX,TX,FY,TY]-N,R2,R3),
findall(N1,(member([FX1,TX1,FY1,TY1]-N1,R3),((FX1<TX,TX1>FX,(FY1=TY;TY1=FY));
(FY1<TY,TY1>FY,(FX1=TX;TX1=FX)))),R),!.
start:-str(S),split_string(S,"\s\n","\s",L),pre(L).
pre([]).
pre([_,B,Q|T]):-
atomics_to_string(L,"/",B),L=[S,N],atom_chars(S,L1),chan(L1,L2),
atom_number(N,N1),solve(N1,L2,R),disp(R,Q),pre(T).
disp(R,A):-
sort(R,R1),atomics_to_string(R1,",",S),
(A==S->Str=" pass ";Str=" fail "),write(Str),writeln(S).
chan([],[]).
chan([A,B|T],L):-chan(T,L1),atom_number(B,N),L=[A-N|L1].
str("0 N7N4E5/8 1,7,12,13,14
1 E1/1 2
2 N6/5 1,4,6
3 W5/3 1,2,4
4 S1N2/1 2,3,4
5 E7E6/11 4,5,10,12
6 W7W3/10 4,5,6,9,11
7 N1E4N1/5 1,4,6
8 N4E5S8/8 1,7,9
9 S7E3N6/9 1,10,16,17
10 N9E7S9/25 1,17,24,26
11 E1N2W2S3/1 2,3,6,8
12 E2N3W3S4/1 2,3,4,5,8,9,11,12
13 E4E8S8N8/7 2,6,8
14 W6W7W7E8/15 8,16
15 E2N9E7S5E7/3 1,2,17,18,19,23,24
16 E2N9E7S5E7/16 2,15,17,27,28
17 E8S7E2N2N9/20 1,2,17,19,25,26,27,28,29
18 N9S9N8W4W5/18 1,17,19
19 S3E9N8N6S5/25 18,19,24,26
20 S4N9W6S2N8/15 1,6,16,23,24
21 W5E3N4S7N7S6/7 1,8,13
22 N7S3N4W3N9W9/16 1,2,12,17,19,20,21,22,28,29,30,31
23 S9W8S7E2E4N9/26 1,27,28,29,36,37,38,39
24 W6W2S9E4N9E6/19 1,20,30,31,32,33,34
25 W7W1W2W6W7S6N9/9 2,3,4,5,6,7,8,10,11,26,27,28,33,34,35,36
26 E2E3E4E5E6E7N7/33 2,4,7,32,34
27 N8E3W8N8S8S9N5/33 1,32,34,41,42
28 S4S6W4N3E6N8S7/16 1,12,17,25,26,27
29 W5N4E3S1N3S8W9/14 1,6,13,18,19,20,21,22,23,24,25,30,31,32,33,34
30 N1E1N1E1N1E1N1E1/7 5,6,8,9
31 N1E1W1S1N1E1W1S1/5 1,3,4,7,8,9
32 N2E2W2S2N2E2W2S2/9 1,5,8,13,17
33 E2S4S1W5N5E8E9W6/36 9,14,37
34 E4S8E5S6E4W9N3W8/33 1,32,34,45,46
35 E6W7E7W4N9N3E6N9/22 8,9,23,26,27
36 E9E7E3S8S3S6W3S6N9/50 1,49,51
37 N6N6E3W8W5W1W3N9S7/30 25,26,27,28,29,31,32,33,35,36,37,38,43,44,45,46
38 S9N2E4N5E6S5S6W8W9/47 39,48
39 N9E7E7E6W8N6N4E1S1E8/34 1,33,35
40 W6S8E9S5W5S8E5E1N3N8/50 1,16,43,48,49,51,54,55,56,57
41 W6W9E5E6S5S8N7W2N6N9/31 1,21,30,32,37,38,39
42 N6S5N7W7S7W4N6W5S9W3S5/42 16,17,18,41,43
43 S9W5N2W9W4E3N8W7N3W7W8/49 34,35,36,42,50,52,53,54
44 W5N9E7E4W9E7W6E4S7S2E7/32 4,5,31,33,46
45 E4W7E4S7E8W9N1E9W1N2W8S5/51 32,33,34,35,36,37,38,39,40,41,52,53,57,58,59,60,61,62,63,64,65
46 N7E6E4S5S6N7N8E2S6N9N5W5/26 20,21,25,27,48
47 N9N5N8E7N7N3N8S7N5W5S7E6/51 1,50,52,69,70
48 N9N5N8E7N7N3N8S7N5W5S7E6/75 24,25,26,37,74,76
49 N1E1N6W3W6N4N7W2S5N5E1E9S8/55 36,42,54,56
50 S9E8E7N5S7S9E6N9W9W5E3N8E9/77 48,49,50,76,78,90,91,92,93
51 S9E8E7N5S7S9E6N9W9W5E3N8E9/92 77,91,93
52 W5N7W4E5E8S9E5E7S7N8E8N9E8/29 21,22,28,30,43
53 W5N7W4E5E8S9E5E7S7N8E8N9E8/67 66,68,83,85
54 S7E9W7W5S8S3W4E7W4S9N4N8E8E7/60 38,39,59,61
55 W6E8E8W8W6N8N9S9W4S9S8N9S2E6/83 74,75,82,84,95
56 E7W4E4S4N4E6W3E7W4W7E5W8E4N5W7/22 1,21,23,71
57 W8S9N8S8N3W5E5N9E3N8S6W2S8E9E5/56 43,55,57,65
58 N8E3N7W3S7S6E9S8N5S7W8E2N9E6N7E7/99 84,85,98,100
59 W3W6S8W9E8N9W6E6N1S4E6S7S7W8S5N8/96 57,82,95,97
60 E6E7N6E9W8E6W7E8W8E5W7W9S6E9S7N5S6/52 38,39,51,53,67,68
61 N7N6S2W8S8W5N9S7N6S6W9E3E8W5N4W6N4/95 91,96,101
62 E6W4E4N9S6S8E6E3W5W4E9E6W9S5N7N9E4S4/23 2,12,22,24,90
63 W2N4W7E4E1W5W8E6S4E2N2N7E3W8E1E6W9N3/51 46,50,52,81,82
64 S8E9W9E7E8W8E8W4W6W6W9W8E5W9S3S8S4E9/100 86,87,99,101
65 W9W5N7E6W8W6W9S1E8S9W6S8S7N9W6S8E3S8/120 110,111,119,121
66 S1W1N4S8S1S3W3W4E7N7N4S4N1S9N6S6S5E1W8/49 41,42,43,44,59,60,61,62,63,64,76,77,78,79
67 S4W4E6N3N6W9N3N5S9N7S8N4W4E7W6S8W2E8S3/78 10,11,12,18,77,79,101,102
68 S4W4E6N3N6W9N3N5S9N7S8N4W4E7W6S8W2E8S3/87 86,88,96,105,106
69 W9W5N7E6W8W6W9S1E8S9W6S8S7N9W6S8E3S8E9/120 110,111,119,121
70 E6E2W4W3E2W8E6W5E8S4S6E1W2N5W4S9N9S2S9E8/87 72,73,74,75,76,86,92,93,94,95,96,101,102,103,104
71 N4W7S3S4W7S5N4N4N9S9E6N7S6S8N9W9N8E9E7S6/74 55,56,57,73,75,81,82
72 N5S4S1W2W1W2W5W6N7W3W8E1S9W9N1W8W1S2W2W6/78 74,75,77,82,83,84
73 N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9N7/87 53,69,86,88
74 N5E5S5W5N6E6S6W6N7E7S7W7N8E8S8W8N9E9S9W9/105 73,90,104,124,140,141
75 N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9W8/119 73,74,78,113,120,122,123,124,131,132,133,134").