The following problem is from the Fiddler (the “spiritual successor to FiveThirtyEight’s The Riddler column”), involving the game of tenpin bowling with traditional scoring:

If you knock down 100 pins over the course of a game, you are guaranteed to have a score that’s at least 100. But what’s the minimum total number of pins you need to knock down such that you can attain a score of at least 100?

I thought this was an interesting problem, in part because traditional scoring in bowling is a bit of a mess. Every pin that you knock down scores at least one point, but some pins may yield additional bonus points… based on previously knocked down pins.

My first thought was to transform the puzzle into an integer linear programming (ILP) problem. In hindsight, the solution ends up having a nice enough form to suggest a more elegant cocktail-napkin proof. But those scoring rules are just messy enough to want some more brute-force verification from the computer. Or at least that’s what I told myself to justify the interesting coding problem.

The Mathematica code is on GitHub; it’s not much, just a few dozen lines. The solution is simple to describe: we can score at least 100 points by knocking down just 44 pins, rolling four consecutive strikes, immediately followed by knocking down four pins, and no more, for a total score of 30+30+24+14+4=102.

We certainly can’t fully brute-force the problem by examining all possible games: the number of distinct “scoreboards” in a game of bowling is

However, at the other extreme, I also wasn’t able to reduce the problem to just a single ILP instance. Not only is the total score (which we are bounding) not a linear function of the variable numbers of pins knocked down by each roll, but even the total number of pins knocked down (which we are trying to minimize) is not a simple linear function of the variables, because of the possible extra frames after a strike or spare in the tenth frame.

Instead, we can trade execution time for preserved code simplicity, by evaluating not just one ILP instance, but of them, by grouping game outcomes according to the sequence of frame “types”: strike, spare, or open. For example, the eventual solution described above occurs in a game of the form (strike, strike, strike, strike, open, open, open, open, open, open). Having fixed the type of each frame in the game, now we can describe the number of pins knocked down and the resulting total score as linear functions of variables indicating the number of pins knocked down by each roll.