Backtracking Algorithm in Python

Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end. The backtracking algorithm is a recursive algorithm that is used to solve problems by making a series of choices, and if a choice leads to a dead end, it backtracks to the last valid choice made and tries a different path. It is often used to solve problems such as the N-Queens puzzle, Sudoku, and the Knight's Tour.

How Does a Backtracking Algorithm Work?

A backtracking algorithm works by recursively exploring all possible solutions to a problem. It starts by choosing an initial solution, and then it explores all possible extensions of that solution. If an extension leads to a solution, the algorithm returns that solution. If an extension does not lead to a solution, the algorithm backtracks to the previous solution and tries a different extension.

The following is a general outline of how a backtracking algorithm works:

1. Choose an initial solution.
2. Explore all possible extensions of the current solution.
3. If an extension leads to a solution, return that solution.
4. If an extension does not lead to a solution, backtrack to the previous solution and try a different extension.
5. Repeat steps 2-4 until all possible solutions have been explored.

Pseudocode:

function backtracking(state):
 if state is a solution:
 return state
 
 for choice in all possible choices:
 if choice is valid:
 make choice
 result = backtracking(state with choice)
 if result is not failure:
 return result
 undo choice
 return failure

It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku. When a dead end is reached, the algorithm backtracks to the previous decision point and explores a different path until a solution is found or all possibilities have been exhausted.

Example of Backtracking Algorithm:

Implement the Backtracking algorithm to solve the N-Queens problem in Python.

Examples:

Input:
N = 4
Output:
[ [".Q..", "...Q", "Q...", "..Q."],
["..Q.", "Q...", "...Q", ".Q.."] ]

Input:
N = 1
Output: [ ["Q"] ]

Step-by-step algorithm:

1. Initialize an empty chessboard of size N x N.
2. Start placing queens on the chessboard, one column at a time.
3. Before placing a queen in a column, check if it is safe to place the queen in that position.
4. If the queen can be placed safely, proceed to the next column recursively.
5. If no safe position is found, backtrack to the previous column and try the next position.
6. Repeat the process until all queens are placed on the chessboard or all possibilities are explored.

Below is the implementation of the above idea:

def is_safe(board, row, col, N): # Check this row on the left side for i in range(col): if board[row][i] == 'Q': 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] == 'Q': 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] == 'Q': return False return True def solve_n_queens(N): board = [['.' for _ in range(N)] for _ in range(N)] result = [] def backtrack(board, col): if col == N: result.append([''.join(row) for row in board]) return for i in range(N): if is_safe(board, i, col, N): board[i][col] = 'Q' backtrack(board, col + 1) board[i][col] = '.' backtrack(board, 0) return result # Example 1 N1 = 4 result1 = solve_n_queens(N1) print(f"Solution for Example 1 with N = {N1}:") for solution in result1: print(solution) print() # Example 2 N2 = 1 result2 = solve_n_queens(N2) print(f"Solution for Example 2 with N = {N2}:") for solution in result2: print(solution) 

Solution for Example 1 with N = 4: ['..Q.', 'Q...', '...Q', '.Q..'] ['.Q..', '...Q', 'Q...', '..Q.'] Solution for Example 2 with N = 1: ['Q'] 

Time Complexity: O(N!)
Auxiliary Space: O(N²)

Related Practice Problem on Backtracking: