[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

Find the largest and smallest paths through the number grid as you move from 'S' to 'F'.   Paths can move straight or diagonally to the right but never to the left.

Source: Math and Logic Puzzles for PC Enthusiasts, J. J. Clessa, Dover Books.

Background & Techniques

I believe this is our first excursion into graph searching here - but  not our last.   I know of no way to solve this problem without examining all paths and selecting those with the largest and smallest sums.     Grids up to 13 by 13 are supported and solved in about a second.  

In simple terms, a graph is a set of points or numbers (called vertices) and some rules for connecting them (called edges).  Mazes are graphs - each box is a vertex and the openings for next moves are edges.  Many games can be treated as graphs  where the game states  (how the board looks at any point in the game) are vertices and the moves define the edges.  

The search technique implemented here is a "depth first" search which follows each path as far as possible before trying the next.   In this case we can always proceed from S all the way to F, in other applications (for example maze solving) it may not be possible to get to the target vertex along any particular path.  

 In other games and puzzles, it may be advantageous to use a "breadth first" search, where we explore all of the adjacent vertices and select the "best" one in order to arrive at a solution faster.   

Recursive calls to procedure GetPath are made, each call checking the vertices that are up and right, straight across right and down and right - the three possible paths from any vertex.    A Stringgrid is used to display results.  An option is provided using Stringrid's OnDrawCell event exit  to animate the searching algorithm so you can watch the paths as they are tested.   

The board is a doubly dimensioned dynamic array of integers.  It is sized with boardsize+2 elements each way so that we can keep an outline of 0's around the numbers in order to simplify testing when we  reach an edge.  

If there is anything else unclear, send me an email.

Addendum:  There is now a Graph Searching page in Math Topics section 

Addendum December 12, 2008:  This program is one of the first postings on DFF; about a month after the  site opened. if September, 2000.  A sharp viewer recently pointed out that there is a faster way to find the largest and smallest sums than searching all paths .   We can construct a second cumulative sum array with each value replaced by the minimum (or maximum) sum path to that point.  This is easily done by examining column values from left to right.  In column 1, the values represent the smallest sum paths.  For each successive column, the smallest  sum for a cell is that value plus the smallest of the 3 sum cells from the previous sum column which could lead to this cell.   By the time we fill the rightmost column, the smallest  value in that column is the minimal path sum.  Repeating the algorithm replacing "smallest" with "largest" sum values will a

 Version 2, posted today implements   this strategy.  It is several hundred times faster than exhaustive search for the larger arrays tested here.   The viewer, who happens to hold a PhD in Mathematics, pointed out that run times for the sum technique grows in polynomial time as opposed to exponential growth for exhaustive search.   In a speed contest for N things, running in time N^X will always win out over things running in Y^N time for large N regardless of the values of X and Y.   There's a whole branch of mathematics dealing with the "Analysis of Algorithms"  which uses "Big O" functions to describe such run time characteristics. 

Running/Exploring the Program

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.