Backtracking of front End Data Structures and Algorithm series (XI)

1. What is backtracking

Backtracking uses the idea of trial and error. It attempts to solve a problem step by step. In the process of step-by-step solution, when it finds that the existing step-by-step solution is not valid, it will cancel the previous step or even the previous step calculation, and try again to find the answer to the problem through other possible step-by-step solutions.

Backtracking is usually done in the simplest recursive way possible. After repeating the steps above over and over, two things can happen:

• Find a correct answer that might exist
• After trying all possible stepwise methods declare that the question has no answer.

In the worst case, backtracking results in a calculation of exponential time.

Backtracking is a strategy of gradually finding and building solutions to problems. Let’s start with a possible action and try to solve the problem with that action. If not, backtrack and select another action until the problem is resolved. Based on this behavior, the backtracking algorithm tries all possible actions (or fewer times if a solution is found faster) to solve the problem.

Suitable for the scene

• There are many roads.
• In these roads, there are dead ends and there are ways out.
• It is usually necessary to recursively simulate all paths.

There are some well-known problems that backtracking can solve

• Knight Patrol problem
• N Queen problem
• Maze mouse problem
• A sudoku solver

DFS can be thought of as backtracking

Back in the framework

result = [];
function backtrack (path, list) {
    if{result.push(path);return
    }
    
    for () {
        // Make a selection (preorder traversal)
        backtrack (path, list)
        // Undo selection (subsequent traversal)}}Copy the code

At its core is the recursion inside the for loop, “making a selection” before the recursive call and “unselecting” after the recursive call — Labuladong’s algorithmic cheat sheet

2. Common scenarios

2.1 Maze Mouse

Suppose we have a matrix of size N by N, and each position of the matrix is a square. Each position (or block) can be free (value 1) or blocked (value 0), as shown in the figure below, where S is the starting point and D is the ending point

function ratInAMaze(maze) { 
    const solution = []; 
    // Initialize each position to zero
    for (let i = 0; i < maze.length; i++) {
        solution[i] = []; 
        for (let j = 0; j < maze[i].length; j++) { 
            solution[i][j] = 0; }}if (findPath(maze, 0.0, solution) === true) {// Return the matrix if there is a solution
        return solution; 
    } 
    return 'NO PATH FOUND';
}

function findPath(maze, x, y, solution) { 
     const n = maze.length; 
     if (x === n - 1 && y === n - 1) { // Verify that the mouse has reached its destination
         solution[x][y] = 1; 
         return true; 
     } 
     if (isSafe(maze, x, y) === true) { // Verify that the mouse can safely move to the position
         solution[x][y] = 1; // Add this step to the path
         if (findPath(maze, x + 1, y, solution)) { // Move horizontally (right) to the next position
             return true; 
         } 
         if (findPath(maze, x, y + 1, solution)) { // Move vertically down to the next position
             return true; 
         } 
         solution[x][y] = 0; // If you can't move horizontally or vertically, remove this step from the path and backtrack
         return false; 
     } 
     return false;
}

function isSafe(maze, x, y) { 
    const n = maze.length; 
    if (x >= 0 && y >= 0&& x < n && y < n && maze[x][y] ! = =0) { 
        return true;
    } 
    return false; 
}
Copy the code

2.2 Sudoku solver

Fill a 9 by 9 matrix with the numbers 1 through 9 and require each row and column to consist of the nine numbers. The matrix also contains small squares (a 3 by 3 matrix) that need to be filled with the same nine numbers

 sudokuSolver(matrix) { 
     if (solveSudoku(matrix) === true) { 
         return matrix; 
     } 
     return 'No solution! '; 
}

const UNASSIGNED = 0; 
function solveSudoku(matrix) { 
    let row = 0; 
    let col = 0; 
    let checkBlankSpaces = false; 
    for (row = 0; row < matrix.length; row++) { // Verify that the puzzle is solved
        for (col = 0; col < matrix[row].length; col++) {
            if (matrix[row][col] === UNASSIGNED) { 
                checkBlankSpaces = true; // There is a blank space
                break; }}if (checkBlankSpaces === true) { // Break out of both loops
            break; }}if (checkBlankSpaces === false) { 
        return true; // If there is no blank position (the position with a value of 0), the puzzle is completed
    } 
    for (let num = 1; num <= 9; num++) { // Try to fill in the positions with 1 to 9, one at a time
        if (isSafe(matrix, row, col, num)) { // Check whether the added numbers conform to the rules
            matrix[row][col] = num; // Fill in the number
            if (solveSudoku(matrix)) { // Try to fill in the next position
                return true; 
            } 
            matrix[row][col] = UNASSIGNED; // If a number is in an incorrect position, we mark the position blank again}}return false; // Trace back and try another number
}

function isSafe(matrix, row, col, num) { 
    return(! usedInRow(matrix, row, num) && ! usedInCol(matrix, col, num) && ! usedInBox(matrix, row - (row %3), col - (col % 3), num) 
    ); 
}

function usedInRow(matrix, row, num) {
    // Check whether the number exists in the row by iterating over each position in the given row of the matrix
    for (let col = 0; col < matrix.length; col++) { 
     if (matrix[row][col] === num) { 
         return true; }}return false; 
} 
function usedInCol(matrix, col, num) { 
    // Iterate through all columns to verify that the number exists in the given column
    for (let row = 0; row < matrix.length; row++) {
        if (matrix[row][col] === num) { 
            return true; }}return false; 
} 
function usedInBox(matrix, boxStartRow, boxStartCol, num) { 
    // Check whether the number exists in the small matrix by iterating over all positions in the 3 by 3 matrix
    for (let row = 0; row < 3; row++) { 
        for (let col = 0; col < 3; col++) { 
            if (matrix[row + boxStartRow][col + boxStartCol] === num) {
                return true; }}}return false; 
}
Copy the code

3. Leetcode

3.1 easy

3.2 middle

1.The whole arrangement

Difficulty: Medium

Solution: Complete permutation (backtracking)

2. The whole arrangement II

Difficulty: Medium

Answer key:

3.A subset of

Difficulty: Medium

Problem: Subset (backtracking)

4.Letters for telephone numbers

Difficulty: Medium

The number combination of telephone numbers

5.combination

Difficulty: Medium

Combination (backtracking +DFS)

6. Effective sudoku

Difficulty: Medium

Answer key:

7.Parentheses generates

Difficulty: Medium

BFS+DFS+ backtracking

3.3 hard

1.N queen

Difficulty: difficult

N Queen (backtracking)

2. Their independence

Difficulty: difficult

Answer key: