1. Consider the problem of placing eight queens on an (eight-by-eight) chess board. Two queens are said to attack each other if they are on the same row, column, or (not necessarily main) diagonal.

a. Give a randomized algorithm to place eight nonattacking queens on the board.

b. Give a backtracking algorithm to solve the same problem.

c. Implement both algorithms and compare the running time.

2. In the game of chess, a knight in row R and column C may move to row 1 ≤ Rt ≤ B and column 1 ≤ Ct ≤ B (where B is the size of the board) provided that either

|R - Rt|= 2 and  |C - Ct|= 1 or

|R - Rt|= 1   and   |C - Ct|= 2

A knight's tour is a sequence of moves that visits all squares exactly once before returning to the starting point.

a. If B is odd, show that a knight's tour cannot exist.

b. Give a backtracking algorithm to ?nd a knight's tour.