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

 

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.

Contact

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

Search DelphiForFun.org only

 

 

 

Solution spaces for puzzles and games are often represented as graphs.   The nodes, or vertices, are valid board configurations and the edges represent moves from one board to another.    Consider the game of tic-tac-toe for example.  We can assign X,O,or E (empty) to each of the 9 playing positions and represent any board configuration as a string of 9 of these characters (XEEEEEEEE represents player1 placing an X in the upper left corner).  The maximum number of nodes is 39, but many of these are invalid.   It is an interesting problem to calculate the number of nodes for a graph of TicTacToe and a program TicTacToeCount which does this is included in the download.  According to my count, there are slightly more than 6000 valid board positions.         

There are many more practical applications of graphs but for our purposes puzzles will do.   Complete graphs are only feasible for relatively small problems - another example is the Sliding Coins puzzle.  A program allowing users to solve the puzzle has already been posted in the Programs section of this site.  In this article, we'll explore the theory and provide a program that finds solutions to the Sliding Coins puzzle by searching.  

First let's figure out how to represent the puzzle in graph form.   One common technique is an Adjacency Matrix or Edge matrix.  If a graph with N nodes is written as an N x N matrix, the intersection of each row and column can flag  existence of an edge between them, or contain a value representing the length (or cost) of the edge (or move).    The Edge Matrix reserves space for an edge between any two nodes.  If the number of actual edges is small then, a lot of space is wasted.   

This is typically the case with board puzzles - from any given configuration, only a few positions can be reached on the next move.  For these cases, an good alternative data structure is the Adjacency List.   Here we make a single master list of all nodes.  Each entry in the list will contain the identifier of the node, and a list with pointers to all adjacent nodes.   This is the model we'll be using here.  

A simple graph with 10 nodes (1-10) and 11 edges.  Edges  nodes adjacent to any node  (1,2), (1,3).  The sample program, SimpleGraph, uses this graph to search all paths from Node #1 to Node #10. The Adjacency list looks like this:

Head Nodes

Node 1
Adjacents (2,3)
Node 2
Adjacents (1,4,5)
Node 3
Adjacents (1,6,7,10)
etc.

For our master list of all nodes in Delphi we use a TStringlist derivative named TGraphList.  It has the advantage of flexibility - the keys identifying our nodes will be strings which can have unlimited length.  We can easily sort the resulting list, this allows efficient retrieval with  the Find method.  Find uses a binary search  to retrieve members from a sorted list.   And a Stringlist has an Objects property to hold the nodes.  The nodes themselves are represented in a TNode container object  with lists of pointers to adjacent nodes.   

We'll investigate 2 techniques to search this structure: depth first search and breadth first search.  Each has its advantages and disadvantages.  Depth first is fast if we limit the depth, but short solutions are not necessarily found first.   Breadth first will always find the minimum length path first, but it's run time can get very long.   The routines described here differ from the standard depth-first and breadth-first traversing routines found in texts,  Those routines typically are concerned with visiting all nodes in a certain order, not in finding paths from A to B.   

Depth first follows a node downward to its 1st adjacent node, then to the 1st adjacent node of that one, until something stops the search.  We'll then backtrack and follow  next adjacent of the predecessor, etc.   This is a naturally recursive operation since for each node we need to perform exactly the same operation each of its adjacents. We'll use a logical stack where retrieval always returns the most recent addition to the list  (called last In, first out, LIFO retrieval). 

Here is the pseudocode for depth first search: 

SearchGoalDF(nodenbr, goalkey, maxdepth) - search depth first for all solutions from nodenbr node to goalkey node with depth of maxdepth or less.

bulletSet visited array to false, visited has an boolean entry for each node.
bulletclear stack
bulletpush nodenbr node onto stack
bulletcall dfs
bulletend.

dfs

bullet

pop (retrieve and delete)  most current stack entry, temp.

bulletmark temp as visited.  {to avoid looping back here as we search on down}
bulletif  temp.key=goalkey then notify caller of solution found
bulletelse if stack.count<maxdepth then for each  node in temp's adjacency list, 
bulletpush adjacent[i] onto stack
bulletcall dfs
bullet mark temp as unvisited {there might be another path through this node to a solution}
bulletend.

Notice that  if A is adjacent to B, the B is normally also adjacent to A and we must handle the case where we would loop from A to B to A to B, etc.  We prevent this with a Visited array that has a flag set when we visit a node so that we do not  revisit it while searching down this path.  When we backtrack we "unvisit" the node because the next path found may  want to include this node also.    

The something that finally stops the search may be visiting all of the nodes, or  some preset limit of how far to search,  or a target node and  no more paths are needed.  This last stopping method is not implemented here, but could be used for a "find any path" scenario.    

The breadth first search  uses a queue list structure where each retrieval returns the node that has been on the queue the longest (first in, first out - FIFO retrieval).  The effect of this is to process all nodes adjacent the start node before we process the nodes adjacent to those nodes, etc.  We have a new problem introduced by breadth first searching - when we finally get the goal node, we have no idea of how we got there!   In the depth first search, each addition was the next node processed and  the stack was the path for each solution found.  For breadth first, we just throw those adjacents onto the queue to be visited some time later.  We'll solve this problem by introducing a new TBreadthObj than contains the node and the path that got us there.  These objects will become the queue objects as we search.   Pseudocode looks like this:

SearchGoalBF(nodenbr, goalkey, maxdepth) - search breadth first for all solutions from nodenbr node to goalkey node of length maxdepth or less.

bulletclear queue
bulletbuild a breadthObj for nodenbr with an empty path, call it temp 
bulletpush temp onto queue
bulletwhile queue is not empty do
bulletget oldest breadthObj from queue, call it temp
bulletdelete temp from queue
bulletif temp.node.key=goalkey then notify caller of solution {pass temp.pathinfo back as the solution}
bulletelse for each adjacent do, if adjacent is not already  in the path then do
bulletcreate a new breadthObj, temp2
bulletcopy adjacent[i] node info and temp pathinfo to temp2
bulletadd temp.node to temp2.pathinfo (the path  grows by one node)
bulletadd temp2 to queue
bulletfree temp
bulletend.

This logic has been incorporated into  TGraphList  in a unit named UTGraphSearch.  Two sample programs are included , one, SimpleSearch, builds a graph with the 10 nodes and 11 edges  described above,   and  searches for ways to get from node #1 to node #10.    The second program, CoinSearch,  searches for solutions to the Sliding Coin puzzle.  

Addendum: October 27, 20005: UTGraphSearch has been add to our common DFF Library file, so a one-time download of the current library version (DFFLIBV04 or later) is required to compile the test programs described here.  Although not used here, there are several changes to UTGraphSearch in preparation for interactive applications:

bulletVertex objects now contain x,y location information.
bulletProcedure Finalize which sorts vertices and assigns index values was previously called after all nodes were built and before edges were added.  It is now called whenever necessary (e.g. adding an edge after adding a vertex).
bulletNew methods to support interactive operations: MoveNode, DeleteNode, DeleteEdge, CloseToEdge,  SetHighLight, ResetAllHighlight, LoadGraph, and SaveGraph.

Download and Explore

bulletDownload source code from here.
bulletDownload current DFF Library file (DFFLibV15 ).

   

bulletDownload Lazarus Source
bulletDownload current DFF Lazarus Library Source(DFFLazLib01)
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.