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