🧭 Branching: How Qaekwy Explores for Solutions
Imagine you’re in a giant maze (search space of variables’ possible assignments), and you’re looking for the exit (the solution). At each intersection, you have to decide which way to go. This is exactly what branching is.
What is Branching?
When the solver gets stuck and can’t figure out what to do next, it has to make a guess. This guess is called a branch.
For example, if a variable x can be any integer from 1 to 10, a branch could be to try x = 5. The solver then sees what happens. Does it lead to a solution? A dead end? Or another intersection where it has to make another guess?
If a guess leads to a dead end, the solver backtracks (goes back to the last intersection) and tries a different path (e.g., x != 5).
Why is Branching Important?
The way the solver makes these guesses can make a huge difference in how fast it finds a solution. A good branching strategy is like having an approximative map of the maze. A bad one is like wandering around randomly.
The Two Parts of a Branching Strategy
A branching strategy has two parts:
- Variable Selection (for arrays): Which variable should we guess a value for? It’s often a good idea to pick the variable with the fewest options, because it’s more likely to lead to a dead end if we make the wrong guess.
- Value Selection: Once we’ve picked a variable, which value should we try first? Sometimes it’s best to try the smallest value, sometimes the largest, and sometimes a value in the middle.
Branching in Qaekwy
Qaekwy lets you choose the branching strategy for each variable. This means you can give the solver hints on how to best explore the maze of your problem.
For a list of all the branching strategies you can use, check out the API Reference for Branching.