Quantitative Finance

# Recursive Backtracking

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is $20$.

 1 2 3 4 2 4 1 5 2 4 3 9 0 5 

That is, $2 + 4 + 5 + 9 = 20$.

Devise a backtracking solution to find the maximum total from top to bottom of the triangle below:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 9 75 59 57 51 32 63 14 83 29 67 93 35 21 87 9 21 56 3 58 87 10 86 100 15 27 68 46 85 95 54 5 22 60 2 51 33 7 9 62 29 13 3 24 2 17 54 23 59 81 59 54 24 2 100 19 29 63 37 25 75 31 17 2 81 78 21 96 67 59 2 72 60 64 4 66 8 82 51 67 52 30 64 80 14 85 89 98 82 70 9 58 88 23 16 56 52 68 65 89 56 87 43 2 37 61 64 59 56 28 25 63 93 91 43 85 41 99 83 81 

Suppose you are given an $m \times n$ matrix $A$ with $0$'s and $1$'s. The matrix represents a maze. The aim is to move from any starting position $(x,y)$ to the position $(m-1,n-1)$ following the path's of $1$'s, when you are only allowed to move to directly adjacent squares.

Write a program to determine the existence of such paths and apply it to the following text file. Which of the (row, column) pairs in our options are connected to position (m-1, n-1)?

Select one or more

You are given an $N \times N$ chess board, empty but for a single knight. Write a program that determines the existence of a series of a legal knight moves that result in the knight visiting every square on the chessboard exactly once. The program is given only the starting coordinate of the "tour" as input.

Suppose $N = 5$. Which of the following starting points will not lead to a valid knight tour?

Details and assumptions

• A coordinate is just a tuple of two numbers $(x,y)$. For example, $(0,0)$ and $(0,4)$ are the top left and top right cells in the board respectively.
×