Implementing Backtracking Search Algorithm to solve CSP

Here’s a Python implementation of a backtracking search algorithm to solve a simple CSP: the N-Queens problem.

Step 1: Define “is_safe” function

• This function checks if it’s safe to place a queen at the position board[row][col].

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

# Check upper diagonal on the 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 the left side
for i, j in zip(range(row, N), range(col, -1, -1)):
if board[i][j] == 1:
return False

return True

Step 2: Define the solve_n_queens Function

• This function attempts to solve the N-Queens problem by placing queens one column at a time.
• It uses recursion to place queens and backtracks if a solution cannot be found.

def solve_n_queens(board, col, N):
# Base case: If all queens are placed, return True
if col >= N:
return True

# Consider this column and try placing the queen in all rows one by one
for i in range(N):
if is_safe(board, i, col, N):
# Place the queen
board[i][col] = 1

# Recur to place the rest of the queens
if solve_n_queens(board, col + 1, N):
return True

# If placing queen in board[i][col] doesn't lead to a solution, backtrack
board[i][col] = 0

# If the queen cannot be placed in any row in this column, return False
return False

Step 3: Define the print_board Function

• This function prints the board configuration with queens placed.

def print_board(board, N):
for i in range(N):
for j in range(N):
print("Q" if board[i][j] == 1 else ".", end=" ")
print()

Step 4: Define the n_queens Function

• This function initializes the board and calls the solve_n_queens function to solve the problem.
• If a solution is found, it prints the board. Otherwise, it indicates that no solution exists.

def n_queens(N):
# Initialize the board
board = [[0] * N for _ in range(N)]

if solve_n_queens(board, 0, N):
print_board(board, N)
else:
print("No solution exists")

Complete code for Backtracking Search Algorithm to solve CSP

Output:

Constraint Satisfaction Problems (CSPs) are a fundamental topic in artificial intelligence and computer science. They involve finding a solution that meets a set of constraints or conditions. Backtracking search is a powerful technique used to solve these problems.

In this article, we will explore the concept of backtracking search, its application in CSPs, and its advantages and limitations.