What size of puzzle is appropriate?

Question

I am making a puzzle based on a Project Euler problem. Here is the puzzle at present:

What path in the triangle below, starting from the top number with each step moving to one adjacent number in the next row, gives the greatest possible sum?

      35
    12  80
  88  79  96
73  56  20  55

The intended solution to this problem is to, in the second-last row, draw an arrow from the greater of the two to the bottom. Then replace the number with the sum of those numbers, as follows:

       35
     12  80 
  161 135 151
 ↗    ↗      ↖
73  56   20   55

When this process is repeated until the top row, it will give the best path. In this case, 35 to 80 to 96 to 55 is the best path.

I feel that this puzzle is too easy, however. There are only so many paths and it's very easy to see which ones couldn't possibly be best. It's definitely possible to solve this without finding the "correct" solution. The obvious solution is to add more rows, but adding too many would require a lot of arithmetic. Already 6 additions must be performed to solve the puzzle, and puzzles get boring if there are too many additions. Five rows would require 10 additions and six rows would require 15.

Should I keep the puzzle at four rows, or increase its size? Is there general advice as to how large a puzzle should be?

Answer 1

Determining an "appropriate size" for a puzzle is all about determining what constraints you consider "appropriate", and then finding a puzzle that fits those constraints.

In your case, you are given a pyramid with $n$ levels, designed in such a way that the dynamic programming approach to the problem requires $\binom{n}{2}$ additions, but there are $2^n$ possible paths in total.

You can make a table of values for this:

$$\begin{matrix} n & \binom{n}{2} & 2^n\\ 4 & 6 & 16 \\ 5 & 10 & 32 \\ 6 & 15 & 64 \\ 7 & 21 & 128 \\ \end{matrix}$$

I personally feel that doing about 10 or 15 additions shouldn't be a problem, so you could get away with a six-row pyramid. However, you seem to feel that this is too much.

Sometimes, the bounds you provide mean that there are no appropriate sizes for the puzzle because they don't require you to see the trick behind it. It just means that that type of puzzle is probably off-limits to your audience.

Answer 2

I'm going to look at your question from a slightly different angle, and argue that there is no correct size for this puzzle; the question isn't a function of the quantity of solving work that's done here, but its very nature.

To my mind, the core issue with the triangle-path problem as a 'human' puzzle is that it's a little too mechanical: there's a relatively straightforward linear-time algorithm that gives the solution. It may take a little while to discover the algorithm, but once you do, no puzzle of this form is going to give you any additional insight over the first; you just have to apply the solution steps that you've determined to the new instance. (For an example of a released puzzle game with this problem, look at Strata on iOS or Mac; the game looks stunning, but the puzzles lose their long-term satisfaction once the algorithm is discovered.)

By contrast, the puzzles that retain long-term appeal tend to be those that are algorithmically hard; that is, those for which no (known) 'fast' algorithm exists, and where good algorithms are conjectured not to exist at all. For instance, Sudoku is known to be NP-complete, and Rush Hour is known to be PSPACE-complete — while both puzzles are susceptible to 'smart' approaches that use knowledge to bound the search space, they're also both (presumably) hard enough that there's no straightforward mechanical approach to solving them that doesn't involve prohibitive amounts of time.

Essentially, making your puzzle larger would make it take longer to solve — but it wouldn't make it any harder, only force the Solver to spend more time on it repeating the same steps. That's an issue inherent to the puzzle itself, and not one that making it larger can address.