×
Computer Science

# 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. Write a program to determine the existence of such paths and apply it to the following text file.

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.
×