Write a program that solves N-Queen Problem in python which involves placing N queens on an NxN chessboard in such a way that no two queens can attack each other.
Introduction
The N-Queens problem is a classic problem in computer science and mathematics that involves placing N queens on an NxN chessboard in such a way that no two queens can attack each other. The problem is a popular topic in programming interviews and competitions and can be solved using different algorithms such as the brute-force approach backtracking and recursive techniques.
In this blog post we will walk through how to write a program that solves the N-Queens problem using a backtracking algorithm. We will break down the problem into manageable steps and explain each step in detail to help you understand the solution. By the end of this post you will have a working program that solves the N-Queens problem.
- Program to Create Snake Game in Python
- Write a Program to Create Hangman Game in Python
- Program to Create Tic Tac Toe Game in Python
- Program to Create BlackJack Game in Python
- Program to Solve Traveling Salesman Problem in Python
Step 1: Create the Board
The first step is to create the chessboard which is an NxN matrix. We will use a two-dimensional array to represent the board where each cell is either empty or contains a queen. We will initialize all the cells to be empty at the beginning of the program.
Step 2: Check if a Position is Safe
The next step is to check if a given position is safe to place a queen. A position is safe if no other queen can attack it horizontally vertically or diagonally. To check if a position is safe we need to check if there are any queens in the same row, column or diagonal. We can do this by iterating over the board and checking each cell in the same row, column, and diagonals.
Step 3: Place the Queen
If we find a safe position to place a queen, we can place the queen in that position. We will mark the cell as containing a queen, and we will continue to the next row to place the next queen. If we cannot find a safe position to place the queen, we need to backtrack to the previous row and try a different position.
Step 4: Backtrack
If we reach a point where we cannot place any queen in a row we need to backtrack to the previous row and try a different position. To backtrack we will remove the queen from the current position mark it as empty and go back to the previous row to try a different position.
Step 5: Solve the Problem
The final step is to solve the N-Queens problem. We will start by placing the first queen in the first row and we will try to place the remaining queens in the subsequent rows. We will use a recursive function to solve the problem which will continue until we have placed all N queens on the board. Once we have placed all N queens on the board we will print the solution.
Code Implementation
Here is the complete code to solve the N-Queens problem in python using backtracking.
def print_board(board):
for row in board:
print(' '.join(row))
def is_safe(board, row, col):
# check row
for i in range(col):
if board[row][i] == 'Q':
return False
# check upper diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
# check lower diagonal
for i, j in zip(range(row, len(board)), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
return True
def solve_n_queens(board, col):
if col == len(board):
print_board(board)
return True
else:
for i in range(len(board)):
if is_safe(board, i, col):
board[i][col] = 'Q'
solve_n_queens(board, col + 1)
board[i][col] = '.'
return False
def n_queens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
solve_n_queens(board, 0)
n = int(input("Enter the size of the chessboard: "))
n_queens(n)
Explanation of the Code:
The print_board() function takes in a board as input and prints it out row by row. The function is used to print the final solution.
The is_safe() function checks if it is safe to place a queen at a given position (row, col) on the board. It checks if there is no queen in the same row upper diagonal and lower diagonal. The function returns True if the position is safe, and False otherwise.
The solve_n_queens() function is the core of the program. It takes in a board and a col as inputs. The col represents the current column, and we start with col = 0. The function first checks if we have placed all the queens on the board (col == len(board)). If yes, we print the solution and return True. If not, we iterate over each row and check if it is safe to place a queen at (row, col). If it is safe, we place a queen at that position, and we recursively call the solve_n_queens() function with the next column (col + 1). If we cannot place a queen at any row, we backtrack to the previous column and try a different row. To backtrack, we remove the queen from the current position, mark it as empty and try the next row. If we have tried all rows and cannot place a queen, we return False.
The n_queens() function takes in the size of the chessboard (n) as input creates an empty board and calls the solve_n_queens() function with the initial column (col = 0).
Conclusion
In this post we have discuss how to solve the N-Queens problem using a backtracking algorithm. We have broken down the problem into manageable steps and explained each step in detail. We have also provided a complete code implementation in Python. By following the steps and understanding the code you should now be able to solve the N-Queens problem on your own.