This one took me a while, largely because I didn’t understand what they meant by backtracking. I was thinking of backtracking to a particular point, so I kept trying to use acyclic graphs, sometimes called forests. That’s not really what they meant, though. In the context of Problem 15, no backtracking just means you can’t go up and you can’t go left. After working a 3x3 version of the problem, I thought the values looked a little familiar; I was right. It’s a counting problem we covered in combinatorics oh so many years ago: Permutations with Repeated Elements. There are 40 steps to any given path (we have to go 20 steps down and 20 steps right). Since the definition of backtracking makes any given move down indistinguishable from any other move down, and any given move right indistinguishable from any other move right, the answer is 40!/(20!20!).

Back to flipping out…