# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Search through a multiway space to find special termination points

Contributed by:
Bradley Klee

ResourceFunction["DepthFirstSearch"][ performs a depth-first backtracking search from | |

ResourceFunction["DepthFirstSearch"][ searches from | |

ResourceFunction["DepthFirstSearch"][ builds the search space iteratively from | |

ResourceFunction["DepthFirstSearch"][…, continues the search through the first result, attempting to find up to | |

ResourceFunction["DepthFirstSearch"][…, returns all terminal states which satisfy | |

ResourceFunction["DepthFirstSearch"][…, bounds overly deep searches by backtracking whenever the depth equals | |

ResourceFunction["DepthFirstSearch"][…,True] returns an Association containing all results and search path data under keys "Results" and "Edges" respectively. |

Breadth-first and depth-first searches are two similar methods for brute-force solving problems of combinatorial enumeration.

A depth-first search starts at a node, and traverses from child to grandchild downward until either a solution is found, or can be shown not to exist. It will then backtrack up one level, taking the next child at that level and again proceeding downward. Whenever a given level is exhausted of possibilities it goes up a level and over to the next child.

Breadth-first searches in contrast proceed horizontally, visiting all children before going to grandchildren.

This ResourceFunction["DepthFirstSearch"] may be used effectively when only one valid solution is needed; otherwise, a breadth-first search using something like NestWhile can often get the desired results in less time. The reason is that depth-first search incurs an extra cost when backtracking, whereas breadth-first search does not need to backtrack.

ResourceFunction["DepthFirstSearch"] includes a usage that operates on directed graphs. This particular usage compares well with the System function DepthFirstScan, and can be used to obtain similar outputs (see "Properties and Relations" section below).

When traversing an input graph, the algorithm simply follows directed edges immediately to terminal nodes, backtracks to branch points, and continues to take new paths until a solution is found. In practice, this can be done by keeping a path history as a memory stack.

The two primary methods generate partial search graphs, rather than requiring a complete search graph as input. Generation of a search space is done using a state update function, either *stateUpdate* or *iterator*.

Function *stateUpdate* takes an input *state* as a first argument and draws a second argument from *levelData*. The list *levelData* is partitioned into sub-lists containing state differentials as items. An input state at level *t* is then combined with a differential from the (t+1)^{th} sub-list of *levelData* to obtain the next state. If the input *state* is inconsistent with the next differential state from *levelData*, *stateUpdate* will return Nothing. This is a failure signal, which causes the algorithm to keep searching for a valid solution. Valid solutions are obtained by combining one differential from each level of *levelData*, and they must also satisfy the test *solutionQ*.

Similarly, when a *state* is input to an *iterator*, the return is a list of candidate states or an empty list. The empty list is a termination condition, which passes the candidate solution to *solutionQ*. If the state satisfies *solutionQ* it will be returned as a positive result. If the state does not satisfy *solutionQ*, it is ignored and the search continues. As opposed to the method using *levelData*, enumerating the search space via an iterator allows solutions to be found at any depth.

The test *solutionQ* should be a function of one variable. Either it takes the name of a terminal vertex on an input graph, or it takes a terminal state created via *stateUpdate* or *iterator*. In fact, states generated by *stateUpdate* or *iterator* can be thought of as nodes on a search graph.

No two backtracking problems are exactly alike, and results can vary based on ordering of candidate states. Optimizations can often be found by including heuristic-based state selection in either *stateUpdate* or *iterator*.

Find a terminal leaf on a binary search tree:

In[1]:= |

Out[1]= |

Find all terminal leafs on a binary search tree:

In[2]:= |

Out[2]= |

Depict the search up to three leafs:

In[3]:= |

Out[3]= |

Find a partition of the first seven integers into two sets with equal sums:

In[4]:= |

Out[4]= |

Find another solution to the same problem:

In[5]:= |

Out[5]= |

Find all solutions:

In[6]:= |

Out[6]= |

Find a Hamiltonian path along the edges of a cube:

In[7]:= |

Out[7]= |

Depict a search for the deepest leaf of a random TreeGraph:

In[8]:= |

Out[8]= |

Find and depict 20 results at depth less than or equal to 10:

In[9]:= |

Out[9]= |

Highlight a search Graph according to its progress in finding All results:

In[10]:= |

Out[10]= |

Compare with DepthFirstScan:

In[11]:= |

Out[11]= |

List all possible partitions of integer 10 into three lesser integers:

In[12]:= |

Out[12]= |

Another way to solve the same problem:

In[13]:= |

Out[13]= |

Prove non-minimality of the first method:

In[14]:= |

Out[14]= |

Undirected graphs have no terminal nodes, so are disallowed:

In[15]:= |

Out[15]= |

If the search space is cyclic, the search can possibly hang:

In[16]:= |

Out[16]= |

Introducing a cut-off limits the number of loops a search can go through:

In[17]:= |

Out[17]= |

To find all relevant results, it may be necessary to search from multiple initial conditions:

In[18]:= |

Out[18]= |

Find a 10×10 periodic pattern to be consistent with five binary templates:

In[19]:= |

Out[19]= |

Highlight the depth-first, single-result search as a subgraph of the comprehensive search graph:

In[20]:= |

Out[20]= |

Find and depict a symmetric arrangement of 8 non-attacking queens on a standard chess board:

In[21]:= |

Out[21]= |

Find and depict a Knight's tour around a 5×5 board:

In[22]:= |

Out[22]= |

Search for a corner-to-corner path across a RandomSierpinskiMaze:

In[23]:= |

Out[23]= |

Optimize the search by introducing a "North-first" heuristic:

In[24]:= |

Out[24]= |

- 1.0.0 – 25 July 2022

This work is licensed under a Creative Commons Attribution 4.0 International License