[Algorithms] Backtracking

Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. It works in incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.


Concepts

Backtracking works in an incremental way to attack problems.
Typically, we start from an empty solution vector and one by one add items. When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives. If none of the alternatives work out then we go to previous stage and remove the item added in the previous stage.
If we reach the initial stage back then we say that no solution exists. If adding an item doesn’t violate constraints then we recursively add items one by one. If the solution vector becomes complete then we print the solution.

Psudo Code

Following is the Backtracking algorithm for Knight’s tour problem.


IF all squares are visited
print the solution
ELSE
a) Add one of the next moves to solution vector and recursively
check if this move leads to a solution. (A Knight can make maximum
eight moves. We choose one of the 8 moves in this step).
b) If the move chosen in the above step doesn't lead to a solution
then remove this move from the solution vector and try other
alternative moves.
c) If none of the alternatives work then return false (Returning false
will remove the previously added item in recursion and if false is
returned by the initial call of recursion then "no solution exists" )

Sample Problems (from LeetCode)

N-Queens (51)

Problem:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:


Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# ugly but easy to understand

import copy

class Solution(object):

# Recurse columnly, from left to right. So columns & right rows/diagnals are good. Just check the left rows & left diagnals.
def isSafe(self, n, board, row, col):
# left row
for i in range(col):
if board[row][i] == 'Q':
return False
# left upper diagonal
for i,j in zip(range(row,-1,-1), range(col,-1,-1)):
if board[i][j] == 'Q':
return False
# left lower diagonal
for i,j in zip(range(row,n,1), range(col,-1,-1)):
if board[i][j] == 'Q':
return False
return True

# solveNQUtil() places queen for each column
def solveNQUtil(self, n, board, col, res):
# base case: If all queens are placed, append to res & return
if col >= n:
# res.append(board) is wrong. board will change afterwards
board_copy = copy.deepcopy(board)
res.append(board_copy)
return

# Consider every row(i) of this col: only when isSafe(), place the queen at this row
for i in range(n):
if self.isSafe(n, board, i, col):
board[i][col] = 'Q'
self.solveNQUtil(n, board, col+1, res)
board[i][col] = '.' # backtracking

def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
board = [['.' for i in range(n)] for j in range(n)]
# board = [['.'] * n] * n is WRONG. '* n' is not deep copy. shoud not use it to initialize board.
res = []
self.solveNQUtil(n, board, 0, res)
res = [[''.join(row) for row in board] for board in res]
return res

Word Search(79)

Problem:
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:


board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import numpy as np

class Solution(object):

def util(self, board, used, word, l, i, j):
# base case: If all characters are placed, return true
if l >= len(word):
return True
# same letter cell may not be used more than once.
# consider edges
if j - 1 >= 0 and board[i][j - 1] == word[l] and used[i][j - 1] == 0:
used[i][j - 1] = 1
if self.util(board, used, word, l + 1, i, j - 1) == True:
return True
used[i][j - 1] = 0
# shouldn't use elif!!! or if one is False, it will not enter another condition
if j + 1 < len(board[0]) and board[i][j + 1] == word[l] and used[i][j + 1] == 0:
used[i][j + 1] = 1
if self.util(board, used, word, l + 1, i, j + 1) == True:
return True
used[i][j + 1] = 0

if i - 1 >= 0 and board[i - 1][j] == word[l] and used[i - 1][j] == 0:
used[i - 1][j] = 1
if self.util(board, used, word, l + 1, i - 1, j) == True:
return True
used[i - 1][j] = 0

if i + 1 < len(board) and board[i + 1][j] == word[l] and used[i + 1][j] == 0:
used[i + 1][j] = 1
if self.util(board, used, word, l + 1, i + 1, j) == True:
return True
used[i + 1][j] = 0
return False

def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
start = np.where(
np.array(board) == word[0]) # 2D array, start[0] contains the row idxs, start[1] contains col idxs

if len(start[0]) == 0 or len(board)*len(board[0])< len(word):
return False

res = []
for i, j in zip(start[0], start[1]):
used = np.zeros((len(board), len(board[0])))
used[i][j] = 1
a = self.util(board, used, word, 1, i, j)
res.append(a)
return True if True in res else False

Conclusion

Steps

Using the solution of N-Queen as a template to solve all backtracking problems.
First we should figure out what does the backtracking function do. In N-Queen, it is a function casted over each column:

  • columns: 1st loop. examine one column per backtracking function call.

Then, in the backtracking function:

  • row: 2nd loop. check every row of a certain col to find all possible next move.
  • neighborhood: 3rd loop: check if the neighbors of (row,col) is valid for further move.

Return Types