Title: Find the highest value path through a two-dimensional array of numbers in C#

This method is similar to path-finding methods described in my books Essential Algorithms: A Practical Approach to Computer Algorithms and Interview Puzzles Dissected, Solving and Understanding Interview Puzzles. Follow those links for more information including tables of contents.

Look at the picture at the top of this post. The goal is to find a path through the array of numbers from the first row to the last row. When moving from one row to the next, you can move one column left or right, or keep the same column as the row above. The goal is to find the path that maximizes the total of the numbers visited.

The following code shows how the program makes the array of numbers when you click the Make Numbers button.

private void btnMakeNumbers_Click(object sender, EventArgs e) { NumRows = (int)nudNumRows.Value; NumCols = (int)nudNumCols.Value; Numbers = new int[NumRows, NumCols]; Random rand = new Random(); for (int row = 0; row < NumRows; row++) { for (int col = 0; col < NumCols; col++) { Numbers[row, col] = rand.Next(1, 99); } } BestPath = null; // Display the numbers. DisplayNumbers(); // Enable the Find Path button. btnFindPath.Enabled = true; lblTotal.Text = ""; }

The code reads the number of rows and columns you entered and then randomly generates the array of numbers. It then calls the DisplayNumbers method to display the numbers. I'll describe that method after I explain how the program generates the best path.

The following FindBestPath method finds the best path through the array.

// The best path. private int[] BestPath = null; private int BestTotal = int.MinValue; // Find the best path. // Return the path's total value. private int FindBestPath() { // Make a test path, one entry per row. int[] test_path = new int[NumRows]; // Start in row 0 and try each column. for (int col = 0; col < NumCols; col++) { test_path[0] = col; FindPath(test_path, 1); } // Return the best total. return BestTotal; }

The method starts by creating a test_path array with one entry per row. This array will eventually hold the column used in each row.

The program then tries using each column as the first visited. For each column, it fills in that column's number in test_path[0] and then calls the following FindPath method to explore solutions that begin with that first column.

// Recursively explore paths starting with the indicated row. // Return the path's total value. private void FindPath(int[] test_path, int row) { // See if we have a complete solution. if (row >= NumRows) { // We have a complete solution. // See if it is better than the best solution so far. int total = 0; for (int r = 0; r < NumRows; r++) total += Numbers[r, test_path[r]]; if (total > BestTotal) { // This is an improvement. BestTotal = total; Array.Copy(test_path, BestPath, NumRows); } } else { // We don't have a complete solution. // Try the possibilities for this row. // Get the column used in the previous row. int prev_col = test_path[row - 1]; // Column - 1 if (prev_col > 0) { test_path[row] = prev_col - 1; FindPath(test_path, row + 1); } // Column test_path[row] = prev_col; FindPath(test_path, row + 1); // Column + 1 if (prev_col < NumCols - 1) { test_path[row] = prev_col + 1; FindPath(test_path, row + 1); } } }

The FindPath method does the most interesting work when it recursively fills in the test_path array. When the array is completely full, it checks the test solution's value to see if it is an improvement over the current best solution.

The method starts by checking its row parameter to see if the test solution is complete. If row >= NumRows, then the method has been called to fill in the entry for the row after the last row in the array. That means the test array is full, so the solution is complete. The method adds up the total value of the solution, compares it to the best solution found so far, and saves it if this is an improvement.

If the test solution is not complete, the method tries each of the three possible allowed values for the column in this row and then recursively calls itself to try values for the rest of the test solution's rows.

Eventually the recursive calls fill in all of the rows' values and the previous case occurs, ending the recursion.

That's all there is to finding the best solution. The following code shows how the program displays the numbers and the best solution, if it has found one.

// Display the numbers and the best path. private void DisplayNumbers() { // Display the numbers. string txt = ""; for (int row = 0; row < NumRows; row++) { txt += Environment.NewLine; for (int col = 0; col < NumCols; col++) { txt += string.Format("{0,3}", Numbers[row, col]); } } txt = txt.Substring(Environment.NewLine.Length); rchNumbers.Text = txt; // Display the best path. if (BestPath == null) return; rchNumbers.Select(); rchNumbers.SelectionBackColor = Color.White; for (int row = 0; row < NumRows; row++) { int start = 1 + row * (NumCols * 3 + Environment.NewLine.Length - 1) + BestPath[row] * 3; rchNumbers.Select(start, 2); rchNumbers.SelectionBackColor = Color.LightGreen; } rchNumbers.Select(0, 0); // Display the best path in the Console window. for (int row = 0; row < NumRows; row++) Console.Write(Numbers[row, BestPath[row]] + " "); Console.WriteLine(""); }

This code first loops through the numbers a builds a multiline string that contains them all. It sets the rchNumbers RichTextBox control's Text property to the result.

After highlighting the solution, the method moves the RichTextBox control's selection point to the beginning of the text so nothing is shown as selected. It finishes by displaying the values selected in the best solution in the Console window so you can verify that the highlighted values match the best solution.

This technique of building a solution by recursively trying every possibility for each of the required entries is quite powerful. You can use this method to solve many hard problems, although it requires you to look at a lot of potential solutions so it only works for relatively small problems. (My books talk more about this and explain some approaches you can use to solve larger problems.)

Download the example to experiment with it and to see additional details.