Xmas

The Filenes Christmas Shopping Puzzle

12 couples were waited on consecutively, as they bought a total of 8 each of the following items:

1. Aris Gloves
2. Airplane Book
3. COCO Perfume
4. Pearl Strands
5. A Football Sweater
6. A Handbag

Each husband and wife were waited on together. Each couple bought 4 items. No two couples bought the same combination of items, and none of the couples bought two or more of the same item.

Using the following clues, can you find:

• The full name of each husband and wife.
• What order they were waited on.
• What items each couple bought.

Hint: One husband is Bob, one wife is Elizabeth, and one surname is Stanton.

1. The Craigs, who bought a handbag, were waited on before the Murphys, who were not waited on last.
2. The Collins bought Aris gloves, a sweater, and handbag, and COCO.
3. The couples waited on 8th and 10th bought the Airplane Book.
4. These five couples were waited on consecutively: the Smiths; Gary and his wife; a couple who bought the Airplane Book and a handbag; the Swains; and Bill and his wife.
5. Geraldine and her husband did not buy either a handbag or a sweater.
6. The couple who were waited on last did not buy pearls.
7. One of the items Tom and his wife bought was the Airplane Book.
8. The Marshalls did not buy COCO or pearls.
9. Evelyn and her husband bought Aris gloves but not COCO.
10. These five couples were waited on consecutively: Martha and her husband; Jack and his wife; the couple who bought Aris gloves, COCO, the Airplane Book, and a handbag; the couple who did not buy either pearls or the Airplane Book; and Margaret and her husband.
11. The first five couples waited on all bought COCO.
12. Chuck and his wife did not buy Aris gloves.
13. The couples waited on first, second, and fourth did not buy a sweater.
14. Eleanor and her husband did not buy COCO.
15. Neither Allen and his wife, who did not buy a handbag, nor the Anthonys bought Aris gloves.
16. Cheryl and her husband, who were not waited on 10th or 12th, and John and his wife are two couples who bought both a sweater and a handbag.
17. The Douglases, who did not buy Aris gloves or a sweater, were waited on 9th.
18. Adam and his wife, who did not buy a handbag, were waited on immediately before the Days.
19. Steve and his wife bought pearls, the Airplane Book, a sweater, and one other item.
20. The last three couples waited on did not buy Aris gloves.
21. The Joneses did not buy a sweater.
22. Susan and her husband bought pearls.
23. George and his wife bought a sweater.
24. The four couples who did not buy Aris gloves are (in no particular order): Dorothy and her husband; the Craigs; Joe and his wife; and Rosalyn and her husband (who did not buy a sweater).
25. The O'Connors bought both COCO and a sweater.
26. Sandra and her husband, who did not buy a sweater, were waited on immediately before Cathleen and her husband.

This is the apogee of the Zebra puzzle style, so pervasive in Prolog discussions because it is well suited to the backtracking approach. All puzzles of this style can be approached in the same way:

• Let there be a an attribute template called, for want of a better name, the feasible functor (ff).
• For each attribute write a list of partially instantiated ffs for each attribute value and it's related values.
• Unify the first list with some permutation of each of the others.

That deals well with positive contraints but negative constraints (filters) have to be introduced separately.

Furthermore, it may be critical in Prolog to process constraints in a particular (but unknown) order. That problem is neatly solved by co-routines, but not many Prologs have that. Failing that, a terrible solution is to embed the whole body in a permutation routine and let it thrash until a suitable goal order is found!