Chapter 9: Algorithm Design Techniques

9.3 Backtracking

Backtracking is a very useful algorithmic technique that can solve a wide range of complex problems in a reasonable amount of time. It is commonly used in decision-making problems where the set of potential choices can be organized into a decision tree or graph.

The basic idea behind backtracking is to construct a solution one step at a time while checking to see if each step contributes to the overall solution. If a step does not contribute to the solution, it is removed, and the next step is attempted.

One great example of a problem that can be solved using backtracking is the N-Queens puzzle. This puzzle requires the placement of N queens on an NxN chessboard in such a way that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. By using backtracking, it is possible to find a solution to this problem.

Backtracking can also be used in other types of problems, such as finding the shortest path in a maze or identifying the best combination of items to pack in a knapsack. Overall, backtracking is a powerful tool that can help solve many different types of problems in a systematic and efficient manner.

Here is a simple Python solution:

def isSafe(board, row, col, N):
    # Check this row on left side
    for i in range(col):
        if board[row][i] == 1:
            return False

    # Check upper diagonal on left side
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Check lower diagonal on left side
    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True

def solveNQUtil(board, col, N):
    if col >= N:
        return True

    for i in range(N):
        if isSafe(board, i, col, N):
            board[i][col] = 1

            # recur to place rest of the queens
            if solveNQUtil(board, col + 1, N) == True:
                return True

            # if placing queen in board[i][col] doesn't lead to a solution,
            # then remove queen from board[i][col]
            board[i][col] = 0

    return False

def solveNQ(N):
    board = [[0]*N for _ in range(N)]

    if solveNQUtil(board, 0, N) == False:
        print("Solution does not exist")
        return False

    for i in range(N):
        for j in range(N):
            print (board[i][j], end = " ")
        print()

    return True

# test
solveNQ(4)

In this code, solveNQUtil is a recursive function that uses backtracking. It takes a partial solution (the board), and a column number col as arguments. It tries to place a queen in all cells of the current col, and then recurs for the next column. If no placement is possible in the current column, it returns False. If a placement is possible, it places a queen and recurs for the next column.

Backtracking is a powerful technique used to solve complex problems that may not have direct solutions or methods available. Essentially, this method entails making a choice, and if it doesn't lead to a solution, undoing (backtracking on) that choice. The idea behind this methodical trial and error is that it enables the problem solver to explore various alternatives that might lead to a solution.

In the case of the board array, if there is no queen that can be placed in the next column, the algorithm removes the queen from the current cell and backtracks to try the next alternative in its column. This process continues until a solution is found or all alternatives have been exhausted. The beauty of backtracking is that it allows the problem solver to systematically explore various options and rule out those that do not work, thus increasing the chances of finding an optimal solution.

In summary, backtracking is a powerful and effective problem-solving technique that can help solve complex problems that may not have direct solutions or methods available. By systematically exploring different alternatives and backtracking on choices that do not lead to solutions, problem solvers can increase their chances of finding optimal solutions.

Indeed, backtracking is a fascinating concept that can be applied to many different problems. Besides the N-Queens problem we discussed, it can also be used to solve puzzles like Sudoku, finding the shortest path in a maze, permutation of a given string, and many others.

It's important to understand that while backtracking can be an efficient way to find solutions, it isn't always the best approach. For problems with large input spaces, backtracking can lead to inefficient solutions since it operates in an exhaustive manner. There are a lot of different factors that can influence whether or not backtracking is the best approach to solve a problem.

Also, another important thing to keep in mind when using backtracking is to carefully design your stopping condition. Because backtracking operates by recursively checking solutions, if you don't properly define when your function should stop, you may end up with an infinite loop or unnecessarily long computations.

Backtracking is a critical tool in an algorithm designer's toolbox, but like any other tool, it should be used with understanding and care. Mastering it requires a lot of practice and problem-solving, so I encourage you to try solving a variety of problems to get a good grasp of when and how to use it effectively.