Introduction
The N Queens problem is a classic example of a puzzle that has fascinated both computer scientists and students for years. It's all about placing N queens on an N×N chessboard in such a way that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. The beauty of this problem lies in its simplicity & the complexity of its solutions.
In this article, we're looking into the Python solution for the N Queens problem, exploring how backtracking—a fundamental concept in computer science—plays a crucial role.
Python Program for N Queen Problem | Backtracking-3
Now, we're going to tackle the N Queens problem using Python, focusing on a method called backtracking. Think of backtracking as a way to make decisions, step by step, and if you hit a dead end, you just step back and try a different path. It's like navigating a maze where you choose a route, and if you face a wall, you backtrack to the last decision point and take a different turn.
Here's a simple Python program that solves the N Queen problem using backtracking. The program defines a board using a 2D list, where zeros represent empty spaces and ones represent queens. The solution involves placing a queen on the board and then checking for conflicts. If a conflict is found, the queen is removed, and a new position is tried.
- Python
Python
def isSafe(board, row, col, n):
# Check this row on left side
for i in range(col):
if board[row][i] == 1:
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] == 1:
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] == 1:
return False
return True
def solveNQUtil(board, col, n):
# base case: If all queens are placed
if col >= n:
return True
# Consider this column and try placing this queen in all rows one by one
for i in range(n):
if isSafe(board, i, col, n):
# Place this queen in board[i][col]
board[i][col] = 1
# recur to place rest of the queens
if solveNQUtil(board, col + 1, n) == True:
return True
# If placing queen in board[i][col] doesn't lead to a solution, then remove queen from board[i][col]
board[i][col] = 0 # BACKTRACK
# If the queen cannot be placed in any row in this column, return False
return False
def solveNQ(n):
board = [[0] * n for _ in range(n)]
if solveNQUtil(board, 0, n) == False:
print("Solution does not exist")
return False
# A utility function to print solution
for i in board:
print(i)
return True
# Driver Code
n = 4
solveNQ(n)
Output
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
In this code:
- isSafe() checks if a queen can be placed on the board without any conflicts.
- solveNQUtil() is where backtracking happens, trying to place queens column by column.
- solveNQ() sets up the board and starts the process by calling solveNQUtil().
- Run this code with n = 4 (or any number you like), and it will print a solution to the N Queens problem, with 1s representing the queens.
- Remember, this is just one of the many solutions, and backtracking ensures we find one that works.
7+ registered 
