You need to login before you can make any post submission.
Backtracking
It is one of problem solving strategy and it uses Brute-Force Approach.
For any given problem try out all possible solutions and pick-up desired solutions.
We also follow this in Dynamic Programming approach but there we solve optimization problem.
Backtracking is not optimization problem, it is used when we have multiple solutions and we want all those solutions.
We can find all the solution and it can be represented in the form of a solution tree also k/a state-space tree.
Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”.
Standard Backtracking Problems:
A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.
A string of length n has n! permutation.
Permutations of string ABC: ABC ACB BAC BCA CBA CAB
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:
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.
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;
}
}
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:
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.
# 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:
maze[0][0]
and destination block is lower rightmost block i.e., maze[N-1][N-1]
. 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:
Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K.
We are considering the set contains non-negative values.
It is assumed that the input set is unique (no duplicates are presented).
The problem is NP-Complete, while it is easy to confirm whether a proposed solution is valid, it may be difficult to determine in the first place whether any solution exists.
There exists a DP solution to this problem which gives pseudo-polynomial time and hence considered weakly NP-Complete.
Example-1: Set = [10, 7, 5, 18, 12, 20, 15] K = 35 then,
Answer: [10, 7, 18] or [20, 15]
Example-2: Set = [15, 22, 14, 26, 32, 9, 16, 8] K = 53 then,
Answer: [15, 22, 16] or [32, 9, 16]
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:
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.
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:
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:
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: