Ken's POTW


Non-Agressive Queens
  1. Can you place N queens on an NxN chessboard such that no queen is attacking any other? Can you find solutions for N <= 7? How many?
  2. Consider a hexagon with a side-length of 3. Each side is marked off at unit intervals, then lines are drawn parallel to the sides to connect these unit marks. This results in 6 rows of triangles in each of the three directions. Assuming now that queens can move in any of the three directions, how many queens can be placed, one per triangle, such that no queen attacks any other?
  3. Consider a triangle with a side-length of 9. Each side is marked off at unit intervals, then lines are drawn parallel to the sides to connect these unit marks. (This looks basically like the hexagon with its sides extended.) This results in 9 rows of triangles in each of the three directions. Now, how many of the 3-directional queens can be placed, one per triangle, such that no queen attacks any other?

Source: 1. Many sources. 2,3. Original.


Solutions were received from: Andy Barr, Leendert Biemans, Nick Baxter.
  1. Solutions do not exist for N=2 or 3, but exist for the other N. Two solutions exist for N=5, seven for N=7.
    N:      1       4       5       5       6
                    .x..    .x...   .x...   .x....
            x       ...x    ...x.   ....x   ...x..
                    x...    x....   ..x..   .....x
                    ..x.    ..x..   x....   x.....
                            ....x   ...x.   ..x...
                                            ....x.
    
    Nick Baxter sent his N=7 solutions when I requested them:
    ...X...
    .X.....
    ......X
    ....X..
    ..X....
    X......
    .....X.
    
    ...X...
    ......X
    ..X....
    .....X.
    .X.....
    ....X..
    X......
    
    ...X...
    ......X
    ....X..
    .X.....
    .....X.
    X......
    ..X....
    
    ..X....
    ......X
    .X.....
    ...X...
    .....X.
    X......
    ....X..
    
    ..X....
    ....X..
    ......X
    .X.....
    ...X...
    .....X.
    X......
    
    ....X..
    ......X
    .X.....
    ...X...
    .....X.
    X......
    ..X....
    
  2. The maximum of 6 is possible. Leendert Biemans found 62 possible configurations. Example:
              ...x...
             x........
            ..........x
            ......x....
             .x.......
              ....x..
    
  3. Again, only 6 are possible. Leendert Biemans and Nick Baxter sent lengthy analyses of this. Nick's approach follows:
    I believe the maximum is still 6.  Look at 4 regions: the hexagon
    from part (2), and the 3 3x3x3 triangles at the corners.  Let's
    assume that 7 queens will fit.  Then there are the following
    cases:
    i) 6 in hexagon, 1 in a 3-triangle
    ii) 5 in hexagon, 2 in a 3-triangle
    iii) 5 in hexagon, 1 in each of 2 3-triangles
    iv) 4 in hexagon, 3 in a 3-triangle
    v) 4 in hexagon, 2 in a 3-triangle, 1 in another
    vi) 4 in hexagon, 1 in each of the 3-triangles
    If one of the 3-triangles has 2 queens, then only one other
    3-triangle can have a queen (more just won't fit!); thus at 
    least 4 queens are in the hexagon.
    
    Since the number of queens in a single 3-triangle plus the hexagon
    cannot be greater than 6 (look at just the 6 rows containing
    the 3-triangle and the hexagon - there must be one with more
    than one queen), cases (i), (ii) and (iv) are eliminated.  Similarly,
    the number of queens in any 2 3-triangles plus the hexagon also
    cannot be greater than 6, eliminating cases (iii) and (v).
    
    This leaves case (vi).  Label all the 3-triangles 1-9:
        1
      4 5 6
    2 7 8 9 3
    
    Since T1 and T3 have 2 queens, (T5,T6,T9) has at most 1 queen,
    giving (T4,T7,T8) at least 3.  Since any tx has at most 2 queens,
    then either (T4,T7) or (T7,T8) has at least 2 queens.  Either way,
    combined with the queen in T1, there are 3 queens that conflict
    with either T1 or T3.
    

Mail to Ken