[Home]   [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 

Running/Exploring the Program

	Currently, the numbers in the largest and smallest path are saved and listed, but not the actual path.  It would be good to change the path arrays to be arrays of points (columns and rows).  This would let us show the max and min paths in color (say green and red)  after the solution was known.
	I'm sure the algorithm could be speeded up some.  Maybe a faster way to copy the input path to the output path inside of the GetPath routine.  The program currently uses dynamic arrays - this would be a good chance to see the speed effect of changing to fixed size arrays.
	I just noticed that the program will generate and solve grids up to 15X15, but only displays properly for 13X13.  You might want to fix the display grid so that the 15X15 case shows OK.  (It has 600,000+ possible paths and is solved in about  8 seconds on my 433 mhz Celeron system - so larger sizes are problematic).

 

Created: October 25, 2000

Modified: July 21, 2006

 

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

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