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.factorcode.org/tags/backtrack.html

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.factorcode.org/tags/backtrack.html

This documentation was generated offline from a
`load-all`

image. If you want, you can also
browse the documentation from within the UI developer tools. See
the Factor website
for more information.

Factor 0.101 x86.64 (2284, heads/master-29a92525f9, Nov 9 2024 06:55:18)