You selected ccp.pl
% Programing the counterfeit coin problem
% using SWI-Prolog version 6.0.2 (Windows Vista OS)
% 13 Aug 2012 (modified: 14 & 15 Aug 2012)
% Created by kenryo Indo (kenryo.indo@gmail.com)
% References:
% [1] Wikipedia: Balance Puzzle. http://en.wikipedia.org/wiki/Balance_puzzle
% [2] Sniedovich, R. (2003): OR/MS Games: 3. Counterfeit Coin Problem
% INFORMS, Trans. Education, Volume 3, Number 2.
% http://archive.ite.journal.informs.org/Vol3No2/Sniedovich/
% [3] Kołodziejczyk, M.:Two-pan balance and generalized counterfeit coin problem
% http://math.uni.lodz.pl/~andkom/Marcel/Kule-en.pdf
% [4] Yosshy: Yosshy no sansu, sugaku no heya (Japanese). http://yosshy.sansu.org/tenbin.htm
%--------------------------------------------------------
% 13 Aug 2012
% 13-coin problem and 8-coin problem
%--------------------------------------------------------
/*
There are N coins that are identical in appearance.
One coin is counterfeit, having a slightly smaller weight than the other coins.
The mission is to identify the counterfeit coin with the aid of a two-pan balance
deploying the smallest possible number of weighings.
(cited from [2] and slightly modified)
*/
% The original 8-coin problem was posed by
% E. D. Schell (American Mathematical Monthly, Jan 1945)
% The 13-coin problem a version of the 8-coin problem was offered by
% H. Steinhaus (Mathematical Snapshots, 3rd ed., Dover, 1999)
all_N_coins( A, N):-
integer(N),
length( L, N),
findall( J, nth1( J, L, _), A).
% solve/5: Solve the puzzle for J a supposed counterfeit coin among the given N coins.
solve( N, A, B, C, J):-
integer(N),
three_weigh( N, A, B, C),
length( L, N),
nth1( J, L, _),
find_fake( N, A, B, C, J).
% solve/4: Solve the puzzle for every supposed counterfeit coin.
solve( N, A, B, C):-
integer(N),
three_weigh( N, A, B, C),
length( L, N),
\+ (
nth1( J, L, _),
\+ find_fake( N, A, B, C, J)
).
% three_weigh/4
% N: the number of coins.
% 1st step weigh: place X1 the left pan, Y1 the right pan, and Z1 on desk.
% 2nd step weigh: place X2 the left pan, Y2 the right pan, and Z2 on desk.
% 3rd step weigh: place X3 the left pan, Y3 the right pan, and Z3 on desk.
three_weigh( N, [X1, Y1, Z1], [X2, Y2, Z2], [X3, Y3, Z3]):-
integer(N),
all_N_coins( A, N),
disjoint_triple( A, X1, Y1, Z1),
disjoint_triple( A, X2, Y2, Z2),
disjoint_triple( A, X3, Y3, Z3).
% find_fake
% observing the results of weighing during three steps:
% data: B = (B(1), B(2), B(3))
% where
% left_rize => B(i) = 1
% right_rize => B(i) = 2
% balanced => B(i) = 0
% When the counterfeit coin is found.
%
% Case 1: B1>0, B2>0, B3>0
% and there is a single unique coin that
% always was placed the side of the rizen (or sunk) pan
% and it is lighter (or heavier).
find_fake( N, B1, B2, B3, J):-
% B1 = [X1, Y1, Z1],
% B2 = [X2, Y2, Z2],
% B3 = [X3, Y3, Z3],
% N = 13,
length( L, N),
three_times_weighed( J, S, [B1, B2, B3]),
\+ (
nth1( K, L, _),
K \= J,
three_times_weighed( K, S, [B1, B2, B3])
).
% Case 2: Either
% 2-1: B1 > 0, and B2 = B3 = 0,
% 2-2: B2 > 0, and B1 = B3 = 0, or
% 2-3: B3 > 0, and B2 = B1 = 0
% and there is a single unique coin in the first, second, third trial
% respectively that was never weighed during the other two trials.
% And if the coin on the rizen side, it is lighter, otherwise heavier.
find_fake( N, B1, B2, B3, J):-
B1 = [X1, Y1, _Z1],
B2 = [X2, Y2, _Z2],
B3 = [X3, Y3, _Z3],
length( L, N),
one_time_weighed( J, F, [B1, B2, B3]),
nth1( P, F, T),
T \= no,
nth1( P, [[X1, Y1], [X2, Y2], [X3, Y3]], [X, Y]),
member( C, [X, Y]),
member( J, C),
append( X, Y, D),
\+ (
nth1( K, L, _),
( N=8 -> member( K, C), K \= J; true),
( N=13 -> member( K, D),K \= J; true),
one_time_weighed( K, F, [B1, B2, B3])
).
% Case 3 (3-1..3-3): either
% B1 = 0, B2 >0, and B3 > 0,
% B1 > 0, B2 =0, and B3 > 0,
% B1 > 0, B2 >0, and B3 = 0,
% and there is a single unique coin in the two inclined weighs.
% And if the coin on the rizen side, it is lighter,
% otherwise heavier.
find_fake( N, B1, B2, B3, J):-
length( L, N),
two_times_weighed( J, F, [B1, B2, B3]),
\+ (
nth1( K, L, _),
K \= J,
two_times_weighed( K, F, [B1, B2, B3])
).
% Case 4: B1 = B2 = B3 = 0
% and there is a single unique coin
% that was never weighed during the three trials.
% It still remains unknown whether the counterfeit coin is light or heavy.
find_fake( N, B1, B2, B3, J):-
length( L, N),
never_weighed( J, [B1, B2, B3]),
\+ (
nth1( K, L, _),
K \= J,
never_weighed( K, [B1, B2, B3])
).
three_times_weighed( J, H, C):-
k_times_weighed( J, H, C, 3).
two_times_weighed( J, H, C):-
k_times_weighed( J, H, C, 2).
one_time_weighed( J, H, C):-
k_times_weighed( J, H, C, 1).
never_weighed( J, C):-
k_times_weighed( J, _, C, 0).
k_times_weighed( _, [], [], 0).
k_times_weighed( J, [left| B], [[X, _, _] | C], K):-
member( J, X),
k_times_weighed( J, B, C, K0),
K is K0 + 1.
k_times_weighed( J, [right| B], [[_, Y, _] | C], K):-
member( J, Y),
k_times_weighed( J, B, C, K0),
K is K0 + 1.
k_times_weighed( J, [no| B], [[_, _, Z] | C], K):-
member( J, Z),
k_times_weighed( J, B, C, K).
% the experimental design: using the 3-adic numbering
% The first argument of b/4 (resp. c/4) below stands for each of 8 (resp.13 ) coins.
% The remaining three arguments represent
% 1st weigh: the 2nd argument,
% 2nd weigh: the 3rd argument, and
% 3rd weigh: the 4th argument.
% where
% a value 1 represents "place left pan",
% a value 2 represents "place right pan", and
% a value 0 represents "remain on desk."
% For the 8-coin problem:
b( 1, 0,1,0).
b( 2, 0,2,0).
b( 3, 1,1,0).
b( 4, 1,0,0).
b( 5, 1,2,0).
b( 6, 2,2,0).
b( 7, 2,1,0).
b( 8, 2,0,0).
x_design_8( A, B, C):-
findall( J, b( J, 1, _,_), X1),
findall( J, b( J, 2, _,_), Y1),
findall( J, b( J, 0, _,_), Z1),
findall( J, b( J, _, 1,_), X2),
findall( J, b( J, _, 2,_), Y2),
findall( J, b( J, _, 0,_), Z2),
findall( J, b( J, _, 0,_), Z2),
A = [X1, Y1, Z1],
B = [X2, Y2, Z2],
C = [[], [], [1,2,3,4,5,6,7,8]].
solve_8( A, B, C):-
x_design_8( A, B, C),
solve( 8, A, B, C).
/*
?- solve_8( A,B,C).
A = [[3, 4, 5], [6, 7, 8], [1, 2]],
B = [[1, 3, 7], [2, 5, 6], [4, 8]],
C = [[], [], [1, 2, 3, 4, 5, 6|...]] ;
false.
*/
% For the 13-coin problem:
c( 1, 0,0,0).
c( 2, 0,0,1).
c( 3, 0,1,0).
c( 4, 0,2,2).
c( 5, 0,2,1).
c( 6, 1,0,0).
c( 7, 1,0,1).
c( 8, 1,0,2).
c( 9, 1,1,0).
c( 10, 2,2,2).
c( 11, 2,2,1).
c( 12, 2,1,0).
c( 13, 2,1,2).
% More concretely,
% 1st step: weighing [6,7,8,9] to [10,11,12,13]
% 2nd step: weighing [3,9,12,13] to [4,5,10,11]
% 3rd step: weighing [2,5,7,11] to [4,8,10,13]
% Analyzing the data:
% If (B(1), B(2), B(3)) coincides with the 3-adic number of a coin K,
% Kth coin is counterfeit and light.
% If (C(1), C(2), C(3)) coincides with the 3-adic number of a coin,
% Kth coin is counterfeit and heavy,
% where C(k) = 2 if B(k) =1, C(k) = 1 if B(k) = 2, and C(k) = 0 if B(k) = 0.
% If (B(1), B(2), B(3)) = (0, 0, 0),
% the first coin is counterfeit but whether light or heavy is unknown.
x_design_13( A, B, C):-
findall( J, c( J, 1, _,_), X1),
findall( J, c( J, 2, _,_), Y1),
findall( J, c( J, 0, _,_), Z1),
findall( J, c( J, _, 1,_), X2),
findall( J, c( J, _, 2,_), Y2),
findall( J, c( J, _, 0,_), Z2),
findall( J, c( J, _,_, 1), X3),
findall( J, c( J, _,_, 2), Y3),
findall( J, c( J, _,_, 0), Z3),
A = [X1, Y1, Z1],
B = [X2, Y2, Z2],
C = [X3, Y3, Z3].
solve_13( A, B, C):-
x_design_13( A, B, C),
solve( 13, A, B, C).
/*
?- x_design_13( A, B, C), solve( 13, A, B, C, 10).
A = [[6, 7, 8, 9], [10, 11, 12, 13], [1, 2, 3, 4, 5]],
B = [[3, 9, 12, 13], [4, 5, 10, 11], [1, 2, 6, 7, 8]],
C = [[2, 5, 7, 11], [4, 8, 10, 13], [1, 3, 6, 9, 12]] ;
false.
?- x_design_13( A, B, C), solve( 13, A, B, C, 3).
A = [[6, 7, 8, 9], [10, 11, 12, 13], [1, 2, 3, 4, 5]],
B = [[3, 9, 12, 13], [4, 5, 10, 11], [1, 2, 6, 7, 8]],
C = [[2, 5, 7, 11], [4, 8, 10, 13], [1, 3, 6, 9, 12]] ;
false.
?- x_design_13( A, B, C), solve( 13, A, B, C, 4).
A = [[6, 7, 8, 9], [10, 11, 12, 13], [1, 2, 3, 4, 5]],
B = [[3, 9, 12, 13], [4, 5, 10, 11], [1, 2, 6, 7, 8]],
C = [[2, 5, 7, 11], [4, 8, 10, 13], [1, 3, 6, 9, 12]] ;
false.
?- x_design_13( A,B,C),length( L, 13), nth1(J, L,_),
\+ \+ (solve(13, A,B,C,J), nl, write(J)), fail.
1
2
3
4
5
6
7
8
9
10
11
12
13
false.
*/
% common programs
% disjoint_pair
disjoint_pair( [], [], []).
disjoint_pair( [ A | W ], [ A | X], Y):-
disjoint_pair( W, X, Y).
disjoint_pair( [ A | W ], X, [ A | Y]):-
disjoint_pair( W, X, Y).
/*
?- disjoint_pair([1,2,3],A,B), nl, write(A-B), fail.
[1,2,3]-[]
[1,2]-[3]
[1,3]-[2]
[1]-[2,3]
[2,3]-[1]
[2]-[1,3]
[3]-[1,2]
[]-[1,2,3]
false.
*/
% disjoint_triple
disjoint_triple( W, X, Y, Z):-
disjoint_pair( W, X, P),
disjoint_pair( P, Y, Z).
/*
?- disjoint_triple([1,2,3],A,B,C), writeln(A-B-C), fail.
[1,2,3]-[]-[]
[1,2]-[3]-[]
[1,2]-[]-[3]
[1,3]-[2]-[]
[1,3]-[]-[2]
[1]-[2,3]-[]
[1]-[2]-[3]
[1]-[3]-[2]
[1]-[]-[2,3]
[2,3]-[1]-[]
[2,3]-[]-[1]
[2]-[1,3]-[]
...
[]-[]-[1,2,3]
false.
*/
% an alternative
d_triple( [], [], [], []).
d_triple( [ A | W ], [ A | X], Y, Z):-
d_triple( W, X, Y, Z).
d_triple( [ A | W ], X, [ A | Y], Z):-
d_triple( W, X, Y, Z).
d_triple( [ A | W ], X, Y, [ A | Z]):-
d_triple( W, X, Y, Z).
/*
?- d_triple([1,2,3],A,B,C),
| \+ disjoint_triple([1,2,3],A,B,C).false.
?- disjoint_triple([1,2,3],A,B,C),
| \+ d_triple([1,2,3],A,B,C).
false.
*/
%-end-------------------------------------------------------
% depreciated(trash)
/*
% for 8-coin
find_fake( N, B1, B2, B3, J):-
W1 = [X1, Y1, Z1],
W2 = [X2, Y2, Z2],
W3 = [X3, Y3, Z3],
N = 8,
length( L, N),
length( Z3, N),
two_times_weighed( J, S, [B1, B2, B3]),
\+ (
nth1( K, L, _),
K \= J,
two_times_weighed( K, S, [B1, B2, B3])
).
three_times_weighed( _, [], []).
three_times_weighed( J, [left| B], [[X1, _] | C]):-
member( J, X1),
three_times_weighed( J, B, C).
three_times_weighed( J, [right| B], [[_, X2] | C]):-
member( J, X2),
three_times_weighed( J, B, C).
two_times_weighed( _, [], []).
two_times_weighed( J, [left| B], [[X, _, _] | C]):-
member( J, X),
two_times_weighed( J, B, C).
two_times_weighed( J, [right| B], [[_, Y, _] | C]):-
member( J, Y),
two_times_weighed( J, B, C).
two_times_weighed( J, [no| B], [[_, _, Z] | C]):-
member( J, Z),
two_times_weighed( J, B, C).
% for 8-coin
three_times_weighed( J, [Z1, Z2, Z3]):-
\+ member( J, Z1),
\+ member( J, Z2),
\+ member( J, Z3).
two_times_weighed( J, [Z1, Z2, Z3]):-
member( J, Z1),
\+ member( J, Z2),
\+ member( J, Z3).
two_times_weighed( J, [Z1, Z2, Z3]):-
\+ member( J, Z1),
member( J, Z2),
\+ member( J, Z3).
two_times_weighed( J, [Z1, Z2, Z3]):-
\+ member( J, Z1),
\+ member( J, Z2),
member( J, Z3).
% --
one_time_weighed( J, 1, [Z1, Z2, Z3]):-
\+ member( J, Z1),
member( J, Z2),
member( J, Z3).
one_time_weighed( J, 2, [Z1, Z2, Z3]):-
member( J, Z1),
\+ member( J, Z2),
member( J, Z3).
one_time_weighed( J, 3, [Z1, Z2, Z3]):-
member( J, Z1),
member( J, Z2),
\+ member( J, Z3).
never_weighed( J, [Z1, Z2, Z3]):-
member( J, Z1),
member( J, Z2),
member( J, Z3).
% an alternative to three_weigh
unit_design_sol( [], [[], [], []]).
unit_design_sol( [N|L], Case):-
member( Case,
[
[[N|X], Y, Z],
[X, [N|Y], Z],
[X, Y, [N|Z]]
]),
unit_design_sol( L, [X, Y, Z]).
design_sol( L, B1, B2, B3):-
unit_design_sol( L, W1),
unit_design_sol( L, W2),
unit_design_sol( L, W3).
*/
return to front page.