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

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

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.

      14      
    23 27 17    
  03 09 05 11 05  
 S 11 21 12 04 23  F
  23 05 01 08 16  
    19 21 07    
      06      

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 NX will always win out over things running in YN 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

bulletDownload source 
bulletDownload  executable  

Suggestions for further exploration

Dec. 2008 Done! 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.  

Dec 2008 Done! 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.  

Dec. 2008 DoneI 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: May 18, 2009

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2013, Gary Darby    All rights reserved.