OpenSource Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have covered the Parallel Backtracking algorithm. We have presented the Time and Space Complexity for various cases.
Table of contents:
 Introduction to Parallel Backtracking
 Solving the NQueen problem using Parallel Backtracking
 Time and Space Complexity
 Conclusion
Introduction to Parallel backtracking
Parallel backtracking is a problemsolving 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 timeconsuming 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 subspaces and assign each subspace to a separate processor or thread to implement parallel backtracking. Each processor or thread then works independently on its assigned subspace, employing its own backtracking algorithm.
Another approach is to use a workstealing 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 NQueen problem using Parallel Backtracking
The concurrent.futures
module in Python will be used to solve the nqueen
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 nqueen
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 nqueen 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 nqueen 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.