- [email protected]
- April 14, 2023
- 11:45 am
- No Comments
N-Queens Problem Code With Python
The N-Queens Problem has applications in fields such as computer science, mathematics, and game theory. It is a classic problem that helps to develop problem-solving skills and understanding of algorithms and data structures
Objective
In the N-Queens Problem, the goal is to place N queens on an NxN chessboard so that no two queens are attacking each other. A queen can attack any other piece that is in the same row, column, or diagonal as itself. The problem can be solved using a backtracking algorithm that tries all possible configurations of queens on the board until a valid solution is found.
The solution involves placing one queen in each row of the board such that no two queens share the same column, and no two queens share the same diagonal. The algorithm recursively explores all possible configurations of queens on the board until a valid solution is found or all configurations have been explored.
algorithms, such as depth-first search or breadth-first search, to explore all possible paths through the maze until a path from the starting position to the ending position is found.
def print_board(board):
# Function to print the board to the console
for row in board:
print(row)
def n_queens(n):
def backtrack(board, col):
# Backtracking function to generate all possible solutions
nonlocal solutions
if col == n:
# Base case: all queens have been placed on the board
solutions.append([row[:] for row in board])
# Add the current board configuration to the solutions list
return
for i in range(n):
if is_valid(board, i, col):
# If the current cell is valid, place a queen there
board[i][col] = 1
backtrack(board, col + 1)
# Recursively call the backtrack function with the next column
board[i][col] = 0
# Backtrack by removing the queen from the current cell
def is_valid(board, row, col):
# Function to check if placing a queen in the current cell is valid
for i in range(col):
if board[row][i] == 1:
# Check the current row for other queens
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
# Check the diagonal going up and to the left
return False
for i, j in zip(range(row, n), range(col, -1, -1)):
if board[i][j] == 1:
# Check the diagonal going down and to the left
return False
return True
solutions = []
board = [[0] * n for i in range(n)]
backtrack(board, 0)
# Generate all possible solutions using the backtrack function
for solution in solutions:
# Print each solution to the console
print_board(solution)
print()
# Print a newline character for readability