Create a n n grid, with four actions namely A = f up, down, left, rightg (some actions are not allowed in the corner states). The grid also contains certain blocked or unreachable locations (actions that lead to blocked locations are not allowed). Your code should accept as inputs (i) the number of blocked locations and (ii) the blocked locations in the form of (x; y) coordinates. Your code should also accept as inputs (i) start-state S (ii) set of goal states G.
(Q1) [25 Marks] Find a path from start state to goal state for the above two cases using breadth-first-search
(Q2) [25 Marks] Find a path from start state to goal state for the above two cases using depth-first-search
For both BFS and DFS use the Graph-Based search strategy, i.e., maintain a explored list. Further, to obtain the BFS and DFS variation, please make use of a counter and a priority queue. You have to print the status of the search at every step. Please use colour based coding or number based coding to distinguish between start (say red or 0), goal (say green or 1), blocked (say black or 1), explored (say yellow or 2), frontier (say blue or 3).
(Q3) [50 Marks] Consider the following puzzle, where s stands for empty space. There are 2 empty spaces which can be slid up, down, right or left. To keep things simple, assume that at each step only one of the space can move (this way any simultaneous move involve both spaces can be thought of as 2 individual moves).
2
6
s
4
3
7
5
s
1
Use Graph-Based BFS to start from any given random position to the goal state given below:
1
2
3
4
5
6
7
s
s
You should print (i) the total number of steps taken to reach the goal, (ii) the action performed (movement of the empty space) at each step (iii) puzzle configuration at each step from start to goal.
Note: In (Q1), (Q2) you have to print the way the algorithm progresses. In (Q3) you have to print the execution of the solution, i.e., how do we reach from start to goal.
