preface

I haven’t seen you for a long time. I miss you very much. Due to some things, I delayed the update of my blog in September. What Koizumi wants to talk about today is the backtracking algorithm.

define

Here’s how backtracking is defined on Wikipedia.

Backtracking is one of the violent search methods. For some computational problems, backtracking is a general algorithm that can find all (or part) of the solutions, especially for constraint compensation problems (when solving constraint satisfaction problems, we gradually construct more candidate solutions, In addition, after confirming that a certain part of the candidate solution is impossible to complete the correct solution, we give up searching for this part of the candidate solution itself and its sub-candidate solutions that can be developed, and turn to testing other part of the candidate solution).

As you can see from the above definition, backtracking actually traverses all possible solutions to the problem. And according to the definition of backtracking, backtracking algorithm, its solution is the “trial and error”, according to step in one direction layer upon layer thorough, if found a step error (i.e., have been unable to solve problems or do not meet the conditions) to solve the problem, will return to the previous step, how to decide the next go, continue to the next step to conversely. You end up with two outcomes:

  1. Search for all solutions that meet the problem criteria
  2. There is no solution to the problem that meets the conditions

Then, according to the definition of backtracking algorithm and previous experience in learning DFS, we can propose three elements of backtracking algorithm:

  1. Paths
  2. Choose
  3. Condition (Condition)

1. The path (Paths)

Before solving the problem, you need to know what are the “next” paths available at the current stage? List available paths.

2. Choose (Choose)

Once you know the alternative paths, you need to make path selection. You can select only one path before the rollback.

3. Conditions (Condition)

Before selecting Next step, check whether the current path still meets the requirements for solving the problem or whether the path has reached the last step and no next step is available.

4. Algorithm template

backtracking(step, nowPath, paths) {//step: indicates the current step. NowPath: indicates the current path. Path: indicates the subsequent steps of the current step
	nowPath.add(step);
	if{result.add(nowPath);// Add to the list of solutions
	} else {
		for nextStep in path	{// "Select next"
			nextPath = nextStep.path;
			result = backtracking(nextStep, nextPath);// Proceed to the next step
		}
	}
	nowPath.remove(step);// If you want to return to the state of the previous step, this step will not be retained
	return result;
}
Copy the code

According to the algorithm template above and the process of dealing with the problem, it can be seen that the essence of == backtracking algorithm is depth-first search algorithm (DFS) ==, whose core idea is recursion, stop condition and path backtracking operation when stop.

Here are two examples to illustrate.

Example backtracking algorithm

A path that neutralizes a binary tree

Binary trees and paths with a certain value are the subject of the more representative backtracking algorithm selected from the finger offer.

Problem description

Enter a binary tree and an integer. Print out the sum of node values in the binary tree as all paths of input integers. A path is formed from the root of the tree down to the nodes passed by the leaf.

Problem analysis

When you look at the output path, when you look at the problem of searching the class, the first thought is the backtracking algorithm. Then the backtracking algorithm determines three elements:

  1. The path

The path is the left and right nodes of the binary tree.

  1. choose

Select the left node first, then the right node.

  1. conditions

Condition: There are no left and right nodes, i.e. the path reaches the leaf node solve the problem: the sum of paths is sum.

  1. process

Each time, the value of the current node is saved, and then the left node is selected for recursion. At the same time, the sum value of each time should be subtracted from the value of the current node as the remaining sum value of the child node. When it reaches the leaf node, determine whether the remaining sum value is 0.)

Code (Java+Go)

The process is annotated in the Java version.

Java version
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    List<List<Integer>> target = new LinkedList();// A collection of problem solutions
    List<Integer> sumPath = new LinkedList();// Record the path
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {// If the root node is empty, return empty
            return target;
        }
        sumPath.add(root.val);// Record the current step to the path
        
        if(root.left ! =null) {
            target = pathSum(root.left, sum - root.val);// The left node recurses first
        }

        if(root.right ! =null) {
            target = pathSum(root.right, sum - root.val);// The right node recurses
        }

        if (root.left == null && root.right == null && sum - root.val == 0) {// To reach the leaf node, whether the sum of the paths is sum
            List<Integer> tmp = new LinkedList(sumPath);
            target.add(tmp);
        }
        sumPath.remove(sumPath.size() - 1);// Go back to the previous step and remove the node from the current path
        returntarget; }}Copy the code
Go version
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func pathSum(root *TreeNode, sum int)[] []int {
    var target [][] int
    var sumPath []int

    if root == nil {
        return target
    }
    target = backtracking(root, sum, sumPath, target)
    return target
}
func backtracking(root *TreeNode, sum int, sumPath []int, target [][]int)[] []int {

    ifroot.Left ! =nil {
        sumPath = append(sumPath,root.Val)
        length := len(sumPath)
        target = backtracking(root.Left, sum - root.Val, sumPath, target)
        sumPath = sumPath[0:length- 1]}ifroot.Right ! =nil {
        sumPath = append(sumPath,root.Val)
        length := len(sumPath)
        target = backtracking(root.Right, sum - root.Val, sumPath, target)
        sumPath = sumPath[0:length- 1]}if root.Left == nil && root.Right == nil && sum - root.Val == 0 {
            sumPath = append(sumPath,root.Val)
            tmp := make([]int , len(sumPath))
            copy(tmp, sumPath)
            target = append(target,tmp)
    }
    return target
}

Copy the code

N queen

The N Queen problem is the most classic backtracking algorithm problem.

Problem description

Force button designs an algorithm that prints various positions of N queens on an N × N chessboard, where each queen is not in a row, column, or diagonal. By “diagonals” I mean all diagonals, not just the two that divide the entire board.

Problem analysis

N Queen is an upgrade based on the eight Queens. When abstracted, queen N is really a search problem. First decide on a standard to place the queen according to the row, that is, consider the position of the queen in each row. Then the backtracking algorithm determines three elements:

  1. The path

Each column of the row is a path

  1. choose

Select a column of the row as the current step

  1. conditions

Condition: the queen’s row and column are completely different, and neither queen and other queens are on the diagonal to solve the problem: the queen is also positioned on row NTH under the current path.

  1. process

This paper only introduces a simple backtracking method, based on set backtracking algorithm. For conditionals, row differences are easy to resolve: row differences are avoided by placing rows, and column differences are avoided by recording placed columns. The relatively easy way to think about the diagonal is, using a little bit of math, to think about the row and column as x,y\

Y = x + const ——> y-x = const The slope of the diagonal is -1: y = x + const ——> y-x = const Y = -x + const ——> y + x = const the row and column on the diagonal have the same sum \

Select “path” according to the above conditions, and finally select the position of the queen in the last line to form “path”.

Code (Java+Go)

Code annotations are in the Java version.

Java version
class Solution {
    public List<List<String>> solveNQueens(int n) 
    {
        List<List<String>> solutions = new LinkedList();// Set of solutions
        int[] queens = new int[n];// Queen position
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet();// Record each column where the queen is placed ----> next path
        Set<Integer> diagonalsUp = new HashSet();// Diagonal up :y - x = const
        Set<Integer> diagonalsDown = new HashSet();// Diagonal down x + y = const
        backtracking(solutions, queens, n, 0, columns, diagonalsUp, diagonalsDown);
        return solutions;
    }
    public void backtracking(List solutions, int[] queens, int n, int row , Set columns, Set diagonalsUp, Set dialogDown)
    {
        if (row == n) 
        {
            solutions.add(getSolution(queens, n));
        } else 
        {
            for (int i =0; i < n; i++) // Place the queen position (column) of the first row
            {
                if (columns.contains(i)) 
                {/ / different columns
                    continue;
                }

                int tmpDiagonalsUp = i - row;
                if(diagonalsUp.contains(tmpDiagonalsUp))
                {// Not diagonal up
                    continue;
                }

                int tmpDiagonalsDown = i + row;
                if(diagonalsDown.contains(tmpDiagonalsDown))
                {// Not diagonally down
                    continue;
                }

                queens[row] = i;
                columns.add(i);
                diagonalsDown.add(tmpDiagonalsDown);
                diagonalsUp.add(tmpdiagonalsUp);
                backtracking(solutions, queens, n, row + 1, columns, diagonalsUp, diagonalsDown); columns.remove(i); diagonalsDown.remove(tmpDiagonalsDown); diagonalsUp.remove(tmpdiagonalsUp); }}}public List<String> getSolution(int[] queens, int n) 
    {
        List<String> solution = new LinkedList();
        for (int i = 0; i < n; i++)
        {
            int index = queens[i];
            String strs = "";
            for(int j =0; j < n; j++)
            {
                if (j == index)
                {
                    strs += "Q";
                } else
                {
                    strs += ".";
                }
            }
            solution.add(strs);
        }
        returnsolution; }}Copy the code
Go version
func solveNQueens(n int)[] []string {
    solutions := [][]string{}
    queens := make([]int, n)
    for i := 0; i < n; i++ {
        queens[i] = - 1
    }
    
    columns, diagonalsUp, diagonalsDown := map[int] bool{}, map[int] bool{}, map[int] bool{}
    solutions = backtracking(solutions, queens, n, 0, columns, diagonalsDown, diagonalsUp)
    return solutions
}

func backtracking(solutions [][] string, queens []int, n int,  row int, columns map[int]bool, diagonalsDown map[int]bool, diagonalsUp map[int]bool)[] []string {
    if row == n {
        solution := getSolution(queens, n)
        solutions = append(solutions, solution)
    } else {
            for i := 0; i < n; i++ {
                if columns[i] {
                    continue
                }
                
                tmpDiagnalsUp := i + row;
                if diagonalsUp[tmpDiagnalsUp] {
                    continue
                }

                tmpDiagnalsDown := i - row;
                if diagonalsDown[tmpDiagnalsDown] {
                    continue
                }

                queens[row] = i
                columns[i] = true
                diagonalsUp[tmpDiagnalsUp] = true
                diagonalsDown[tmpDiagnalsDown] = true
                solutions = backtracking(solutions, queens, n, row + 1, columns, diagonalsDown, diagonalsUp)

                queens[row] = - 1
                delete(columns, i)
                delete(diagonalsUp, tmpDiagnalsUp)
                delete(diagonalsDown, tmpDiagnalsDown)
            }
        }
        return solutions
}

func getSolution(queens []int, n int) []string {
    solution :=[]string{}
    for i := 0; i < n; i++ {
        strs := make([]byte, n)
        for j := 0; j < n; j++ {
                strs[j] =  '. '
            }
        strs[queens[i]]= 'Q'
        solution = append(solution, string(strs))
    }
    return solution
}
Copy the code

conclusion

This is the end of the preliminary explanation of backtracking algorithm. Make clear the kernel and three elements of backtracking algorithm, and then try to meet the conditions of backtracking algorithm. The kernel of backtracking algorithm is DFS. When encountering some problems of recursion, search, path, recording process, etc., you can consider whether it is backtracking algorithm. Ask yourself the following questions: \

  1. Is recursion used?
  2. Does recursion have to satisfy certain conditions?
  3. Does the recursive process need to record the path from the beginning to the current state?
  4. Is it a search problem?
  5. How can problem conditions be satisfied? (key)

Backtracking algorithm largely uses the idea of DFS, and is quite similar to the memo optimization of dynamic programming. In the learning process, DFS, backtracking algorithm and dynamic programming can be learned and understood together.