[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:



import copy

class (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:

import numpy as np

class (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

return all possible solutions – N-Queen

return if exist any solution – Word Search

Reference

1. N-Queen Problem - GeeksforGeeks

Reference

[algorithms] backtracking

Concepts

Psudo Code

Sample Problems (from LeetCode)

N-Queens (51)

Word Search(79)

Conclusion

Steps

Return Types

近期文章

近期评论

标签

热门

文章归档

分类目录

功能