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

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

That is, 2+4+5+9=202 + 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×nm \times n matrix AA with 00's and 11's. The matrix represents a maze. The aim is to move from any starting position (x,y)(x,y) to the position (m1,n1)(m-1,n-1) following the path's of 11'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×NN \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=5N = 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)(x,y). For example, (0,0)(0,0) and (0,4)(0,4) are the top left and top right cells in the board respectively.
×

Problem Loading...

Note Loading...

Set Loading...