B u s L o g i c:- prolog, code, chatter.

A solution to the Three Cards Puzzle

I don't usually use Prolog to solve puzzles, but it is a real strength of the language, so I decided to give it a go.

First an easy one taken from Puzzle Prime. https://www.puzzleprime.com/brain-teasers/deduction/three-cards/

The puzzle is defined as so:

There are three playing cards in a row. There is a two to the right of a king. There is a diamond to the left of a spade. There is an ace to the left of a heart. There is a heart to the left of a spade. Identify the three cards.

First off the puzzle is talking about cards, so a way to represent a card is need. I'm going to use the term c/2 to represent a card, where it might look like c(king, hearts). The first parameter is the card number, the second is the suite.

Next there is a pattern in the puzzle where each card is defined in relation to each other by position. For example card 1 is 'to the left' of card 2. This is true for all the puzzle rules. The puzzle doesn't define if that means immediately to the left or a some point to the left and there is a difference because if it can be anywhere to the left/right then more rules are needed.

These positional rules can be created into a prolog predicate that looks like the folllowing:

position_rule(A,B,A,B,_).
position_rule(A,B,A,_,B).
position_rule(A,B,_,A,B).

A and B are the cards, and the last three positions are the possible places those cards can be placed. For exapmle if position_rule is called with position_rule(c1, c2, P1, P2, P3) the following results are obtained:

?- position_rule(c(king, hearts), c(two, spades), P1, P2, P3).
P1 = c(king, hearts),
P2 = c(two, spades) ;

P1 = c(king, hearts),
P3 = c(two, spades) ;

P2 = c(king, hearts),
P3 = c(two, spades).

This covers all the possible cominations that cards can relate to each other by position if there are three cards.

Now the rules of the puzzle can be spelt out using the position_rule/5 predicate.

% There is a two to the right of a king.
card_rule1(C1,C2,C3) :- position_rule(c(king,_),c(two,_),C1,C2,C3).

% There is a diamond to the left of a spade.
card_rule2(C1,C2,C3) :- position_rule(c(_,diamond),c(_,spade),C1,C2,C3).

% There is an ace to the left of a heart.
card_rule3(C1,C2,C3) :- position_rule(c(ace,_),c(_,heart),C1,C2,C3).

% There is a heart to the left of a spade.
card_rule4(C1,C2,C3) :- position_rule(c(_,heart),c(_,spade),C1,C2,C3).

Note that we only know about one part of each card in the puzzle rules, so leave the other part as a blank variable which will be filled in using the next predicate.

cards(C1,C2,C3) :-
    card_rule1(C1,C2,C3),
    card_rule2(C1,C2,C3),
    card_rule3(C1,C2,C3),
    card_rule4(C1,C2,C3).

cards/3 just applies all the rules, with the same variables, and running this we get the answer:

?- cards(C1, C2, C3).
C1 = c(ace, diamond),
C2 = c(king, heart),
C3 = c(two, spade) ;
false.

?-

There is only one solution, but how did prolog find this solution? Though backtracking of course! Variables can only be set once and after that any attempt to set a variable to something different will fail and a different solution will be tried. To see this let's look at the three possible answers from card_rule1/3. All but one will fail when calling the subsequent rules. For example:

if rule 1 produces:

  C1 = c(king, _), C2 = c(two, _), C3 = _

This will fail on rule 3 because the ace can only be in the leftmost or middle positions, and at the moment the king or two are taking those spots.

if rule 1 produces:

C1 = c(king, _), C2 = _, C3 = c(two, _)

There is a possible answer for rule 3, but only if the ace is in the middle position. If the ace is in the middle position, then the heart must be in the right most position. This can't work because of rule 4, which has the heart to the left of the spade.
finally if rule 1 produces:

C1 = _, C2 = c(king, _), C3 = c(two, _)

There are no future conflicts with the rules. Prolog will try each combination one by one until a path to the end is found that satisfies all variables being unified with the same value.