### Search

 Search WWW Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

Support DFF - Shop

If you shop at Amazon anyway,  consider using this link.

We receive a few cents from each purchase.  Thanks

### Support DFF - Donate

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.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

(Hint: If you can wait, current year calendars are usually on sale in January.)

### Contact

 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.