In class, we considered the N Queens problem, where we had to place N queens on an N-by-N chessboard such that no two queens were in the same row, column, or diagonal (i.e., no two queens are threatening each other). We designed a simple local search algorithm for this problem as follows: First, because we know that each column can contain only one queen, assign each queen to her own column. Place each queen at a random location within her column. Calculate the number of pairs of queens that are threatening each other (e.g., if Q1 is threatened by both Q2 and Q3, this counts as 2 threats). For each queen Qi, consider moving queen Qi to a different location in the same column, and calculate the new number of conflicts that would exist if you performed that move. Once you have performed these calculations, perform the move that results in the greatest reduction in the current number of conflicts (subject to the constraint that each queen must remain in her assigned column). If there is no move that reduces the current number of conflicts, then terminate. Repeat until termination. Give an example showing that this algorithm may fail to nd a correct solution. (Hint: try N = 4. Show that (a) there is a solution in which all queens are safe, and (b) there is some starting position and some sequence of moves following the above description that fails to find such a solution.)