Recursive Backtracking
To put it simply, the idea behind backtracking comes down to trial and error. If you can't think of a way to jump to finding the solution to a problem, there is always the strategy of just trying different things until one of them works. When you search for a solution, try a possibility; if you find yourself stuck, back up and try the next one. Repeat until you find a viable solution.
In a general algorithm this looks something like:
1. Have I arrived at a viable solution?
1a) Yes: return true! (or whatever makes sense for a successful outcome)
1b) No: So where can I go from here? Choose an alternative and go there. Is this new path a solution? This is where the recursive call comes into play - restart the algorithm from the new location.
2. Are there any remaining alternative routes? If there are, choose one and start over.
3. Finally, when I am out of places to go, return false (or whatever makes sense for a termination outcome)
I'll apply this logic to two examples:
Rock, Paper, Scissors
This problem asks you to write a function that generates every sequence of throws a single player could throw over a three-round game of rock-paper-scissors. The output should look something like:
[["rock", "rock", "rock"],
["rock", "rock", "paper"],
["rock", "rock", "scissors"],
["rock", "paper", "rock"],
...etc...
At first glance, this could easily be solved by nesting 3 for-loops together, one for each round:
var rockPaperScissors = function () {
var options = ["rock", "paper", "scissors"];
var result = [];
for (var i = 0; i < options.length; i++) { // for each option
for (var j = 0; j < options.length; j++) { // loop through the other options
for (var k = 0; k < options.length; k++) {
var combination = [options[i], options[k], options[j]];
result.push(combination);
}
}
}
return result;
};
But what if we don't know how many rounds there will be? This can be solved through recursive backtracking by starting off with an empty array, and each time checking if the length of that array has built up to the number of rounds specified in the arguments to the function. Until then, an inner function looks through all of the options and calls itself, passing the growing results array.
var rockPaperScissors = function (rounds) {
var options = ["rock", "paper", "scissors"];
var result = [];
rounds = rounds || 3;
var findOutcome = function (playedSoFar) {
// recursive to find all possible combinations
if (playedSoFar.length === rounds) {
return result.push(playedSoFar); // .push() returns length of resulting array
} else {
for (var i = 0; i < options.length; i++) {
findOutcome(playedSoFar.concat(options[i])); // concat adds a val or an array to an array
}
}
};
findOutcome([]);
return result;
};
N-Queens
This algorithm returns the number of nxn chessboards that exist, with n queens placed such that none of them can attack each other. In the below implementation, there are a couple of helper functions I refer to. Firstly, the board passed in is just a 2D array representing an n by n matrix filled with 0's. togglePiece() simply changes the cell at the given column and row to 1 or 0, depending on what it was before. hasAnyQueensConflicts() is the culmination of a number of checks up and down the columns, and across the board diagonals, checking for any other queens already placed on the board and returning true if any conflicts exist.
As you can see, it actually follows quite a simple pattern. True to the recursive backtracking general pattern, we start by checking for a successful case - if we have reached the last column, it must mean that we have created a board without collisions, and should add to the count of solutions.
The problem is recursively being divided into the sub problem of placing single queen on the chess board. Then, to identify if the toggled queen resulted in a solution, we can check whether any of the already placed queens attack this position. If yes, then it's safe to move to the next column. If no conflict exists, then place the queen and move on to placing the next queen (i.e. the next row).
var solveNQueens = function (column, n, board) {
if (column === n) {
count++;
return;
}
for (var row = 0; row < n; row++) {
board.togglePiece(row, column);
if (!board.hasAnyQueensConflicts()) {
solveNQueens(column + 1, n, board);
}
board.togglePiece(row, column);
}
};
solveNQueens(0, n, board);