Backtracking
Backtracking is the act of finding a set solution through looping over possibilities and adding each one to a possible solution, if the added value breaks our possible solution we want to remove the value and move to the next possibility. It can be incredibly useful for bringing us solutions to complex puzzle problems.
Wikipedia defines our backtracking as “a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.”
What would it look like?
Your basic layout is gonna look something like this where your adding a solution and if it’s no longer passing remove it. This method is fairly popular and not too complicated should your helper functions working properly.
To have some sort of basic psuedocode order of operations
root, reject, true only if the partial candidate is not worth completing.
accept the val, next generate the next alternative extension of a candidate, after the extension and we get our output.
function(){
let soulutionSet = []
soulutionSet.forEach(ele, i => {
soulutionSet[i] = 1
if (!comparison(solutionSet)){
solutionSet[i] = null;}})
};
When to use?
It’s best to save using this method when looking to solve constraint satisfaction problems such as n queens, sudoku, getting directions. There’s plenty of ways to solve them but the friendliest and cleanest from my experience working on n queens has been through applying backtracking.
