1. (40 pts) Regarding the 5-Queens problem (n-Queen problem with n = 5), answer following questions: a) (10 pts) Complet

[answerhappygod]

1 40 Pts Regarding The 5 Queens Problem N Queen Problem With N 5 Answer Following Questions A 10 Pts Complet 1 (233.91 KiB) Viewed 57 times

1. (40 pts) Regarding the 5-Queens problem (n-Queen problem with n = 5), answer following questions: a) (10 pts) Complete state space tree is a state space built by DFS without calling any nodes as non-promising so that no pruning of tree branches occurs. Suppose you solve a 5-Queens problem with DFS without pruning to construct the complete state space tree. How many nodes are there in this tree? b) (10 pts) How many potential solutions (including wrong ones) are there by using the strategy in (a) where DFS is used without pruning? c) (10 pts) Now let's attempt to solve the 5-Queens problem by using the backtracking algorithm with DFS and treating any nodes as non-promissing if it is along any column or diagnoal of previously placed queens. Suppose we visit children of a node in left-to-right order. Show a sketch of the portion of the pruned state space tree that would lead to the first solution. d) (10 pts) Display the first solution found by (b) and answer how many nodes you visited to reach this solution from the root node in the pruned state space tree.