Recursive Backtracking Practice Problems Online

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

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

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

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)?

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.

Concept Quizzes

Challenge Quizzes

Recursive Backtracking

Trees

Concept Quizzes

Challenge Quizzes

Recursive Backtracking