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.