Iomework solutions must be submitted through Canvas. Only pdf, word, and txt files are allowed. If you have multiple pictures, please include all pictures in one Word/pdf file. You can always update your submissions before due date, but only the latest version will be graded.] 1. [1 pt] The goal of the 4-queens problem is to place 4 queens on a 4 rows 4 columns chessboard, such that no two queens attach each other. One solution to the 4-queens problem is shown in Figure 1. Design a search-based solution to solve the 4-queens problem. Your solution must include following four components: a. Define state and show examples of three states (including initial state and goal state) [0.25 pt] b. Define a successor function, and estimate total number of states, based on the defined successor function [0.25 pt] c. Show state graph with at least five states and their relationships (the graph must have a path from initial state to goal state) [0.25pt] d. Show how to find solution(s) from the state graph [0.25pt] 2. [2 pts]. Figure 2 shows a state graph with five states. Assume that "a" is the initial state, and " G " is the goal state. a. Use Breath First Search (BFS) to build a search tree to carry out search from the initial state to the goal state (Show complete search tree). [1 pt] i. Mark order of the search node (on the BFS tree) being visited from initiate state to find the goal state (break tie in favor of node with a lower alphabetic order, e.g., "b" has a higher priority than "c"). ii. Is the solution optimal? Why or why not? iii. Explain why avoiding revised state is important in creating BFS search tree. b. Use Depth First Search (BFS) to build a search tree to carry out search from the initial state to the goal state (Show complete search tree). [1 pt] i. Mark order of the search node (on the BFS tree) being visited from initiate state to find the goal state (break tie in favor of node with a lower alphabetic order, e.g., "b" has a higher priority than "c"). ii. Is the solution optimal? Why or why not? iii. Explain why avoiding revised state is important in creating DFS search tree. Figure 3 3. [1.5 pts] Figure 3 shows a stage graph with 9 states. Create a search tree (using Breath First Search (BFS) algorithm) to traverse the state graph from "a". a. Show complete BFS search three with at least three levels (root, 1st, and 2nd ). If multiple nodes are created for same state, say "f", use f1,f2,f3, etc., to denote each node (the number corresponding to node being created). Break tie in favor of node with a lower alphabetic order, e.g., "b" has a higher priority than "c". [0.5 pt] b. Report the order of the nodes being visited, and the Fringe structure (report fringe structure of each step as show in the table below) [0.5pt]. c. Compare the fringe structure and explain the memory consumption of each method, with respect to branching factor (b) and the search depth (d)[0.5pt]. Set all nodes to "not visited"; q= new Queue( ) q.enqueue(initial node); Figure 4: Breath First Search (BFS) 4. [1.5 pts] Figure 3 shows a stage graph with 9 states. Create a search tree (using Depth First Search (DFS) algorithm showing in Figure 5) to traverse the state graph from "a". a. Show complete DFS search three with at least three levels (root, 1st, and 2nd ). If multiple nodes are created for same state, say "f", use f1, f2,f3, etc., to denote each node (the number corresponding to node being created). Break tie in favor of node with a lower alphabetic order, e.g., "b" has a higher priority than "c". [0.5 pt] b. Report the order of the nodes being visited, and the Fringe structure (report fringe structure of each step as show in the table below) [0.5pt]. c. Compare the fringe structure and explain the memory consumption of each method, with respect to branching factor (b) and the search depth (d)[0.5pt]. 123456789procedureDFS-iterative(G,V):letSbeastackS.push(V)whileSisnotemptyV=S.pop()ifvisnotlabeledasdiscovered:labelvasdiscoveredforalledgesfromvtowinG.adjacentEdges(v)do Figure 5 Depth First Search DFS 5. [ 3 pts] Figure 6 shows a robot navigation field, where the red square (d2) is the robot, and green square (d4) is the goal. The shad squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Node are coded using an alphabet letter followed by a digit (such as a0, b1, b2 etc.). When two sibling nodes are inserted into fringe (queue), use deque order to favor node with a lower alphabet and a lower digit. For example, if d1 and e2 are sibling nodes, d1 will be dequeued first (because "d" has a lower alphabetic order than "e"). If al and a2 are sibling nodes, a1 will be dequeued first (because "1" has a lower digit than "2"). Node expanded/visited does not need to be revisited. - Use Depth First Search to find path from d2 to d4. - Report nodes in the fringe in the orders they are included in the fringe. [0.5pt] - Report the order of the nodes being expanded. [0.5pt] - Report the final path from d 2 to d4. [0.5 pt] - Use Breadth First Search to find path from d2 to d4. - Report nodes in the fringe in the orders they are included in the fringe. [0.5pt] - Report the order of the nodes being expanded. [0.5pt] - Report the final path from d2 to d4. [0.5 pt] For all programming tasks, please submit the Notebook as html or pdf files for grading (your submission must include scrips/code and the results of the script). For each subtask, please use task description (requirement) as comments, and report your coding and results in following format: M \# Report all samples with respect to the crim index on a plot (the x-axis shows the index of the sample, and the y-axis \# shows the crim index of the sample). y= boston [ 'Crim' ] x=np. arange( (y shape[e] ] \# generate x index plt. scatter (x,y, marker =00) : 6. [2 pts] The "Blind Search to Play Maze [Notebook, html]" posted on Canvas "Source Code" shows a Maze game using DFS and BFS search (using "DFS" or "BFS" parameters). Use Notebook as the skeleton code, validate and compare following settings and results. a. Using Figure 7 as the game field, and use any two states as initial and goal states, report a screenshot of the program. Explaining the meaning of the output [0.25pt] b. Set initial state as [0,0] and goal state as [0,1]. Report number of nodes expanded by BFS and DFS, respectively. Report final path discovered by each algorithm, respectively [0.25pt]. Explain why or why not the method is optimal [0.25pt], and why one approach expands far more nodes than the other method [0.25pt] c. Set initial state as [0,0] and goal state as [0,1],[0,2],[0,3],[0,5],[0,6],[0,7],[0, 8],[0,9], respectively. Create one plot to show the number of maximum Fringe size of BFS ( x-axis denotes the goal state, and y-axis denotes the maximum Fringe size) [0.25 pt]. Create one plot to show the number of maximum Fringe size of DFS ( x axis denotes the goal state, and y-axis denotes the maximum Fringe size) [0.25 pt]. Explain how the Fringe size grows with respect to the search depth for DFS and BFS, respectively. [0.25 pt] d. For goal state [0,9], compare path returned by BFS and DFS, respectively. Which method is optimal, and which method is not optimal? Why? [0.25 pt] 7. [1 pt] Following Homework 1 ChatGPT assignment, this assignment is to implement a program (ie., using programming) to read questions from an input excel file (e.g., input.csf), and then save the ChatGPT generate answers as another excel file (e.g., output.csv). Each row of the input excel file includes questions to ask ChatGPT (each row corresponds to one question). Your answers should also be saved as a pure text (or excel file), with each row corresponding to one answer. Here are required implementation: a. The program should read text from a given excel file (e.g., a csv file), and print out content of the first five lines (using example.csv file posted on canvas as a template) [0.25pt] b. For text content in each row, please use the text as chatGPT input, and collect (and print out) ChatGPT answers [0.5pt] c. Save chatGPT answers as another output.csv file (without each answer being saved as one row). All answers from your input.csv file should be saved as one output.csv file. This allows fast batch processing later [0.25pt]