Understanding Backtracking

Abstract Pseudo code to help understand the gist of backtracking

bool Solve(configuration conf)
{
if (no more choices) // BASE CASE
return (if conf is goal state);

for (all available choices)
{
try one choice c;
…


This content originally appeared on DEV Community and was authored by dhavalraj007

recursive tree/choice tree
Abstract Pseudo code to help understand the gist of backtracking

bool Solve(configuration conf)
{
    if (no more choices) // BASE CASE
       return (if conf is goal state);

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        ok = Solve(updated conf with choice c made);
        if (ok)
           return true;
        else
           unmake choice c;
    }

return false; // tried all choices, no soln found
}

When you need to find all possible solutions

void Solve(configuration conf,solutions& sols)
{
    if (no more choices) // BASE CASE
       if conf is goal state
           sols.add(conf);
       return;

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        Solve(updated conf with choice c made);
        unmake choice c;
    }

return; // tried all choices, no soln found
}

Examples:

N-Queens

Problem statement

given a grid of size NxN arrange N queens in a grid such that no queen attacks other.
input:

N = 4

Output:

0  1  0  0
0  0  0  1
1  0  0  0
0  0  1  0

Pseudo Code

bool solve(grid,queens)
{
    //if(no more choices) //conf is goal state // BASE CASE
    if(queens==0)           
        return true;

    //for (all available choices)
    for(all safe grid cell c)
    {
        //try one choice c;
        // recursively solve after making choice
        put queen at cell c;
        // ok = Solve(updated conf with choice c made);
        ok = solve(grid,queens-1);

        if(ok)
            return true;
        else
            remove queen from cell c;   //unmake choice c;
    }

    return false;       // tried all choices, no soln found
}

Cpp code

//checks whether the cell (i,j) is unsafe or safe
bool is_Atttacked(int i, int j, vector<vector<int>>& grid)
{
    int N = grid.size();
    for (int ele : grid[i])
    {
        if (ele == 1)
            return true;
    }


    for (int row = 0; row < N; row++)
    {
        if (grid[row][j] == 1)
            return true;
    }

    for (int y = 0; y < N; y++)
    {
        int x = (i - j) + y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }


    for (int y = 0; y < N; y++)
    {
        int x = (i + j) - y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }

    return false;
}

//main recursive function
bool NQueens(vector<vector<int>>& grid, int N)
{
    if (N == 0)
        return true;

    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid.size(); j++)
        {
            if (is_Atttacked(i, j, grid))
                continue;

            grid[i][j] = 1;

            if (NQueens(grid, N - 1))
                               return true;
                        else
                    grid[i][j] = 0;
        }
    }
    return false;
}

Knights Tour

Problem statement

Given a NxN board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.

input:

N = 5

output:

0  5  14 9  20 
13 8  19 4  15 
18 1  6  21 10 
7  12 23 16 3 
24 17 2  11 22

Pseudo code

//grid filled with -1 and grid[0][0] = 0 , steps = 1 , x=y=0
bool solve(grid,steps,x,y)
{
    if(steps==grid.size()^2)
    {
        print(grid);
        return true;
    }

    for(all possible/safe moves from (x,y))
    {
        grid[move.x][move.y] = steps;
        ok = solve(grid,steps+1,move.x,move.y);
        if(ok)
            return true;
        else
            grid[move.x][move.y] = -1;
    }
    return false;
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;


void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}

bool solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return true;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            int ok = solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            if(ok)
                return true;
            else
                grid[Xnext][Ynext] = -1;
        }
    }

    return false;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

Cpp code for all possible solutions

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}


void solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            grid[Xnext][Ynext] = -1;
        }
    }

    return;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

Find all Paths in a Maze/Rat in a Maze

Problem Statement:

given a binary matrix of size NxN find and print Path from top left corner to bottom right corner.
input:

1 0 0 0
1 1 1 1
0 1 0 1
1 1 1 1

output:

1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

1 0 0 0
1 1 1 1
0 0 0 1
0 0 0 1

Cpp code for all Possible Paths

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>>& grid)
{
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid.size();j++)
        {
            cout<<grid[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


bool isValid(vector<vector<int>> &maze,vector<vector<int>> &ans,int x,int y)
{
    return (x>=0 and x<maze.size() and y>=0 and y<maze.size() and maze[x][y]==1 and ans[x][y]==0);
}

void findPath(vector<vector<int>> &maze,vector<vector<int>> ans,int x,int y)
{
    if(ans[maze.size()-1][maze.size()-1] == 1)
        {
            print(ans);
            return;
        }

    if(isValid(maze,ans,x+1,y))     //down
    {
        ans[x+1][y] = 1;
        findPath(maze,ans,x+1,y);
        ans[x+1][y] = 0;
    }

    if(isValid(maze,ans,x-1,y))     //up
    {
        ans[x-1][y] = 1;
        findPath(maze,ans,x-1,y);
        ans[x-1][y] = 0;
    }

    if(isValid(maze,ans,x,y+1))     //right
    {
        ans[x][y+1] = 1;
        findPath(maze,ans,x,y+1);
        ans[x][y+1] = 0;
    }

    if(isValid(maze,ans,x,y-1))     //left
    {
        ans[x][y-1] = 1;
        findPath(maze,ans,x,y-1);
        ans[x][y-1] = 0;
    }
    return;
}

int main() {
    int x,y;
    x=0,y=0;

    vector<vector<int>> maze = { 
                    { 1, 0, 0, 0 },
                    { 1, 1, 1, 1 },
                    { 0, 1, 0, 1 },
                    { 1, 1, 1, 1 } };
    int N = maze.size();
    vector<vector<int>> ans(N,vector<int>(N,0));
    ans[0][0] = 1;

    findPath(maze,ans,x,y);
}

Find all possible combinations satisfying given constraints

Problem Statement

Given a number N find all possible combination of 2N numbers such that every element from 1 to 2N appears exactly twice and the distance between them is equal to that number.

input:

N = 3

output:

 3 1 2 1 3 2
 2 3 1 2 1 3

In this problem, recursive tree can be formed in two ways. first way is you first consider N elements as choices and other is you consider 2N positions as choices. In first way you choose one of N elements and place it at the 0th position in array and then you recurs for all other indices(here you need to have some way to not put the number more than once). In second way you take first element from N and choose one of 2N locations to put the first element and recurs for all other N-1 numbers. as the second way seems much easy we will implement that.

Pseudo Code

void solve(array,n)
{
    if(n becomes 0)
    {
        print array
        return;
    }

    for(all indices i in array)
    {
        if(inserting in n in array at index i is safe)  // safe means array[i] and array[i+n+1] is free
        {
            array[i] = n;       // put n at i and i+n+1
            array[i+n+1] = n;

            solve(array,n-1);   //recur for all n-1 numbers

            array[i] = -1;      //unmake choice
            array[i+n+1] = -1;
        }
    }
    return; //no soln found
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> ar)
{
    for(auto e:ar)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

bool is_safe(vector<int> array,int n,int i)
{
    return (i<array.size() and i+n+1<array.size() and array[i]==-1 and array[i+n+1]==-1);
}


void solve(vector<int> array,int n)
{
    if(n==0)
    {
        print(array);
        return;
    }

    for(int i=0;i<array.size();i++)
    {
        if(is_safe(array,n,i))
        {
            array[i] = n;
            array[i+n+1]=n;
            solve(array,n-1);
            array[i] = -1;
            array[i+n+1] = -1;
        }
    }
    return;
}

int main() {
    int N = 7;
    vector<int> v(2*N,-1);
    solve(v,N);
}


This content originally appeared on DEV Community and was authored by dhavalraj007


Print Share Comment Cite Upload Translate Updates
APA

dhavalraj007 | Sciencx (2021-08-15T09:59:15+00:00) Understanding Backtracking. Retrieved from https://www.scien.cx/2021/08/15/understanding-backtracking/

MLA
" » Understanding Backtracking." dhavalraj007 | Sciencx - Sunday August 15, 2021, https://www.scien.cx/2021/08/15/understanding-backtracking/
HARVARD
dhavalraj007 | Sciencx Sunday August 15, 2021 » Understanding Backtracking., viewed ,<https://www.scien.cx/2021/08/15/understanding-backtracking/>
VANCOUVER
dhavalraj007 | Sciencx - » Understanding Backtracking. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/08/15/understanding-backtracking/
CHICAGO
" » Understanding Backtracking." dhavalraj007 | Sciencx - Accessed . https://www.scien.cx/2021/08/15/understanding-backtracking/
IEEE
" » Understanding Backtracking." dhavalraj007 | Sciencx [Online]. Available: https://www.scien.cx/2021/08/15/understanding-backtracking/. [Accessed: ]
rf:citation
» Understanding Backtracking | dhavalraj007 | Sciencx | https://www.scien.cx/2021/08/15/understanding-backtracking/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts