The backtrack vocabulary implements simple non-determinism by selecting an element of a sequence, performing a test and backtracking to select the next element if the test fails.

Find a first successful element:

Find all combinations of successful elements:

Select elements from a sequence:

Examples

Let's solve the following puzzle: a farmer has some chickens and some cows for a total of 30 animal, and the animals have 74 legs in total.

The output means there is only one solution: the farmer has 23 chickens and 7 cows. If we want to only find the first solution, the following approach could be used:

See more examples here: https://re-factor.blogspot.com/search?q=backtrack

Find a first successful element:

if-amb ( true false -- ? )

Find all combinations of successful elements:

amb-all ( quot -- )

bag-of ( quot -- seq )

Select elements from a sequence:

amb ( seq -- elt )

amb-lazy ( seq -- elt )

Examples

Let's solve the following puzzle: a farmer has some chickens and some cows for a total of 30 animal, and the animals have 74 legs in total.

: check ( chickens cows -- ? )
[ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;
[
1 30 [a,b] amb 1 30 [a,b] amb
[ check must-be-true ] [ 2array ] 2bi
] bag-of .

V{ { 23 7 } }

V{ { 23 7 } }

The output means there is only one solution: the farmer has 23 chickens and 7 cows. If we want to only find the first solution, the following approach could be used:

: check ( chickens cows -- ? )
[ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;
[
1 30 [a,b] amb 1 30 [a,b] amb
2dup check must-be-true
"%d chickens, %d cows\n" printf
t
] [ "No solution." print ] if-amb drop

23 chickens, 7 cows

23 chickens, 7 cows

See more examples here: https://re-factor.blogspot.com/search?q=backtrack