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.