Puzzles for Programmers and Pros

6.13. Winning at the Slots

Heuristics help to move through a search space based on cost and perhaps enlightened greed (as in simulated annealing). Sometimes you don't control the size of the search space, however, or there are winning configurations and losing configurations and nothing in between. In such cases, you might still do better than a brute force exhaustive search if there is structure in the winning configurations.

A field known as combinatorial design can help. The idea is that even if you don't test the full search space, perhaps you can be systematic in some sense at least. For example, perhaps you can guarantee that every value of every parameter is tried at least once. Usually, that's insufficient. Perhaps you can ensure that every combination of values of every pair of parameters is tried once. In this puzzle, we look for triplets.

Consider a special slot machine with five wheels. One has four different values. The others have three each.

wheel 1: apples, cherries, grapes, pears

wheel 2: cherries, grapes, pears

wheel 3: apples, grapes, pears

wheel 4: apples, cherries, pears

wheel 5: apples, cherries, grapes

In this machine, the player sets the wheel values, then pulls the lever. If it's a winning combination, the payout is $500. Each pull of the lever costs $10. The winning combination depends on only three wheels. You don't know which three, but you know that the first wheel is one of them. If you are lucky enough to find the correct values of the correct three ...