QueenInterference

This problem contains images.

In chess the queen reigns supreme over all other pieces. She has mastered the techniques of the rook and the bishop, thus allowing her to move any number of steps diagonally, vertically, or horizontally. Since a single queen controls such a large area, it is hard to put multiple queens on the board without them getting in each others' way (two queens are "in each others' way" if one can reach the other in a single move). For this reason there is a famous challenge requiring n queens to be placed on an n-by-n chess board such that no two queens interfere with each other.

In this problem you will implement a particular randomized solution. The board is setup as follows starting with column 1 on the left, and ending with column n on the right:

• 1) Choose a random number R between 1 and n inclusive.
• 2) Place a queen in row R of the current column (row 1 is the top; row n is the bottom).

An alteration step works as follows:

• 1) Compute T, the number of columns containing reachable queens.
• 2) Choose a random number K between 1 and T inclusive. Let C denote the Kth column, counting from the left, that contains a reachable queen. In effect, we have randomly chosen one of the reachable queens.
• 3) For each of the n positions in column C, compute how many queens from other columns can currently reach that position.
• 4) Move the queen in column C to the position in column C reachable by the fewest number of queens. If multiple positions are tied, continue to step 5, otherwise the alteration step is complete.
• 5) Compute P, the number of positions that tied in step 4.
• 6) Choose a random number Q between 1 and P inclusive. Counting from the top down, move the queen to the Qth of the tied positions in 4.

Note that an alteration step may not cause any movement at all. You will return how many alteration steps are required before no two queens interfere with one another. The ith random value used in the algorithms above will be (a(i) % Up)+1 where Up is the inclusive upper bound on the random number required and a(i) is given by the following formula:

• a( 1 ) = 1 ,
• a( k+1 ) = ( 16807 * a( k ) ) % 2147483647 for k > 0.

Here % denotes modulus or remainder. Use a 64-bit integral type to correctly compute the a(j) values. Random values 1 through n will be used to setup the board, while the remaining values will be used to perform the alteration steps. Make sure to follow the algorithm carefully thus ensuring each random value is used at the correct time. Specifically, make sure you do not continue on to step 5 unless directed to do so. If no alteration steps are required, return 0.