==> competition/games/chess/queen.most.s <== On an regular chess board, at most eight queens of one color can be placed so that there are no mutual attacks. Here is one configuration: ----------------- |Q| | | | | | | | ----------------- | | |Q| | | | | | ----------------- | | | | |Q| | | | ----------------- | | | | | | |Q| | ----------------- | |Q| | | | | | | ----------------- | | | | | | | |Q| ----------------- | | | | | |Q| | | ----------------- | | | |Q| | | | | ----------------- On an nxn board, if n is not divisible by 2 or 3, n^2 queens can be placed such that no two queens of the same color attack each other. The proof is via a straightforward construction. For n=1, the result is obviously true, so assume n>1 and n is not divisible by 2 or 3 (thus n>=5). Assume we are given n queens in each of these n "colors" (numbers): 0 1 2 ... n-1 The proof is by construction. The construction is easier to see then to describe, we do both. Here is what it looks like: 0 1 2 3 4 ... n-2 n-1 n-2 n-1 0 1 2 ... n-4 n-3 n-4 n-3 n-2 n-1 0 ... n-6 n-5 ...(move one row down => sub 2 (mod n); one col right => add 1 (mod n)) 2 3 4 5 6 ... 0 1 People who know how a knight moves in chess will note the repetitive knight move theme connecting queens of the same color (especially after joining opposite edges of the board). Now to describe this: place in each cell a queen whose "color" (number) is: j - 2*i + 1 (mod n), where i is the # of the row, and j is the # of the column. Then no 2 queens of the same color are in the same: row, column, or diagonal. Actually, we will prove something stronger, namely that no 2 queens of the same color are on the same row, column, or "hyperdiagonal". (The concept, if not the term, hyperdiagonal, goes back to 19th century.) There are n hyperdiagonals of negative slope (one of them being a main diagonal) and n hyperdiagonals of positive slope (one of them being the other main diagonal). Definition: for k in 0..n-1: the k-th negative hyperdiagonal consists of cells (i,j), where i-j=k (mod n) the k-th positive hyperdiagonal consists of cells (i,j), where i+j=k (mod n) Then 0-th negative hyperdiagonal is simply the NW-SE main diagonal. Then "1-th" positive hyperdiagonal is simply the SW-NE main diagonal. The other 2*(n-1) hyperdiagonals appear as 2 disconnected diagonal fragments of cells, but if you join opposite edges of an nxn board to each other, forming a sphere, these 2 fragments become linearly connected forming a great circle. Now to the proof: 1) First note that the above color assignment does indeed uniquely define the color of a queen in each of the n^2 cells. 2) no row contains 2 queens of the same color: cells (i, a) and (i, b) contain queens of the same color => a-2i-1 = b-2i-1 (mod n) => a = b (mod n) => a = b (since a,b are within 1..n) 3) no column contains 2 queens of the same color: cells (a, j) and (b, j) contain queens of the same color => j-2a-1 = j-2b-1 (mod n) => 2a = 2b (mod n) => a = b (mod n) (since n and 2 have no common factor) => a = b (since a,b are within 1..n) 4) no negative hyperdiagonal contains 2 queens of the same color: cells (a, j) and (b, k) on the same negative hyperdiagonal contain queens of the same color => a-j = b-k (mod n) AND j-2a-1 = k-2b-1 (mod n) => 2a-2j = 2b-2k (mod n) AND j-2a = k-2b (mod n) => (adding corresponding sides:) -j = -k (mod n) => j = k. And thus a = b, as well (see first equality, 5th line up) 5) no positive hyperdiagonal contains 2 queens of the same color: cells (a, j) and (b, k) on the same positive hyperdiagonal contain queens of the same color => a+j = b+k (mod n) AND j-2a-1 = k-2b-1 (mod n) => 2a+2j = 2b+2k (mod n) AND j-2a = k-2b (mod n) => (adding corresponding sides:) 3j = 3k (mod n) => j = k (mod n) (since n and 3 have no common factor) => j = k. Likewise a = b. As special cases with the 0th negative hyperdiagonal and 1st positive hyperdiagonal, no 2 queens on the same main diagonal are colored the same. Now is this condition, than n be not divisible by 2 and 3 also *necessary*? Mike Konrad mdk@sei.cmu.edu ****** . . . o . This is a solution for the 5-queen problem o . . . . at the torus. It has the 90 degree rotation symmetry. . . o . . . . . . o . o . . . According to T. Klove, The modular n-queen problem II, Discrete Math. 36 (1981) 33 it is unknown how to construct symmetric (90 rot) solutions for n = 1 or 5 (mod 12) and n has prime factors = 3 (mod 4). He solved the smallest cases 49 and 77. Try the next cases 121 and 133 or find a general solution. A further reference for modular or reflected queen problems is: Martin Gardner, Fractal Music, Hypercards and More ..., Freeman (1991) ******** For the 3-D N-queens problem the answer is four, at (1,1,2), (1,3,3), (2,3,1), and (3,2,3). You can't have more because with four, you must have at least two in at least one of the three horizontal slices of the cube. For the two-or-more-queen slice you must solve the n-queens problem for a 3x3 planar board, which allows you to place at most 2 queens, and one must be in a corner. The two queens cover all but one spot in the adjacent slice, so if the two-queen slice is the middle one we're already limited to no more than 4 queens. But if we put the 2-queen slice at the bottom or top, then the corner queen has line of sight to all corners of the opposite slice, so it can contain at most one queen, and so can the middle slice. If they sit in a 4x4x4 cube, the maximum is 7. Here is a sample. 1. 4 4 3 2. 2 3 4 3. 1 2 2 4. 2 4 2 5. 3 2 1 6. 1 1 4 7. 3 1 3 If they sit in a 5x5x5 cube, the maximum is 13. Here is a sample. 1. 4 5 4 2. 3 5 1 3. 5 4 2 4. 3 1 2 5. 2 1 4 6. 2 5 5 7. 4 1 5 8. 1 5 2 9. 5 2 1 10. 2 3 1 11. 1 3 5 12. 1 1 1 13. 5 1 3