「連環の数」という、ちょっとだけ有名な？パズルがある。
パソコン初心者の館：藤原さんの制約プログラミング のページを参考にしました。
♪ 環が２つの場合
A〜Cには、1〜3を1つずつ入れる。そして互いに素である。
重なっている部分は、その両隣の和となる。 つまり、 B=A+C となる。
解の一例は、次のようになります。
♪ プログラムコード code
love:uema% cat renkan_2.pl [~/love/prolog] % renkan_2.pl main :- range( 1, 3, R ), member( A, R ), member( B, R ), member( C, R ), different( [A,B,C] ), B is A + C, write( 'A = ' ), write( A ), nl, write( 'B = ' ), write( B ), nl, write( 'C = ' ), write( C ), nl. range( N, N, [N] ) :- N >= 1, !. range( N, M, [N|R] ) :- N >= 1, N =< M, N1 is N + 1, range( N1, M, R ). member( A, [A|_] ). member( A, [_|B] ) :- member( A, B ). different([]). different([X|Xs]) :- \+ member(X, Xs), different(Xs). love:uema% [~/love/prolog]
実行例
love:uema% swipl -qs renkan_2.pl [~/love/prolog] ?- main. A = 1 B = 3 C = 2 true ; A = 2 B = 3 C = 1 true ; false. ?-
２つの解が求まりました。
♪ ３連環の場合
問題：
解の一例は、次のようになります。
♪ プログラムコード code
love:uema% cat renkan_3.pl [~/love/prolog] % renkan_3.pl main :- range( 1, 5, R ), member( A, R ), member( B, R ), member( C, R ), member( D, R ), member( E, R ), different( [A,B,C,D,E] ), B is A + C, D is C + E, write( 'A = ' ), write( A ), nl, write( 'B = ' ), write( B ), nl, write( 'C = ' ), write( C ), nl, write( 'D = ' ), write( D ), nl, write( 'E = ' ), write( E ), nl. range( N, N, [N] ) :- N >= 1, !. range( N, M, [N|R] ) :- N >= 1, N =< M, N1 is N + 1, range( N1, M, R ). member( A, [A|_] ). member( A, [_|B] ) :- member( A, B ). different([]). different([X|Xs]) :- \+ member(X, Xs), different(Xs). love:uema% [~/love/prolog]
実行例
love:uema% swipl -qs renkan_3.pl [~/love/prolog] ?- main. A = 1 B = 4 C = 3 D = 5 E = 2 true ; A = 2 B = 3 C = 1 D = 5 E = 4 true ; A = 2 B = 5 C = 3 D = 4 E = 1 true ; A = 4 B = 5 C = 1 D = 3 E = 2 true ; false. ?-
４つの解が求まりました。
♪ ７連環の場合
上の方法を７連環にも伸ばし、実行しましたが、すごく時間がかかります。
なので別の方法でプログラミングしました。一瞬で求まりました。
♪ プログラムコード code
% renkan_7.pl main :- range( 1, 13, R0 ), del( A, R0, R1 ), A =< 7, % これで対称解を省くことが出来るかも？ del( B, R1, R2 ), del( C, R2, R3 ), B is A + C, del( D, R3, R4 ), del( E, R4, R5 ), D is C + E, del( F, R5, R6 ), del( G, R6, R7 ), F is E + G, del( H, R7, R8 ), del( I, R8, R9 ), H is G + I, del( J, R9, R10 ), del( K, R10, R11 ), J is I + K, del( L, R11, R12 ), del( M, R12, _ ), L is K + M, write( ' A=' ), write( A ), write( ', B=' ), write( B ), write( ', C=' ), write( C ), write( ', D=' ), write( D ), write( ', E=' ), write( E ), write( ', F=' ), write( F ), write( ', G=' ), write( G ), write( ', H=' ), write( H ), write( ', I=' ), write( I ), write( ', J=' ), write( J ), write( ', K=' ), write( K ), write( ', L=' ), write( L ), write( ', M=' ), write( M ), nl, write( '--------------------------------------------------------------------------' ),nl, flush_output, fail. range( N, N, [N] ) :- N >= 1, !. range( N, M, [N|R] ) :- N >= 1, N =< M, N1 is N + 1, range( N1, M, R ). del( A, [A|L], L ). del( A, [B|L1], [B|L2] ) :- del( A, L1, L2 ).
実行例
love:uema% swipl -qs renkan_7.pl [~/love/prolog] ?- main. A=1, B=3, C=2, D=10, E=8, F=12, G=4, H=9, I=5, J=11, K=6, L=13, M=7 -------------------------------------------------------------------------- A=1, B=4, C=3, D=8, E=5, F=11, G=6, H=13, I=7, J=9, K=2, L=12, M=10 -------------------------------------------------------------------------- A=1, B=6, C=5, D=7, E=2, F=10, G=8, H=11, I=3, J=12, K=9, L=13, M=4 -------------------------------------------------------------------------- A=1, B=6, C=5, D=8, E=3, F=7, G=4, H=13, I=9, J=11, K=2, L=12, M=10 -------------------------------------------------------------------------- A=1, B=6, C=5, D=8, E=3, F=13, G=10, H=12, I=2, J=9, K=7, L=11, M=4 -------------------------------------------------------------------------- A=1, B=6, C=5, D=13, E=8, F=10, G=2, H=11, I=9, J=12, K=3, L=7, M=4 -------------------------------------------------------------------------- A=1, B=10, C=9, D=12, E=3, F=5, G=2, H=8, I=6, J=13, K=7, L=11, M=4 -------------------------------------------------------------------------- A=1, B=10, C=9, D=12, E=3, F=11, G=8, H=13, I=5, J=7, K=2, L=6, M=4 -------------------------------------------------------------------------- A=1, B=11, C=10, D=13, E=3, F=8, G=5, H=12, I=7, J=9, K=2, L=6, M=4 -------------------------------------------------------------------------- A=1, B=12, C=11, D=13, E=2, F=6, G=4, H=9, I=5, J=8, K=3, L=10, M=7 -------------------------------------------------------------------------- A=1, B=12, C=11, D=13, E=2, F=7, G=5, H=8, I=3, J=9, K=6, L=10, M=4 -------------------------------------------------------------------------- A=2, B=3, C=1, D=8, E=7, F=12, G=5, H=11, I=6, J=10, K=4, L=13, M=9 -------------------------------------------------------------------------- A=2, B=3, C=1, D=9, E=8, F=13, G=5, H=12, I=7, J=11, K=4, L=10, M=6 -------------------------------------------------------------------------- A=2, B=5, C=3, D=9, E=6, F=10, G=4, H=11, I=7, J=8, K=1, L=13, M=12 -------------------------------------------------------------------------- A=2, B=5, C=3, D=11, E=8, F=12, G=4, H=13, I=9, J=10, K=1, L=7, M=6 -------------------------------------------------------------------------- A=2, B=6, C=4, D=9, E=5, F=12, G=7, H=8, I=1, J=11, K=10, L=13, M=3 -------------------------------------------------------------------------- A=2, B=7, C=5, D=6, E=1, F=10, G=9, H=13, I=4, J=12, K=8, L=11, M=3 -------------------------------------------------------------------------- A=2, B=8, C=6, D=9, E=3, F=10, G=7, H=11, I=4, J=5, K=1, L=13, M=12 -------------------------------------------------------------------------- A=2, B=8, C=6, D=13, E=7, F=11, G=4, H=5, I=1, J=10, K=9, L=12, M=3 -------------------------------------------------------------------------- A=2, B=10, C=8, D=11, E=3, F=7, G=4, H=9, I=5, J=6, K=1, L=13, M=12 -------------------------------------------------------------------------- A=2, B=10, C=8, D=11, E=3, F=12, G=9, H=13, I=4, J=5, K=1, L=7, M=6 -------------------------------------------------------------------------- A=2, B=10, C=8, D=13, E=5, F=11, G=6, H=7, I=1, J=4, K=3, L=12, M=9 -------------------------------------------------------------------------- A=2, B=11, C=9, D=10, E=1, F=4, G=3, H=8, I=5, J=12, K=7, L=13, M=6 -------------------------------------------------------------------------- A=2, B=11, C=9, D=10, E=1, F=6, G=5, H=13, I=8, J=12, K=4, L=7, M=3 -------------------------------------------------------------------------- A=2, B=12, C=10, D=11, E=1, F=6, G=5, H=8, I=3, J=7, K=4, L=13, M=9 -------------------------------------------------------------------------- A=2, B=13, C=11, D=12, E=1, F=7, G=6, H=10, I=4, J=9, K=5, L=8, M=3 -------------------------------------------------------------------------- A=3, B=4, C=1, D=10, E=9, F=11, G=2, H=8, I=6, J=13, K=7, L=12, M=5 -------------------------------------------------------------------------- A=3, B=7, C=4, D=6, E=2, F=12, G=10, H=11, I=1, J=9, K=8, L=13, M=5 -------------------------------------------------------------------------- A=3, B=7, C=4, D=9, E=5, F=6, G=1, H=12, I=11, J=13, K=2, L=10, M=8 -------------------------------------------------------------------------- A=3, B=7, C=4, D=12, E=8, F=13, G=5, H=6, I=1, J=10, K=9, L=11, M=2 -------------------------------------------------------------------------- A=3, B=8, C=5, D=7, E=2, F=6, G=4, H=13, I=9, J=10, K=1, L=12, M=11 -------------------------------------------------------------------------- A=3, B=8, C=5, D=9, E=4, F=10, G=6, H=7, I=1, J=12, K=11, L=13, M=2 -------------------------------------------------------------------------- A=3, B=9, C=6, D=7, E=1, F=5, G=4, H=12, I=8, J=10, K=2, L=13, M=11 -------------------------------------------------------------------------- A=3, B=10, C=7, D=8, E=1, F=12, G=11, H=13, I=2, J=6, K=4, L=9, M=5 -------------------------------------------------------------------------- A=3, B=11, C=8, D=12, E=4, F=13, G=9, H=10, I=1, J=6, K=5, L=7, M=2 -------------------------------------------------------------------------- A=3, B=12, C=9, D=10, E=1, F=5, G=4, H=11, I=7, J=13, K=6, L=8, M=2 -------------------------------------------------------------------------- A=3, B=13, C=10, D=11, E=1, F=8, G=7, H=12, I=5, J=9, K=4, L=6, M=2 -------------------------------------------------------------------------- A=3, B=13, C=10, D=11, E=1, F=9, G=8, H=12, I=4, J=6, K=2, L=7, M=5 -------------------------------------------------------------------------- A=4, B=5, C=1, D=7, E=6, F=8, G=2, H=11, I=9, J=12, K=3, L=13, M=10 -------------------------------------------------------------------------- A=4, B=5, C=1, D=12, E=11, F=13, G=2, H=8, I=6, J=9, K=3, L=10, M=7 -------------------------------------------------------------------------- A=4, B=6, C=2, D=7, E=5, F=13, G=8, H=11, I=3, J=12, K=9, L=10, M=1 -------------------------------------------------------------------------- A=4, B=6, C=2, D=9, E=7, F=12, G=5, H=8, I=3, J=13, K=10, L=11, M=1 -------------------------------------------------------------------------- A=4, B=7, C=3, D=12, E=9, F=11, G=2, H=10, I=8, J=13, K=5, L=6, M=1 -------------------------------------------------------------------------- A=4, B=9, C=5, D=11, E=6, F=13, G=7, H=8, I=1, J=3, K=2, L=12, M=10 -------------------------------------------------------------------------- A=4, B=9, C=5, D=12, E=7, F=13, G=6, H=8, I=2, J=3, K=1, L=11, M=10 -------------------------------------------------------------------------- A=4, B=10, C=6, D=9, E=3, F=5, G=2, H=13, I=11, J=12, K=1, L=8, M=7 -------------------------------------------------------------------------- A=4, B=10, C=6, D=9, E=3, F=8, G=5, H=7, I=2, J=13, K=11, L=12, M=1 -------------------------------------------------------------------------- A=4, B=11, C=7, D=9, E=2, F=12, G=10, H=13, I=3, J=8, K=5, L=6, M=1 -------------------------------------------------------------------------- A=4, B=11, C=7, D=13, E=6, F=8, G=2, H=5, I=3, J=12, K=9, L=10, M=1 -------------------------------------------------------------------------- A=4, B=13, C=9, D=10, E=1, F=3, G=2, H=8, I=6, J=11, K=5, L=12, M=7 -------------------------------------------------------------------------- A=4, B=13, C=9, D=12, E=3, F=5, G=2, H=8, I=6, J=7, K=1, L=11, M=10 -------------------------------------------------------------------------- A=4, B=13, C=9, D=12, E=3, F=11, G=8, H=10, I=2, J=7, K=5, L=6, M=1 -------------------------------------------------------------------------- A=5, B=7, C=2, D=6, E=4, F=12, G=8, H=9, I=1, J=11, K=10, L=13, M=3 -------------------------------------------------------------------------- A=5, B=8, C=3, D=4, E=1, F=11, G=10, H=12, I=2, J=9, K=7, L=13, M=6 -------------------------------------------------------------------------- A=5, B=8, C=3, D=7, E=4, F=6, G=2, H=11, I=9, J=10, K=1, L=13, M=12 -------------------------------------------------------------------------- A=5, B=8, C=3, D=7, E=4, F=6, G=2, H=13, I=11, J=12, K=1, L=10, M=9 -------------------------------------------------------------------------- A=5, B=9, C=4, D=6, E=2, F=13, G=11, H=12, I=1, J=8, K=7, L=10, M=3 -------------------------------------------------------------------------- A=5, B=11, C=6, D=7, E=1, F=3, G=2, H=10, I=8, J=12, K=4, L=13, M=9 -------------------------------------------------------------------------- A=5, B=11, C=6, D=8, E=2, F=9, G=7, H=10, I=3, J=4, K=1, L=13, M=12 -------------------------------------------------------------------------- A=5, B=12, C=7, D=8, E=1, F=3, G=2, H=11, I=9, J=13, K=4, L=10, M=6 -------------------------------------------------------------------------- A=5, B=12, C=7, D=11, E=4, F=13, G=9, H=10, I=1, J=3, K=2, L=8, M=6 -------------------------------------------------------------------------- A=5, B=12, C=7, D=13, E=6, F=8, G=2, H=11, I=9, J=10, K=1, L=4, M=3 -------------------------------------------------------------------------- A=5, B=13, C=8, D=9, E=1, F=11, G=10, H=12, I=2, J=6, K=4, L=7, M=3 -------------------------------------------------------------------------- A=5, B=13, C=8, D=10, E=2, F=11, G=9, H=12, I=3, J=4, K=1, L=7, M=6 -------------------------------------------------------------------------- A=5, B=13, C=8, D=12, E=4, F=10, G=6, H=7, I=1, J=3, K=2, L=11, M=9 -------------------------------------------------------------------------- A=6, B=7, C=1, D=4, E=3, F=12, G=9, H=11, I=2, J=10, K=8, L=13, M=5 -------------------------------------------------------------------------- A=6, B=7, C=1, D=5, E=4, F=13, G=9, H=12, I=3, J=11, K=8, L=10, M=2 -------------------------------------------------------------------------- A=6, B=7, C=1, D=10, E=9, F=13, G=4, H=12, I=8, J=11, K=3, L=5, M=2 -------------------------------------------------------------------------- A=6, B=8, C=2, D=3, E=1, F=10, G=9, H=13, I=4, J=11, K=7, L=12, M=5 -------------------------------------------------------------------------- A=6, B=8, C=2, D=5, E=3, F=7, G=4, H=13, I=9, J=10, K=1, L=12, M=11 -------------------------------------------------------------------------- A=6, B=9, C=3, D=4, E=1, F=11, G=10, H=12, I=2, J=7, K=5, L=13, M=8 -------------------------------------------------------------------------- A=6, B=9, C=3, D=7, E=4, F=5, G=1, H=12, I=11, J=13, K=2, L=10, M=8 -------------------------------------------------------------------------- A=6, B=10, C=4, D=7, E=3, F=5, G=2, H=13, I=11, J=12, K=1, L=9, M=8 -------------------------------------------------------------------------- A=6, B=10, C=4, D=9, E=5, F=12, G=7, H=8, I=1, J=3, K=2, L=13, M=11 -------------------------------------------------------------------------- A=6, B=10, C=4, D=11, E=7, F=12, G=5, H=13, I=8, J=9, K=1, L=3, M=2 -------------------------------------------------------------------------- A=6, B=10, C=4, D=13, E=9, F=11, G=2, H=3, I=1, J=8, K=7, L=12, M=5 -------------------------------------------------------------------------- A=6, B=11, C=5, D=7, E=2, F=3, G=1, H=10, I=9, J=13, K=4, L=12, M=8 -------------------------------------------------------------------------- A=6, B=11, C=5, D=7, E=2, F=12, G=10, H=13, I=3, J=4, K=1, L=9, M=8 -------------------------------------------------------------------------- A=6, B=13, C=7, D=9, E=2, F=12, G=10, H=11, I=1, J=4, K=3, L=8, M=5 -------------------------------------------------------------------------- A=6, B=13, C=7, D=12, E=5, F=8, G=3, H=4, I=1, J=10, K=9, L=11, M=2 -------------------------------------------------------------------------- A=7, B=8, C=1, D=5, E=4, F=6, G=2, H=11, I=9, J=12, K=3, L=13, M=10 -------------------------------------------------------------------------- A=7, B=8, C=1, D=12, E=11, F=13, G=2, H=5, I=3, J=9, K=6, L=10, M=4 -------------------------------------------------------------------------- A=7, B=10, C=3, D=8, E=5, F=9, G=4, H=6, I=2, J=13, K=11, L=12, M=1 -------------------------------------------------------------------------- A=7, B=10, C=3, D=9, E=6, F=8, G=2, H=13, I=11, J=12, K=1, L=5, M=4 -------------------------------------------------------------------------- A=7, B=12, C=5, D=11, E=6, F=8, G=2, H=3, I=1, J=10, K=9, L=13, M=4 -------------------------------------------------------------------------- A=7, B=13, C=6, D=11, E=5, F=9, G=4, H=12, I=8, J=10, K=2, L=3, M=1 -------------------------------------------------------------------------- false. ?-