Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BacktrackSearch

Source Notebook

Solve computational problems using a generic backtracking algorithm

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["BacktrackSearch"][s,ptest,test]

performs a backtrack search of the solution space s, expanding a partial solution for as long as ptest gives True and returning the first valid solution satisfying test.

ResourceFunction["BacktrackSearch"][s,ptest,test,n]

attempts to return n solutions.

Details and Options

ResourceFunction["BacktrackSearch"] starts with a smallest possible configuration and incrementally adds elements to it until a partial solution yields a valid solution; or abandons a candidate as soon as it determines that it cannot possibly be completed to a valid solution.
ResourceFunction["BacktrackSearch"] can be much faster than brute-force enumeration of all complete candidates, since it can eliminate many candidates with a single test.
ResourceFunction["BacktrackSearch"][s,True&,…] performs a brute-force search.
Count n can be a positive integer or All.

Examples

Basic Examples (3) 

Use backtracking to find a way to partition an integer n into k smaller integers:

In[1]:=
n = 10; k = 3;
In[2]:=
ResourceFunction["BacktrackSearch"][Table[Range[n - 1], {k}], Total[#] <= n &, Total[#] == n &]
Out[2]=

Find two possible partitions:

In[3]:=
ResourceFunction["BacktrackSearch"][Table[Range[n - 1], {k}], Total[#] <= n &, Total[#] == n &, 2]
Out[3]=

All partitions:

In[4]:=
ResourceFunction["BacktrackSearch"][Table[Range[n - 1], {k}], Total[#] <= n &, Total[#] == n &, All]
Out[4]=

Version History

  • 1.0.0 – 23 March 2020

License Information