Doubly Attacking Queens

Place the maximum number of chess queens on an NxN chessboard, such that each queen attacks exactly 2 other queens. Solve for N=2,3,4,5. (I'm interested in higher N, but I think computer searches may be needed to prove maximality.)

There are two different ways to analyze this:

  1. A queen can attack only as far as another queen. Thus, for three queens in a line, the center one would be attacked by two queens, but the end queens would only be attacked by one (the center one.) With this interpretation, you can easily place N+1 queens on the board by putting N along a side and 1 in a corner.
  2. A queen can attack through other queens. This simply means that any line which contains 2 queens can contain no more than 3 queens. (You could think of the problem then as placing the maximum number of checkers on the board such that each checker is in line with exactly two other checkers horizontally, vertically, or diagonally.)
It's my theory that the best solutions will work for both interpretations above (you won't need to find three queens in a line), but I don't mind being proven wrong. [2/26/01: I've been proven wrong.]

Source: Original.

Solutions were received from Al Zimmermann. His solutions are below. I don't have confirmation that his solutions are maximal or not. You might be interested in trying to find the only other solution for N=4.

Update 3/23/06 Richard Mathar pointed out there are some integer sequences associated with this problem: id:A051568, id:A051755.

Update 10/18/00 Richard Mathar provided a more thorough computer analysis of part 1 (below). His results do improve on Al's for part 1, but not for part 2.

Update 2/26/01 Claudio Baiocchi focused on trying to improve part 2 and his computer found that solutionsfor part 1 can be found with more queens than those which can be found for part 2. He found the same results as Richard Mathar, but added the conclusion (for up to 7x7) that Al's solutions are still maximal for part 2. (There's no additional supporting text below.)

From Al: Here are some results I came up with for N = 2 through 9. They all satisfy both interpretations. I have no idea how close these might come to being optimal. 
N  Queens
---------
2     3
3     4
4     6
5     7
6     9
7    11
8    13
9    14

Q Q
Q -

Q - -
Q - -
- Q Q

Q - - -
- - Q Q
Q Q - -
- - - Q

Q - - - Q
Q - Q - -
- - - Q -
- Q - - -
- Q - - -

Q - - - Q -      
Q - - - - -      
- Q - - - -      
- - - - Q Q      
- Q Q - - -      
- - - Q - -      

Q - - - - Q -    
Q - - Q - - -    
- - - - - Q Q    
- - - - - - -    
- - Q - - - -    
- Q - - - - Q
- - - Q Q - -    

Q - - - - Q - -  
- - - Q - Q - -  
Q Q - - - - - -  
- - - - Q - - -  
- - - - - - Q Q  
- - Q - - - - -  
- - - - - - - Q  
- Q Q - - - - -  

Q - - - Q - - - -
Q - - - - - - - -
- Q - - - - - - -
- - - - Q - - - Q
- Q - - - - - - -
- - - - - - - Q Q
- - Q Q - - - - -
- - - - - Q - - -
- - Q - - - Q - -

10/18/00 from Richard Mathar: 
Finally there are some results for the POTW on "Doubly Attacking Queens",
where a star in the table means that I've searched through the full configuration
space with a program, and where the number of solutions/setups indicates
the number of non-equivalent arrangements of queens, such that they cannot
be mapped onto each other by the four mirror operations or the three rotations
(symmetry operations of the square). The interpretation of "attacking" is
that (like in the chess rule) no attacks may pass through an intermediate
queen. For this interpretation, the cases N<=7 ought be settled now (supposed
my program is correct....)

Cheers.
Richard Mathar, mathar@mpia-hd.mpg.de

N      number of queens     number of configs
4      6*                   2
5      8*                   1
6      10*                  1
7      12*                  5
8      14                   >=2
9      16                   >=13
10     17                   >=44
11     19                   >=14
12     21                   >=1 

Some outputs follow.
==== N = 4
6 queens:
Q - Q -
- - Q -
- Q - -
- Q - Q

6 queens:
Q - Q -
- - - Q
- Q - Q
Q - - -

==== 4
==== N = 5
8 queens:
Q Q - - Q
- - - Q -
Q - - - -
Q - Q - -
- - - Q -

==== 5
==== N = 6
10 queens:
Q Q Q - Q -
- - - - - Q
- - - - - Q
Q - - - - -
- - - Q - -
Q - - Q - -

==== 6
==== N = 7
12 queens:
Q Q Q - - - Q
- - - - - Q -
- - - - - Q -
Q - - - - - -
Q - - - - - -
Q - - Q Q - -
- - - - - Q -

12 queens:
Q Q Q - - - Q
- - - - - Q -
- - - - - Q -
Q - - - - - -
Q - - - - - -
Q - - Q - - -
- - - - Q Q -

12 queens:
Q Q Q - - - Q
- - - - - - Q
- - - - - Q -
Q - - - - - -
Q - - - - - -
Q - - Q Q - -
- - - - - Q -

12 queens:
Q Q Q - - - Q
- - - - - - Q
- - - - - Q -
Q - - - - - -
Q - - - - - -
Q - - Q - - -
- - - - Q Q -

12 queens:
Q Q - Q - - Q
- - - - - Q -
Q - - - - - -
- - - - - Q -
Q - - - - - -
Q - Q - Q - -
- - - - - Q -

==== 7
==== N = 8
14 queens:
Q Q Q - Q - Q -
- - - - - - - Q
- - - - - - - Q
Q - - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - - - Q - -
Q - - Q - Q - -

14 queens:
Q Q - Q - - - -
- - - - Q - - Q
Q - - - - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - Q
Q - - - - Q - -
- - Q - - - Q -
==== 8
One example each for 9,10,11,12:
==== N = 9
16 queens:
Q Q Q Q - - - - Q
- - - - - - - Q -
- - - - - - - Q -
- - - - - - - Q -
Q - - - - - - - -
Q - - - - - - - -
Q - - - - - - - -
Q - - - Q Q Q - -
- - - - - - - Q -

==== N = 10
17 queens:
Q Q Q Q Q - Q - - Q
- - - - - - - - - Q
- - - - - - - - - Q
- - - - - - - - Q -
- - - - - - - - - -
Q - - - - - - - - -
- - - - - - - - - -
Q - - - - - - - - -
Q - - - - Q - - - -
- - - - - Q - Q Q -

==== N = 11
19 queens:
Q Q Q Q Q Q - - - Q Q
- - - - - - - Q - - -
- - - - - - - - - - Q
- - - - - - - - - - Q
- - - - - - - - - - Q
- - - - - - - - - - -
Q - - - - - - - - - -
Q - - - - - - - - - -
Q - - - - - - - - - -
- - - - - - Q - Q - -
- - - - - - Q - Q - -

==== N = 12
21 queens:
Q Q Q Q Q Q - Q - - - Q
- - - - - - - - - - - Q
- - - - - - - - - - - Q
- - - - - - - - - - - Q
- - - - - - - - - - Q -
- - - - - - - - - - - -
Q - - - - - - - - - - -
- - - - - - - - - - - -
Q - - - - - - - - - - -
Q - - - - - - - - - - -
Q - - - - - Q - - - - -
- - - - - - Q - Q Q Q -
Mail to Ken