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:
- Initialize an empty chessboard of size
N x N. - Start placing queens on the chessboard, one column at a time.
- Before placing a queen in a column, check if it is safe to place the queen in that position.
- If the queen can be placed safely, proceed to the next column recursively.
- If no safe position is found, backtrack to the previous column and try the next position.
- 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)
Output
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(N2)
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.