In this assignment, you will tormulate the NQueens problem as a search problem and solve it using

traditional search algorithms:

Breadth$-$First Search $($BFS$),$

Uniform Cost Search $($UCS$),$

Depth First Search$($DFS$),$

Depth Limited Search $($DLS$),$

Iterative Deepening Search $($IDS$),$

Greedy Search, and A$*$ Search.

assume that you are allowed to move a single queen in its column at each step and

each move is of cost $1.$ In other words, each action will be in the form of "Move Queen $i$ to row $j",$ where

$1i,jN.$

$3\mathrm{.}1$ Implementation

Use your solution to PA$1$ and do the following modifications.

You have to define NQueens class as a child of abstract SearchProblem $($see

models.py$).$

There are $3$ main functions $($actions$,$ is$\_$goal, result$)$ that you have to implement for uninformed

search algorithms, and one function $($heuristic$)$ for informed search algorithms. $($In addition to

these functions, you may define internal helper functions if you need.$)$

$\_\_$init$\_($self$,N)$: Class constructor that initializes the attributes. Calls parent class constructor

with the initial state. The initial state can be randomly generated or initialized by the user as

before. You can define the list of all possible actions here $($as in missioners example$).$

actions$($self$,$ state$)$: Returns the list of possible actions from the state given as parameter.

result$($self$,$ state, action$)$: Computes and returns the resulting new state when the given action is

performed from the given state.

is$\_$goal$($self$,$ state$)$: Returns whether the state given as parameter is a goal state. Note that a

goal state is a state on which the number of attacking pairs is $0.($Hint: You already implemented

this in PA$1.)$

heuristic $($self$,$ state$)$: Returns the estimated solution cost from the given state to the goal state.

You can use the number of attacking pairs in the given state as a heuristic function.

A template class definition for NQueens is given in Figure $1.***$ Uninformed Search Algorithms $***$

$**********************************$

import random

#class definition for NQueens

class NQueens$()$:

def $\_\_$init$\_\_($self$,$ N$)$:

self.N $=$ N

self.$\_$set$\_$state$()$

def $\_\_$str$\_\_($self$)$:

return f$"$N: $\{$self$.$N$\},$ state: $\{$self$.$state$\}"$

def $\_$set$\_$state$($self$)$:

state$\_$answer $=$ input$("$Enter $1$ for Manuel Entrance, $0$ for Random State:"$)$

if state$\_$answer $=="0"$:

self.state $=$ self.generate$\_$random$\_$state$()$

elif state$\_$answer $=="1"$:

state$\_$temp $=$ input$("$enter state: $")$

if self.$\_$is$\_$valid$($state$\_$temp$)$:

self.state $=$ state$\_$temp

else:

self.state $=$ "wrong state"

else:

self.state$=$"wrong entry"

def generate$\_$random$\_$state$($self$)$:

random$\_$state $=""$

for i in range$($self$.$N$)$:

str$\_$val $=$ random.randint$(1,$self.N$)$

random$\_$state$+=$ str$($str$\_$val$)$

return random$\_$state

def $\_$is$\_$valid$($self$,$state$)$:

if len$($state$)!=$ self.N :

print$("$The length of the state string is not equal to N$.")$

return False

for i in range$($len$($state$))$:

try:

if $($int$($state$[$i or $($int$($state$[$i$])>$ self.N$)$:

print$("$State string includes numbers greater than N or less than $1.")$

return False

except:

return False

return True

def $\_$count$\_$attacking$\_$pairs$($self$,$

state$)$:

if self.$\_$is$\_$valid$($self$.$state$)$:

atacking$\_$pairs $=0$

for index,state$\_$indexed in enumerate$($state$)$:

for index$1,$ state$\_$indexed$1$ in enumerate$($state$)$:

if index $$ index$1$:

coordinate $=[$index$+1,$int$($state$\_$indexed$)]$

coordinate$\_1=[$index$1+1,$int$($state$\_$indexed$1)]$

if $($abs$($coordinate$[0]-$coordinate$\_1[0])==$ abs$($coordinate$[1]-$coordinate$\_1[1]))$ or $($coordinate$[0]==$ coordinate$\_1[0])$ or $($coordinate$[1]==$ coordinate$\_1[1])$:

atacking$\_$pairs$+=1$

return atacking$\_$pairs

return "Error"

problem $=$ NQueens$(5)$ #create NQueens instance

print$($problem$)$ #print the description of the problem

print$($problem$.\_$count$\_$attacking$\_$pairs$($problem$.$state$))$

$-----------$

Output Should be like this:

Graph search? True

BFS

Resulting path:

$[($None$,\text{'}1432\text{'}),((\text{'}$Move queen $1$ to row $2\text{'},1,2),\text{'}2432\text{'}),((\text{'}$Move

Resulting state: $2413$

Total cost: $3$

Viewer stats:

$\{\text{'}$max$\_$fringe$\_$size': $120,$ 'visited$\_$nodes': $87,$ 'iterations': $87$