Name: Gayatri Sandip Sagade
Roll No.2441013
Batch: C
Assignment No.05: Design n-Queens matrix having first Queen placed. Use backtracking to
place remaining Queens to generate the final n-queen's matrix
Program:
def is_safe(board, row, col, n):
# Check this column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper left diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check upper right diagonal
for i, j in zip(range(row, -1, -1), range(col, n)):
if board[i][j] == 1:
return False
return True
def solve_n_queens_util(board, row, n, solutions):
if row == n:
# A solution is found, add the board to the solutions list
solution = []
for i in range(n):
[Link](board[i][:])
[Link](solution)
return
for col in range(n):
if is_safe(board, row, col, n):
# Place the queen
board[row][col] = 1
# Recur to place the rest of the queens
solve_n_queens_util(board, row + 1, n, solutions)
# Backtrack and remove the queen
board[row][col] = 0
def solve_n_queens(n):
board = [[0 for _ in range(n)] for _ in range(n)]
solutions = []
# Start from the first row and find all solutions
solve_n_queens_util(board, 0, n, solutions)
return solutions
def print_solutions(solutions):
count = 1
for solution in solutions:
print(f"Solution {count}:")
for row in solution:
print(row)
print()
count += 1
n = int(input("Enter the value of n for the n-Queens problem: "))
if n < 1:
print("Please enter a valid value for n (n should be >= 1).")
else:
solutions = solve_n_queens(n)
if solutions:
print_solutions(solutions)
else:
print(f"No solutions exist for {n}-Queens.")
#Output:
Enter the value of n for the n-Queens problem: 6
Solution 1:
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
Solution 2:
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
Solution 3:
[0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
Solution 4:
[0, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0]
