SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
Experiment: 4
PART A
(PART A: TO BE REFFERED BY STUDENTS)
Aim: To Implement backtracking algorithm: N-Queen Problem.
Theory:
Back Tracking
Backtracking name itself suggests that we are going back and coming forward; if it satisfies
the condition, then return success, else we go back again. It is used to solve a problem in
which a sequence of objects is chosen from a specified set so that the sequence satisfies
When to use a Backtracking algorithm?
When we have multiple choices, then we make the decisions from the available choices. In
the following cases, we need to use the backtracking algorithm:
o A piece of sufficient information is not available to make the best choice, so we use
the backtracking strategy to try out all the possible solutions.
o Each decision leads to a new set of choices. Then again, we backtrack to make new
decisions. In this case, we need to use the backtracking strategy.
Applications of Backtracking
o N-queen problem
o Sum of subset problem
o Graph coloring
o Hamiliton cycle
N-Queens Problem
N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no
queens attack each other by being in the same row, column or diagonal.
It can be seen that for n =1, the problem has a trivial solution, and no solution exists for n =2
and n =3. So first we will consider the 4 queen’s problem and then generate it to n - queen’s
problem.
Given a 4 x 4 chessboard and number the rows and column of the chessboard 1 through 4.
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
Since, we have to place 4 queens such as q1 q2 q3 and q4 on the chessboard, such that no two
queens attack each other. In such a conditional each queen must be placed on a different row,
i.e., we put queen "i" on row "i."
Now, we place queen q1 in the very first acceptable position (1, 1). Next, we put queen q2 so
that both these queens do not attack each other. We find that if we place q2 in column 1 and 2,
then the dead end is encountered. Thus the first acceptable position for q2 in column 3, i.e. (2,
3) but then no position is left for placing queen 'q3' safely. So we backtrack one step and place
the queen 'q2' in (2, 4), the next best possible solution. Then we obtain the position for placing
'q3' which is (3, 2). But later this position also leads to a dead end, and no place is found
where 'q4' can be placed safely. Then we have to backtrack till 'q1' and place it to (1, 2) and
then all other queens are placed safely by moving q2 to (2, 4), q3 to (3, 1) and q4 to (4, 3). That
is, we get the solution (2, 4, 1, 3). This is one possible solution for the 4-queens problem. For
another possible solution, the whole method is repeated for all partial solutions. The other
solutions for 4 - queens problems is (3, 1, 4, 2) i.e.
Backtracking Algorithm Method 1:
The idea is to place queens one by one in different columns, starting from the leftmost
column. When we place a queen in a column, we check for clashes with already placed
queens. In the current column, if we find a row for which there is no clash, we mark this
row and column as part of the solution. If we do not find such a row due to clashes, then we
backtrack and return false.
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
Method 1:
1) Start in the leftmost column
2) If all queens are placed
return true
3) Try all rows in the current column.
Do following for every tried row.
a) If the queen can be placed safely in this row
then mark this [row, column] as part of the
solution and recursively check if placing
queen here leads to a solution.
b) If placing the queen in [row, column] leads to
a solution then return true.
c) If placing queen doesn't lead to a solution then
unmark this [row, column] (Backtrack) and go to
step (a) to try other rows.
4) If all rows have been tried and nothing worked,
return false to trigger backtracking.
Backtracking Algorithm Method 2:
The idea is to place queens one by one in different rows, starting from the topmost row.
When we place a queen in a row, we check for clashes with already placed queens. In the
current column, if we find a row for which there is no clash, we mark this row and column
as part of the solution. If we do not find such a row due to clashes, then we backtrack and
return false.
Method 2:
0) Make a board,make a space to collect all solution states.
1) Start in the topmost row.
2) Make a recursive function which takes state of board and the current row number
as its parameter.
3) Fill a queen in a safe place and use this state of board to advance to next recursive
call, add 1 to the current row. Revert the state of board after making the call.
a) Safe function checks the current column, left top diagonal and right top diagonal.
b) If no queen is present then fill else return false and stop exploring that state
and track back to the next possible solution state
4) Keep calling the function till the current row is out of bound.
5) If current row reaches the number of rows in the board then the board is filled.
6) Store the state and return.
Source: https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/
https://www.javatpoint.com/n-queens-problems
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
PART B
(PART B: TO BE COMPLETED BY STUDENTS)
Students must submit the soft copy as per following segments within two hours of the
practical. The soft copy must be uploaded on the portal at the end of the practical. The
filename should be PPS_batch_rollno_experimentno Example: PAI_A1_B001_Exp1
Roll No.: Name:
Prog/Yr/Sem: Batch: A1
Date of Experiment: Date of Submission:
# Python program to solve N Queen
# Problem using backtracking
global N
N=4
def printSolution(board):
for i in range(N):
for j in range(N):
print (board[i][j],end=' ')
print()
# A utility function to check if a queen can
# be placed on board[row][col]. Note that this
# function is called when "col" queens are
# already placed in columns from 0 to col -1.
# So we need to check only left side for
# attacking queens
def isSafe(board, row, col):
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
# 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):
# base case: If all queens are placed
# then return true
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):
# Place this queen in board[i][col]
board[i][col] = 1
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
# recur to place rest of the queens
if solveNQUtil(board, col + 1) == True:
return True
# If placing queen in board[i][col
# doesn't lead to a solution, then
# queen from board[i][col]
board[i][col] = 0
# if the queen can not be placed in any row in
# this column col then return false
return False
# This function solves the N Queen problem using
# Backtracking. It mainly uses solveNQUtil() to
# solve the problem. It returns false if queens
# cannot be placed, otherwise return true and
# placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) == False:
SVKM’s NMIMS University
Mukesh Patel School of Technology Management & Engineering
COURSE: Principles of Artificial Intelligence
print ("Solution does not exist")
return False
printSolution(board)
return True
# driver program to test above function
solveNQ()
