Home techblogs algorithms recursion-backtrack-approach

Recursion and Backtrack Approach

What is Backtracking Approach ?

Problems which are typically solved using backtracking technique have following property in common:

Notes:-

Standard Backtracking Problems:

Standard Backtracking Problems

1. All Permutations of a Given String***

Problem:
Algorithm:
Implementation:
def generate_permutations_util(string, left, right):
    if(left == right):
        print("{}".format("".join(string)))
        return
    
    for i in range(left, right):
        string[left], string[i] = string[i], string[left]
        generate_permutations_util(string, left+1, right)
        string[left], string[i] = string[i], string[left]    # Backtrack


def generate_permutations(string):
    n = len(string)
    generate_permutations_util(list(string), 0, n)



print("Example-1:")
generate_permutations("ABC")

print("\nExample-2")
generate_permutations("ABCD")


# Complexity:
#    • Time: O(n*n!) :- There are n! permutations and it requires O(n) time to print a permutation.
#    • Auxilliary Space: O(1)

Output:

all_permuatations_of_string

Complexity:



2. Knight’s Tour Problem***

Problem:

The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.

knight_tour

Naive Approach:

The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.

while there are untried tours {
   generate the next tour 
   if this tour covers all squares {
      print this path;
   }
}
Backtracking Approach:
Implementation:
POSSIBLE_MOVES = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2,1)]

def valid_move(x, y, tour_matrix):
    return (x>=0 and x<N and y>=0 and y<N and tour_matrix[x][y]==-1)


def knight_tour_util(current_x, current_y, move_number, tour_matrix):
    if(move_number == N*N):
        return True
    
    # Try all possible moves
    for x_move, y_move in POSSIBLE_MOVES:
        next_x = current_x + x_move
        next_y = current_y + y_move
        if(valid_move(next_x, next_y, tour_matrix)):
            tour_matrix[next_x][next_y] = move_number
            if(knight_tour_util(next_x, next_y, move_number+1, tour_matrix) == True):
                return True
            else:
                tour_matrix[next_x][next_y] = -1  # Backtrack
    return False


def knight_tour():
    # Create a 2-D Matrix(N*N)
    tour_matrix = [[-1]*N for _ in range(N)]

    #  Knight is initially at the first block 
    tour_matrix[0][0]  = 0

    if(knight_tour_util(0, 0, 1, tour_matrix) == True):
        for i in range(N):
            for j in range(N):
                print("{0: =2d}".format(tour_matrix[i][j]), end=" ")
            print()
        print()
    else:
        print("No solution exist")



print("Knight Tour Example-1: 4*4 Matrix")
N = 4
knight_tour()

print("\nKnight Tour Example-2: 5*5 Matrix")
N = 5
knight_tour()

print("\nKnight Tour Example-3: 8*8 Matrix")
N = 8
knight_tour()


# Complexity:
#    • Time: O(8^(n^2)) :- There are N*N i.e., N^2 cells in the board and we have a maximum of 8 choices to make from a cell.
#    • Auxilliary Space: O(N^2)

Output:

knight_tour_output

Complexity:
Notes:



3. N-Queen Problem***

Problem:

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

Example: 4 Queen problem.

Approach:
Algorithm:
  1. Start in the leftmost column
  2. If all queens are placed: return true
  3. Try all rows in the current column. Do following for every tried row.
    • a) If the queen can be placed safely in this row then mark this [row,column] as part of the solution and recursively check if placing queen here leads to a solution.
    • b) If placing the queen in [row, column] leads to a solution then return true.
    • c) If placing queen doesn’t lead to a solution then unmark this [row,column] (Backtrack) and go to step (a) to try other rows.
  4. If all rows have been tried and nothing worked, return false to trigger backtracking.
Implementation:
# To check if a queen can be placed on board[row][col]. 
# Note that this function is called when "col" number of queens are already placed in columns from 0 to col -1. 
# So we need to check only left side for attacking queens.
def is_safe(board, row, col):
    safe = True
    # Check this row on left side.
    for j in range(col):
        if(board[row][j] == 1):
            safe = False
            break
    
    # Check upper diagonal on left side
    i = row; j=col
    while(i>=0 and j>=0):
        if(board[i][j]==1):
            safe = False
            break
        i-=1; j-=1
    
    # Check lower diagonal on left side
    i = row; j = col
    while(i<N and j>=0 and safe):
        if(board[i][j]==1):
            safe = False
            break
        i+=1; j-=1

    return safe
    

def n_queen_util(board, col):
    # Base case: If all queens are placed then return true 
    if(col == N):
        return True
    
    # Consider this column and try placing this queen in all rows one by one 
    for i in range(N):
        if(is_safe(board, i, col)):
            # Place this queen in board[i][col] 
            board[i][col] = 1
            # Recur to place rest of the queens 
            if(n_queen_util(board, col+1) == True):
                return True
            else:
                board[i][col] = 0   # Backtrack
    
    # If the queen can not be placed in any row in this colum col  then return false
    return False


def n_queen():
    board = [[0]*N for i in range(N)]

    if(n_queen_util(board, 0) == True):
        for i in range(N):
            print(board[i])
    else:
        print("No solution exists")



print("N-Queen Example-1: 3*3 Matrix")
N = 3
n_queen()

print("\nN-Queen Example-2: 4*4 Matrix")
N = 4
n_queen()

print("\nN-Queen Example-3: 5*5 Matrix")
N = 5
n_queen()

print("\nN-Queen Example-4: 8*8 Matrix")
N = 8
n_queen()


# Complexity:
#    • Time: 
#    • Auxilliary Space:

Output:

n-queen-output

Complexity:



4. Rat in Maze***

Problem:
Example Maze:

rat_in_maze_1

rat_in_maze_2

Algorithm:
Implementation:
def rat_in_maze_util(solution_maze, x, y):
    if(x == N-1 and y == N-1):
        return True
    
    # Make a move in forward direction if it is_safe to move
    if(given_maze[x][y+1] == 1):
        solution_maze[x][y+1] = 1
        if(rat_in_maze_util(solution_maze, x, y+1) == True):
            return True
        else:
            solution_maze[x][y+1] = 0   # Backtrack
    
    # Make a move in downward direction if it is_safe to move
    if(given_maze[x+1][y] == 1):
        solution_maze[x+1][y] = 1
        if(rat_in_maze_util(solution_maze, x+1, y) == True):
            return True
        else:
            solution_maze[x][y+1] = 0   # Backtrack
    
    return False


def rat_in_maze():
    solution_maze = [[0]*N for i in range(N)]
    solution_maze[0][0] = 1

    if(rat_in_maze_util(solution_maze, 0, 0)):
        for i in range(N):
            print(solution_maze[i])
    else:
        print("No Solution exist.")



print("Rat in Maze Example-1: 4*4 Matrix")
N = 4
given_maze = [ [1, 0, 0, 0], 
               [1, 1, 0, 1], 
               [0, 1, 0, 0], 
               [1, 1, 1, 1] ]
rat_in_maze()

Output:

rat_in_maze_output

Complexity:



5. Subset Sum Problem

Problem:
Implementation:
def subset_sum(given_set, num):
    if num < 1 or len(given_set) == 0:
        return False

    if num == given_set[0]:
        return [given_set[0]]

    with_v = subset_sum(given_set[1:], num-given_set[0])
    if with_v:
        return [given_set[0]] + with_v
    else:
        return subset_sum(given_set[1:], num)
    


print("Subset Sum Example-1:")
given_set = [10, 7, 5, 18, 12, 20, 15]
print(subset_sum(given_set, 35))

print("Subset Sum Example-2:")
given_set = [15, 22, 14, 26, 32, 9, 16, 8]
print(subset_sum(given_set, 53))

Output:

subset_sum_output

Complexity:



6. Sudoku***

Problem:

Given a partially filled 9×9 2D array grid[9][9], the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

Backtracking Approach:
Algorithm:
Implementation
import math

# get_base_box gives start row or col of the mini_box
# like if row = 2 then base_row = 0 and if row = 8 then base_row = 6
def get_base_box(index, k):
    return int(index/k)*k


def find_unassigned_box(matrix):
    n = len(matrix[0])
    for row in range(n): 
        for col in range(n): 
            if(matrix[row][col]==0): 
                return (True, row, col)

    return (False, None, None)


def is_safe(matrix, row, col, num):
    n = len(matrix[0])
    status = True
    # Check if the row is safe
    for i in range(n):
        if(matrix[row][i] == num):
            status = False
            break
    
    # Check if the column is safe
    for i in range(n):
        if(matrix[i][col] == num):
            status = False
            break
    
    # Check if the individual 3*3 box is safe as n = 9 hence k = 3
    k = int(math.sqrt(n))
    base_row = get_base_box(row, k)
    base_col = get_base_box(col, k)
    for i in range(k): 
        for j in range(k): 
            if(matrix[i+base_row][j+base_col] == num): 
                status = False
                break

    return status


def solve_sudoku(matrix):
    n = len(matrix[0])
    # Check for unassigned box and return status, if status is True also return row and col of that box
    found, row, col = find_unassigned_box(matrix)

    # If No unassigned box found, we are done 
    if(not found):
        return True
    
    # Consider digits 1 to 9 
    for num in range(1, n+1):
        # Check if it is safe to put this number
        if(is_safe(matrix, row, col, num)):
            # Put this number
            matrix[row][col] = num
            # Recur to check if it leads to solution
            if(solve_sudoku(matrix) == True):
                return True
            else:
                matrix[row][col] = 0  # Backtrack
    
    return False



print("Sudoku Example-1:")
matrix = [[3,0,6,5,0,8,4,0,0], 
          [5,2,0,0,0,0,0,0,0], 
          [0,8,7,0,0,0,0,3,1], 
          [0,0,3,0,1,0,0,8,0], 
          [9,0,0,8,6,3,0,0,5], 
          [0,5,0,0,9,0,6,0,0], 
          [1,3,0,0,0,0,2,5,0], 
          [0,0,0,0,0,0,0,7,4], 
          [0,0,5,2,0,6,3,0,0]]

n = len(matrix[0])
if(solve_sudoku(matrix)): 
    for i in range(n):
        for j in range(n):
            print(matrix[i][j], end=" ")
        print() 
else: 
    print("No solution exists")

Output:

sudoku_problem_output

Complexity:



7. Tower of Hanoi

Problem:

3 Towers given, and one of tower has all the disks kept in increasing order of size from top to bottom.

We have to move all those disks to another tower with below conditions:

Approach:

Implementation
def tower_of_hanoi(n, source, auxiliary, destination):
    if(n>0):
        # Move n-1 disks from source to auxilliary using destination
        tower_of_hanoi(n-1, source, destination, auxiliary)

        # Move that 1 disk now from source to destination
        print("Move 1 disk from {} to {}".format(source, destination))

        # Move rest n-1 from auxiliary to destination using source
        tower_of_hanoi(n-1, auxiliary, source, destination)



print("Tower of Hanoi Example-1")
tower_of_hanoi(3, "A", "B", "C")

print("\nTower of Hanoi Example-2")
tower_of_hanoi(4, "A", "B", "C")

Output:

tower_of_hanoi_output

Complexity:



← Previous: Selection Algorithms

Next: Greedy Approach →






Subscribe !

Subscribe to the mailing list and get the latest updates in your mailbox.

Connect to me through Social Networks !

Get socially conneted on social networks and be updated.
LinkedIn GitHub StackOverflow Instagram

Contact Me !

You can reach me using below contact details.
  • Hyderabad, Telangana, India
  • +91-9037489697
  • +91-9037489697
  • astikanand@gmail.com