Parallel Backtracking

In this article, we have covered the Parallel Backtracking algorithm. We have presented the Time and Space Complexity for various cases.

Table of contents:

1. Introduction to Parallel Backtracking
2. Solving the N-Queen problem using Parallel Backtracking
3. Time and Space Complexity
4. Conclusion

Introduction to Parallel backtracking

Parallel backtracking is a problem-solving technique that involves searching through a large number of potential solutions in parallel. The objective is to find a solution that meets a set of constraints or conditions.

The search in a traditional backtracking algorithm is done sequentially, with the algorithm exploring one path at a time, going deeper and deeper into the solution space until it finds a solution or exhausts all possibilities. For large problems, this can be time-consuming and inefficient.

Parallel backtracking, on the other hand, employs multiple processors or threads to work on different parts of the solution space at the same time. This enables the algorithm to explore multiple paths at the same time, significantly speeding up the search process.

One approach is to divide the solution space into smaller sub-spaces and assign each sub-space to a separate processor or thread to implement parallel backtracking. Each processor or thread then works independently on its assigned sub-space, employing its own backtracking algorithm.

Another approach is to use a work-stealing algorithm, in which each thread starts from a different starting point and attempts to find a solution; when one thread exhausts its solution space, it steals work from other threads that have not completed.

Parallel backtracking can be used to solve puzzles, find optimal solutions in games, schedule tasks, and solve other combinatorial optimization problems.

Solving the N-Queen problem using Parallel Backtracking

The concurrent.futures module in Python will be used to solve the n-queen problem using a parallel backtracking algorithm. The concurrent.futures module allows you to run function calls asynchronously, allowing you to use multiple threads or processes in parallel.

Here's an example of how the concurrent.futures module could be used to solve the n-queen problem using a parallel backtracking algorithm:

solve_nqueens(n) is a function that takes an integer n as an argument and returns the number of queens to place on a n x n chessboard. First, the function defines two helper functions:

• is_valid(board, row, col): This function determines whether it is safe to place a queen on the board at the given (row, col) position. Iterating over the rows of the board, it looks for queens in the same column or on diagonals to check for clashes with other queens.

• solve(board, col): Backtracking is used to find all solutions to the n-queen problem. As inputs, the function takes the board and the current col. It begins by placing queens in the current col, and for each row in the col, it determines whether or not it is valid to place a queen in that row; if so, it places the queen and calls the solve function recursively for the next col; if not, it backtracks and tries the next row.

from concurrent.futures import ThreadPoolExecutor, as_completed
from prettytable import PrettyTable

def solve_nqueens(n):
    def is_valid(board, row, col):
        # check if a queen can be placed at board[row][col]
        # check the rows and columns
        for i in range(n):
            if board[row][i] or board[i][col]:
                return False
        # check diagonals
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j]:
                return False
        for i, j in zip(range(row, -1, -1), range(col, n)):
            if board[i][j]:
                return False
        return True

    def solve(board, col):
        if col >= n:
            return [board[i][:] for i in range(n)]
        solutions = []
        for row in range(n):
            if is_valid(board, row, col):
                board[row][col] = 1
                solutions += solve(board, col + 1)
                board[row][col] = 0
        return solutions

    board = [[0] * n for _ in range(n)]
    solutions = solve(board, 0)
    return solutions

Next, we create an instance of ThreadPoolExecutor from the concurrent.futures module, which allows multiple function calls to be executed in parallel using a pool of worker threads. It calls the submit method to request that the solve function be run asynchronously by one of the worker threads.

The max_workers parameter specifies the maximum number of threads that can be used concurrently. You can change this value based on the number of CPU cores in your machine. If you set a value that is greater than the number of cores, performance may suffer.

The as_completed function is used to loop through completed tasks and retrieve their solutions. This function takes a list of futures objects and returns an iterator that returns the futures as they finish.

Finally, it returns a list of solutions that includes all possible ways to place n queens on the board without clashes.

def parallel_solve_nqueens(n, num_threads):
    with ThreadPoolExecutor(max_workers=num_threads) as executor:
        futures = [executor.submit(solve_nqueens, n) for _ in range(num_threads)]
        for future in as_completed(futures):
            yield from future.result()

The prettyprint() function is used to present the solution in a table format. As there are many solutions that can be available, the function accept the input display_sol to display x numbers of solutions

def prettyprint(solutions, display_sol):
    x = PrettyTable()
    x.field_names = ["0","1","2","3", "4", "5", "6", "7"]
    for idx, sol in enumerate(solutions):
        if ((idx+1) / 8 <= display_sol):
            sol = ["Q" if x == 1 else "." for x in sol]
            x.add_row(sol)
            if ((idx+1) % 8 ==0):
                print(f"Solution {int((idx+1)/8)}")
                print(x)
                x.clear_rows()        
# Example usage
n = 8
num_threads = 4
display_sol = 5
solutions = list(parallel_solve_nqueens(n, num_threads))
print(f'Found {int(len(solutions)/8)} solutions for {n}-Queens problem. \nDisplaying the first {display_sol} below.')
prettyprint(solutions,display_sol)

Time and Space Complexity

The time complexity of the parallel backtracking algorithm for solving the n-queen problem with Python's concurrent.futures module is O(n^n). This is because the algorithm still needs to explore all possible queen combinations on the board, and this number grows exponentially with board size.

The algorithm only needs to store the current state of the board and the solutions, which each take O(n) space, the space complexity is the same as the sequential backtracking algorithm, which is O(n).

Conclusion

In practice, a parallel backtracking algorithm using concurrent.futures can be faster than a sequential backtracking algorithm, especially for large values of n, because it allows the algorithm to explore multiple solutions concurrently, rather than waiting for one solution to be completed before beginning the next. This can result in significant speed increases, particularly on machines with multiple cores or processors.

With this article at OpenGenus, you must have the complete idea of Parallel Backtracking Algorithm.