Backtracking Algorithms

Last week I tackled n-queens, it was my first introduction to coding a backtracking algorithm. This type of algorithmic technique is best used for finding solutions step by step, building a solution and modifying it over time until there is a solution that satisfies all the current constraints. These types of algorithms are used in the 8-queens puzzle, crossword puzzles, Sudoku and some logical programming languages. Using backtracking to solve a sudoku puzzle:

1. Place a single number in each square
2. If the number that is placed cannot be in the spot we will backtrack/recurse and try the next number

Solving the problem using a backtracking algorithm is faster than attempting to generate all possible solutions, also called the naive approach. Using the backtracking technique will eliminate a lot of permutations that you would have to generate if you were to solve this puzzle with a naive approach. Iterating through a tree datatype is another example of this algorithmic technique. During the 8-queens sprint we needed to place 8 queen chess pieces on a chessboard so that none of them could attack each other. The same thought process of solving sudoku also applies here. First you place one piece then check for any horizontal and diagonal conflicts, then place the next piece. Once that piece is placed you check for more conflicts if there is one them move that piece to the next space. Each solution will be generated one square at a time and if there is a conflict we backtrack. The code below is from n-queens and is checking for any rook solutions.

findNRooksSolution = function (n) {

  //creating a new board
  let newBoard = new Board({ 'n': n });

  //iterating over the board object
  for (let col in newBoard.rows()) {

    //creating an array of row and col values
    let arr = newBoard.rows()[col];

    //placing a piece
    arr[col] = 1;
  }

Backtracking in Tree Data Structure

Starting at the root node, 1, and iterating until we get to the leaf with the value of 7. If the first node the algorithm looks at is bad it will backtrack to the parent node then go to the correct branch until the desired value is reached. Below is a code example of how this process is implemented.

treeMethods.contains = function (target, obj = this) {
  //if the target is strictly equal to the value
  if (obj.value === target) {
    //true is returned
    return true;
  }
  //checking the length of the children
  else if (obj.children.length > 0) {
    //setting default value of result to false
    let result = false;

    //iterating over the the array of children
    obj.children.forEach(child => {
      //using a recursive call to check nested nodes
      if (obj.contains(target, child)) {
        result = true;
      }
    });
    return result;
  }
}

Above is a code example of what a function that searches for a value within a tree and below is the pseudocode code thought process of the above code.

function (target) {
    if(target is equal to the leaf node){
        return true
    } else {
        forEach(child node of the current leaf node) {
            if(recursive call is true)
               return true
        }
        return false
    }
}

As mentioned previously logical programming languages such as Icon, use algorithmic backtracking to generate answers internally.