N - Queen Algorithm (Artificial Intelligence LAB)
Problem Statement:
Implement a solution for a Constraint Satisfaction Problem using Branch and Bound and
Backtracking for n-queens problem or a graph coloring problem.
Objectives:
1.To study Constraint Satisfaction Problem using Branch and Bound Algorithms
Theory:
We have seen so many techniques like Local search, Adversarial search to solve different
problems. The objective of every problem-solving technique is one, i.e., to find a solution to
reach the goal. Although, in adversarial search and local search, there were no constraints on the
agents while solving the problems and reaching to its solutions. In this section, we will discuss
another type of problem-solving technique known as Constraint satisfaction technique. By the
name, it is understood that constraint satisfaction means solving a problem under certain
constraints or rules. Constraint satisfaction is a technique where a problem is solved when its
values satisfy certain constraints or rules of the problem. Such type of technique leads to a
deeper understanding of the problem structure as well as its complexity.
Constraint satisfaction depends on three components,
Graph coloring problem involves assigning colors to certain elements of a graph subject to
certain restrictions and constraints. In other words, the process of assigning colors to the vertices
such that no two adjacent vertexes have the same color is caller Graph Coloring. This is also
known as vertex coloring. Graph coloring (also called vertex coloring) is a way of coloring a
graph’s vertices such that no two adjacent vertices share the same color. This post will discuss a
greedy algorithm for graph coloring and minimize the total number of colors used.
K–colorable graph:
A coloring using at most k colors is called a (proper) k–coloring, and a graph that can be
assigned a (proper) k–coloring is k–colorable.
K–chromatic graph:
The smallest number of colors needed to color a graph G is called its chromatic number, and a
graph that is k–chromatic if its chromatic number is exactly k
N-Queens Problem
Implement N Queen's problem using Back Tracking
Backtracking is finding the solution of a problem whereby the solution depends on the previous
steps taken. For example, in a maze problem, the solution depends on all the steps you take oneby-one. If any of those steps is wrong, then it will not lead us to the solution. In a maze problem,
we first choose a path and continue moving along it. But once we understand that the particular
path is incorrect, then we just come back and change it. This is what backtracking basically is.In
backtracking, we first take a step and then we see if this step taken is correct or not i.e., whether
it will give a correct answer or not.
N Queen Problem: N Queens Problem is a famous puzzle in which n-queens are to be placed on
a nxn chess board such that no two queens are in the same row, column or diagonal. The N
Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens
attack each other
Algorithm for N Queens Problem
Step 1: Start
Step 2: Given n queens, read n from user and let us denote the queen number by k. k=1,2,..,n.
Step 3: We start a loop for checking if the k<sup>th</sup> queen can be placed in the respective
column of the k<sup>th</sup> row.
Step 4: For checking that whether the queen can be placed or not, we check if the previous
queens are not in diagonal or in same row with it.
Step 5: If the queen cannot be placed backtracking is done to the previous queens until a feasible
solution is not found.
Step 6: Repeat the steps 3-5 until all the queens are placed.
Step 7: The column numbers of the queens are stored in an array and printed as a n-tuple solution
Step 8: Stop
Conclusion:
Successfully implemented constraint satisfaction algorithm
global N
N = 4
def printSolution(board):
for i in range(N):
for j in range(N):
print (board[i][j],end=' ')
print()
def isSafe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
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):
if col >= N:
return True
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
if solveNQUtil(board, col + 1) == True:
return True
board[i][col] = 0
return False
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) == False:
print ("Solution does not exist")
return False
printSolution(board)
return True
solveNQ()
G = [[ 0, 1, 1, 0, 1, 0],
[ 1, 0, 1, 1, 0, 1],
[ 1, 1, 0, 1, 1, 0],
[ 0, 1, 1, 0, 0, 1],
[ 1, 0, 1, 0, 0, 1],
[ 0, 1, 0, 1, 1, 0]]
node = "abcdef"
t_={}
for i in range(len(G)):
t_[node[i]] = i
degree =[]
for i in range(len(G)):
degree.append(sum(G[i]))
colorDict = {}
for i in range(len(G)):
colorDict[node[i]]=["Blue","Red","Yellow","Green"]
sortedNode=[]
indeks = []
for i in range(len(degree)):
_max = 0
j = 0
for j in range(len(degree)):
if j not in indeks:
if degree[j] > _max:
_max = degree[j]
idx = j
indeks.append(idx)
sortedNode.append(node[idx])
theSolution={}
for n in sortedNode:
setTheColor = colorDict[n]
theSolution[n] = setTheColor[0]
adjacentNode = G[t_[n]]
for j in range(len(adjacentNode)):
if adjacentNode[j]==1 and (setTheColor[0] in colorDict[node[j]]):
colorDict[node[j]].remove(setTheColor[0])
for t,w in sorted(theSolution.items()):
print("Node",t," = ",w)
