Scribd
Upload
6 views

Ai Lab Report-2

This lab report focuses on the N-Queen problem, which involves placing N queens on an N×N chessboard such that no two queens threaten each other. The report outlines the objectives, procedures, implementation in Python, and discusses the backtracking approach used to solve the problem. It highlights the significance of the N-Queens problem in computer science and its implications in algorithmic problem-solving.

Uploaded by

Mahmudul Hasan GUB
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Ai Lab Report-2

This lab report focuses on the N-Queen problem, which involves placing N queens on an N×N chessboard such that no two queens threaten each other. The report outlines the objectives, procedures, implementation in Python, and discusses the backtracking approach used to solve the problem. It highlights the significance of the N-Queens problem in computer science and its implications in algorithmic problem-solving.

Uploaded by

Mahmudul Hasan GUB
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Green University of Bangladesh

Department of Computer Science and Engineering (CSE)


Faculty of Sciences and Engineering
Semester: (Spring, Year:2024), B.Sc. in CSE (Day)

Lab Report NO #04


Course Title: Artificial Intelligence Lab
Course Code: CSE 316 Section: 213 D2

Lab Experiment Name: N -Queen Problem.

Student Details

Name ID

Mahmudul Hasan 213002198

Lab Date : 14th May 2024


Submission Date : 5th June 2024
Course Teacher’s Name : Md Naimul Pathan

Lab Report Status


Marks: ………………………………… Signature:.....................
Comments:.............................................. Date:..............................
TITLE OF THE LAB REPORT EXPERIMENT
N -Queen Problem
OBJECTIVES/AIM
• To attain knowledge on the Collab and how it works.
• To gather knowledge on N-Queen for beginners..
• To implement the basics of Python.

PROCEDURE / ANALYSIS / DESIGN Else:


The N-Queens problem is a classic problem in computer science and combinatorial optimization. The problem
can be stated as follows: given an N×NN \times NN×N chessboard, place NNN queens on the board such that no two
queens threaten each other.
• Create an N×NN \times NN×N chessboard (represented as a 2D array) with all cells initialized to 0, indicating that
no queen is placed on the board yet.
• Start placing queens one by one in each column, beginning from the leftmost column.
• If it is not safe to place a queen in any cell of the current column, backtrack to the previous column and try
placing the queen in the next available row of that column.
IMPLEMENTATION :

def is_safe(board, row, col, n):


# Check if there is a queen in the same row on the 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 solve_n_queens_util(board, col, n):
# If all queens are placed then return True
if col >= n:
return True

for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1

# Recur to place rest of the queens


if solve_n_queens_util(board, col + 1, n):
return True
board[i][col] = 0
return False
def solve_n_queens(n):
board = [[0 for _ in range(n)] for _ in range(n)]

if not solve_n_queens_util(board, 0, n):


print("Solution does not exist")
return False
# Print the solution
print("Solution exists and is as follows:")
for i in range(n):
for j in range(n):
print(board[i][j], end=" ")
print()

return True

if __name__ == "__main__":
try:
n = int(input("Enter the size of the chessboard (N): "))
if n <= 0:
raise ValueError("N must be a positive integer")
solve_n_queens(n)
except ValueError as ve:
print("Invalid input:", ve)

Result:

ANALYSIS AND DISCUSSION:


The N-Queens problem is typically solved using a backtracking approach, where you systematically try all possible
configurations and backtrack whenever you reach a dead-end or an invalid configuration. Various optimizations can be
applied to improve the efficiency of the backtracking algorithm, such as early pruning of search space, symmetry
breaking, and using bit manipulation instead of a 2D array to represent the board.
SUMMARY
The N-Queens problem is not only a fascinating puzzle but also an important problem in computer science with practical
implications across various domains. Its solution demonstrates the power of algorithms and problem-solving techniques
in tackling complex challenges.

You might also like