3. State-Space Search (22 points) Consider the following puzzle: We say that a collection of queens on a chessboard covers the board if every square on the board is either a queen or is under attack by a queen. (A queer can move on rows, columns, or diagonals.) The problem is to find the minimum number of queens that can cover ak x k chessboard. For example, the diagram below shows that an 8 x 8 board can be covered with 5 queens. (Note: In parts c, d, and e below, a crude upper bound is sufficient. I am not looking for mathematically sophisticated solutions.) (a) (4 pts) Show how this problem can be solved using state-space search. ii. Actions ii. Goal Test IV b) (4 pts) Show how the state space can be structured to be tree-structured (systematic); that is, for any state S, there is a unique path of actions that generates S. (c) (5 pts) Let M be the minimum number of queens needed to cover a k x k board. Give a (d) (5 pts) Give a simple upper bound on the branching factor in the state space in terms of k (e.g. 2k, . (e) (4 pts) Using big O notation, give simple upper bounds on the time and space requirements for solving the problem in terms of k (keep in mind that Me is not known till after the search has been completed). You may estimate time and space in terms of the number of nodes that must be generated and the number of nodes that must be kept simultaneously in memory that is, you do not have to consider how much space is required to store a single node or how much time is required to generate and evaluate a single node. Express these bounds in terms of k. ty fo ii. Upper bound on space complexity for depth-first search in terms of k, e.g. O(k3) ii Upper bound on time complexity for breadth-first search in terms of k,e.g. O iv. Upper bound on space complexity for breadth-first search in terms of k.e.g Ok 3. State-Space Search (22 points) Consider the following puzzle: We say that a collection of queens on a chessboard covers the board if every square on the board is either a queen or is under attack by a queen. (A queer can move on rows, columns, or diagonals.) The problem is to find the minimum number of queens that can cover ak x k chessboard. For example, the diagram below shows that an 8 x 8 board can be covered with 5 queens. (Note: In parts c, d, and e below, a crude upper bound is sufficient. I am not looking for mathematically sophisticated solutions.) (a) (4 pts) Show how this problem can be solved using state-space search. ii. Actions ii. Goal Test IV b) (4 pts) Show how the state space can be structured to be tree-structured (systematic); that is, for any state S, there is a unique path of actions that generates S. (c) (5 pts) Let M be the minimum number of queens needed to cover a k x k board. Give a (d) (5 pts) Give a simple upper bound on the branching factor in the state space in terms of k (e.g. 2k, . (e) (4 pts) Using big O notation, give simple upper bounds on the time and space requirements for solving the problem in terms of k (keep in mind that Me is not known till after the search has been completed). You may estimate time and space in terms of the number of nodes that must be generated and the number of nodes that must be kept simultaneously in memory that is, you do not have to consider how much space is required to store a single node or how much time is required to generate and evaluate a single node. Express these bounds in terms of k. ty fo ii. Upper bound on space complexity for depth-first search in terms of k, e.g. O(k3) ii Upper bound on time complexity for breadth-first search in terms of k,e.g. O iv. Upper bound on space complexity for breadth-first search in terms of k.e.g Ok