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

by Brilliant Staff

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.

Show explanation
View wiki
by Brilliant Staff

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.
Show explanation
View wiki
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...