Function Repository Resource:

# BacktrackSearch

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]:=
 In[2]:=
 Out[2]=

Find two possible partitions:

 In[3]:=
 Out[3]=

All partitions:

 In[4]:=
 Out[4]=

## Version History

• 1.0.0 – 23 March 2020