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