Algorithms – Recursive backtracking

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Algorithms no doubt confuse most of us, and we struggle to learn. After learning it is also easy to forget, we need to do a good summary, algorithm I will continue to update the various algorithms I encountered in learning algorithm, strive to enrich the content of the article, become a serial. In this article, we will introduce recursion and use recursion to realize backtracking, and solve some problems encountered in some programs.

recursive

In layman’s terms, recursion is calling itself in a program and leaving an exit to return to.

It is generally used to solve the problem that the same routine is used when the conditions are not met until the correct result is returned.

---

Recursion as an algorithm is widely used in programming languages. A procedure or function in the introduction to the definition or call their own, directly or indirectly, with a kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code. — From Baidu Encyclopedia

back

Backtracking algorithm tries again and again, and when it can’t continue, it goes back to the previous node to start a new attempt until the problem is solved or fails.

Backtracking method is a kind of optimal search method, according to a certain strategy to search, in order to achieve the goal. When a certain point fails, it will take a step back and choose again. Such algorithm that fails to go back again is the backtracking algorithm. After turning back, the appropriate point to be found again is the backtracking point.

---

In fact, backtracking algorithm is a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will backtrack back and try another path. — From Baidu Encyclopedia

Recursion and backtracking

Recursion and backtracking do not conflict, but we can achieve backtracking algorithm through recursion, so that we can use this relatively stupid way to solve the maze, eight queens and other problems.

For example:

Maze problem

Successful Escape Map:1	1	1	1	1	1	1	
1	2	2	2	2	2	1	
1	0	0	0	0	2	1	
1	0	1	1	0	2	1	
1	1	1	0	0	2	1	
1	0	0	0	0	2	1	
1	0	0	0	0	2	1	
1	1	1	1	1	1	1	
Copy the code

package com.zhj.bz.datastructure.recursion;

import java.util.Arrays;

/** * Recursion: maze problem *@author zhj
 */
public class MiGong {
    public static void main(String[] args) {
        // Create a two-dimensional array to simulate a maze
        / / map
        int row = 8;
        int col = 7;
        int[][] map = new int[row][col];
        // Use 1 to represent the wall
        / / set up the wall
        for (int i = 0; i < col; i++) {
            map[0][i] = 1;
            map[row-1][i] = 1;
        }
        for (int i = 0; i < row; i++) {
            map[i][0] = 1;
            map[i][col-1] = 1;
        }
        / / set baffle
        map[4] [1] = 1;
        map[4] [2] = 1;
        map[3] [2] = 1;
        map[3] [3] = 1;
        / /.
        if (setWay2(map, 1.1, row, col)) {
            System.out.println("Escape without incident.");
        } else {
            System.out.println("Cornered");
        }
        System.out.println("Map:");
        for (int[] ints : map) {
            for (int n : ints) {
                System.out.print(n + "\t"); } System.out.println(); }}/** * map[row-2][col-2] indicates the exit * 1 cannot go, 2 can go, 3 indicates that the position has been passed, but can not go * under the policy, right, up, left, if not go back *@paramThe map map *@paramI point of departure *@paramJ starting point *@paramRow Map size *@paramCol map size *@return* /
    public static boolean setWay(int[][] map, int i, int j,int row, int col) {
        if (map[row-2][col-2] = =2) {
            return true;
        } else {
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay(map,i+1,j, row, col)) { / /
                    return true;
                } else if (setWay(map, i,j+1, row, col)){ / / right
                    return true;
                } else if (setWay(map,i-1,j-1, row, col)){ / /
                    return true;
                } else if (setWay(map,i,j-1, row, col)){ / / left
                    return true;
                } else {
                    map[i][j] = 3;
                    return false; }}else {
                return false; }}}/** * map[row-2][col-2] indicates the exit * 1 cannot go, 2 can go, 3 indicates that the position has been passed, but cannot go@paramThe map map *@paramI point of departure *@paramJ starting point *@paramRow Map size *@paramCol map size *@return* /
    public static boolean setWay2(int[][] map, int i, int j,int row, int col) {
        if (map[row-2][col-2] = =2) {
            return true;
        } else {
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay2(map, i, j+1, row, col)) { / / right
                    return true;
                } else if (setWay2(map, i+1, j, row, col)){ / /
                    return true;
                } else if (setWay2(map, i, j-1, row, col)){ / / left
                    return true;
                } else if (setWay2(map, i-1, j-1, row, col)){ / /
                    return true;
                } else {
                    map[i][j] = 3;
                    return false; }}else {
                return false; }}}}Copy the code

Eight Queens problem

---

package com.zhj.bz.datastructure.recursion;

/** ** there are 92 possible solutions to the problem 8*8@author zhj
 */
public class Queen8 {

    private static final int MAX = 8;
    private static int[] array = new int[MAX];
    private static int index = 0;

    public static void main(String[] args) {
        check(0);
    }

    /** * put the NTH queen *@param n
     */
    public static void check(int n) {
        if (n == MAX) {
            index++;
            System.out.println("The first"+ index +"Time" + "Eight queens are in place.");
            show();
            return;
        }
        for (int i = 0; i < MAX; i++) {
            // Put the current queen in the first column of the row
            array[n] = i;
            // Determine if there is a problem
            if (judge(n)) {
                // Then put the n+1 queen
                check(n+1);
            }
            // The conflict continues to circle down, with the NTH queen moved one position back}}/** * check that when we place the NTH queen, we check whether the queen conflicts with the previous queen *@paramNTH queen *@return* /
    public static boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            // array[I] == array[n] Checks whether the array is in the same column
            // math. abs(n- I) == math. abs(array[n]-array[I]
            // n is increasing every time
            if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])) {
                return false; }}return true;
    }

    public static void show(a) {
        for (int i = 0; i < array.length; i++) {
            System.out.println("The first" + (i+1) + "A queen, placed in the first place." + array[i] + "A place."); }}}Copy the code