Waste less time on Facebook — follow Brilliant.
×

Trees

Whether you're working with a road map or just some numerical data, organizing data in trees allows for an efficient representation of connections and hierarchies.

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.

main image

main image

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

Problem Loading...

Note Loading...

Set Loading...