Backtracking

BACKTRACKING

                   Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. 

There are three types of problems in backtracking –

1. Decision Problem – In this, we search for a feasible solution.
2. Optimization Problem – In this, we search for the best solution.
3. Enumeration Problem – In this, we find all feasible solutions.
   

  PSEUDO CODE:

1. Recursive backtracking solution.

void findSolutions(n, other params) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            findSolutions(n+1, other params);
            removeValue(val, n); 

2.Finding whether a solution exists or not 

 boolean findSolutions(n, other params) :
    if (found a solution) :
        displaySolution();
        return true;

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            if (findSolutions(n+1, other params))
                return true;
            removeValue(val, n);
        return false;
 

RAT IN A MAZE :

A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1].

 

The rat can move only in two directions: forward and down.
In the maze matrix, 0 means the block is a dead end and 1 means the block can be used in the path from source to destination.

Algorithm:

1. Create a solution matrix, initially filled with 0’s.
2. Create a recursive funtion, which takes initial matrix, output matrix and position of rat (i, j).
3. if the position is out of the matrix or the position is not valid then return.
4. Mark the position output[i][j] as 1 and check if the current position is destination or not. If destination is reached print the output matrix and return.
5. Recursively call for position (i+1, j) and (i, j+1).
6. Unmark position (i, j), i.e output[i][j] = 0.
   

 PROGRAM:

 

public class RatMaze {

  

    // Size of the maze

    static int N;

  

    /* A utility function to print 

    solution matrix sol[N][N] */

    void printSolution(int sol[][])

    {

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N; j++)

                System.out.print(

                    " " + sol[i][j] + " ");

            System.out.println();

        }

    }

  

    /* A utility function to check 

        if x, y is valid index for N*N maze */

    boolean isSafe(

        int maze[][], int x, int y)

    {

        // if (x, y outside maze) return false

        return (x >= 0 && x < N && y >= 0

                && y < N && maze[x][y] == 1);

    } 

    /* This function solves the Maze problem using 

    Backtracking. It mainly uses solveMazeUtil() 

    to solve the problem. It returns false if no 

    path is possible, otherwise return true and 

    prints the path in the form of 1s. Please note 

    that there may be more than one solutions, this 

    function prints one of the feasible solutions.*/

    boolean solveMaze(int maze[][])

    {

        int sol[][] = new int[N][N];

  

        if (solveMazeUtil(maze, 0, 0, sol) == false) {

            System.out.print("Solution doesn't exist");

            return false;

        }

  

        printSolution(sol);

        return true;

    }

  

    /* A recursive utility function to solve Maze 

    problem */

    boolean solveMazeUtil(int maze[][], int x, int y,

                          int sol[][])

    {

        // if (x, y is goal) return true

        if (x == N - 1 && y == N - 1

            && maze[x][y] == 1) {

            sol[x][y] = 1;

            return true;

        }

  

        // Check if maze[x][y] is valid 

            if (isSafe(maze, x, y) == true) {

            // mark x, y as part of solution path

            sol[x][y] = 1;

  

            /* Move forward in x direction */

            if (solveMazeUtil(maze, x + 1, y, sol))

                return true;

  

            /* If moving in x direction doesn't give 

            solution then Move down in y direction */

            if (solveMazeUtil(maze, x, y + 1, sol))

                return true;

  

            /* If none of the above movements works then 

            BACKTRACK: unmark x, y as part of solution 

            path */

            sol[x][y] = 0;

            return false;

        }

  

        return false;

    }

  

    public static void main(String args[])

    {

      
RatMaze rat = new RatMaze();

        int maze[][] = { { 1, 0, 0, 0 },

                         { 1, 1, 0, 1 },

                         { 0, 1, 0, 0 },

                         { 1, 1, 1, 1 } };

  

        N = maze.length;

        rat.solveMaze(maze);

    }

}