Problem Statement
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).
- 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.
- a( 1 ) = 1 ,
- a( k+1 ) = ( 16807 * a( k ) ) % 2147483647 for k > 0.
Definition
- Class:
- QueenInterference
- Method:
- numSteps
- Parameters:
- int
- Returns:
- int
- Method signature:
- int numSteps(int n)
- (be sure your method is public)
Constraints
- n must be between 4 and 100 inclusive.
- n will not be 17.
Examples
4
Returns: 34
5
Returns: 4
The first 5 random numbers are 2,3,5,4,4 thus producing the following initial configuration. Alteration Step 1: All 5 queens are reachable, so we choose a random number between 1 and 5 inclusive. The number we get is 1, so we shall work on the leftmost column. Computing reachabilities we arrive at the following scores. Since there are 3 positions reachable by 1 queen, we retrieve another random number between 1 and 3 inclusive. The number turns out to be 3 so the queen is placed on the lowest of the 3 potential spots. Alteration Step 2: Since only 4 queens are still reachable we choose a random number between 1 and 4 inclusive. The next two random values are 1 and 3 so the previous steps are repeated and the board remains unchanged. Alteration Step 3: Again we choose a random number between 1 and 4 inclusive, but this time we get 4. Column 5 is the fourth column containing a reachable queen. We thus compute how many queens can reach each position in that column. Row 2 is the least reachable, so the queen is moved there. Alteration Step 4: Now there are 3 reachable queens so we choose a random number between 1 and 3 inclusive. We get the number 2 thus causing us to alter column 3 (the second column from the left containing a reachable queen). Now we compute how many queens can reach each position. Only the topmost position is reachable by 0 queens so we move the queen there. Now the board is complete, so we return 4.
6
Returns: 340
7
Returns: 6
66
Returns: 89
19
Returns: 475
The most possible steps.
20
Returns: 90
30
Returns: 53
40
Returns: 60
50
Returns: 79
15
Returns: 38
14
Returns: 32
55
Returns: 41
9
Returns: 8
10
Returns: 17
100
Returns: 148
6
Returns: 340
8
Returns: 101
11
Returns: 254
16
Returns: 146
19
Returns: 475
25
Returns: 101
27
Returns: 304
29
Returns: 120
31
Returns: 127
32
Returns: 108
33
Returns: 156
35
Returns: 105
45
Returns: 132
47
Returns: 122
49
Returns: 147
51
Returns: 136
53
Returns: 122
56
Returns: 121
62
Returns: 149
65
Returns: 177
69
Returns: 129
70
Returns: 163
72
Returns: 163
73
Returns: 106
74
Returns: 127
75
Returns: 161
76
Returns: 101
77
Returns: 112
79
Returns: 126
80
Returns: 155
81
Returns: 190
83
Returns: 123
84
Returns: 170
85
Returns: 137
86
Returns: 115
87
Returns: 138
88
Returns: 173
89
Returns: 127
90
Returns: 102
91
Returns: 103
92
Returns: 116
93
Returns: 152
94
Returns: 169
95
Returns: 146
96
Returns: 102
97
Returns: 150
98
Returns: 141
99
Returns: 136
100
Returns: 148
7
Returns: 6
19
Returns: 475
100
Returns: 148