Queens

[cinelli]

.--- --- --- --- --- --- --- ---
| Q |   |   |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   | Q |   | Q |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   |   | Q |   |
 --- --- --- --- --- --- --- ---
|   | Q |   |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   |   | Q |   |
 --- --- --- --- --- --- --- ---
|   | Q |   |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   | Q |   | Q |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   |   |   | Q |
 --- --- --- --- --- --- --- ---

The diagram above shows how ten queens can be placed on a chessboard so that each queen attacks precisely one other queen. Can you place 14 queens so that each queen attacks precisely two other queens?

Cinelli

[cinelli]

Since a week has gone by and there are no replies, I think I had better give a hint or two.

Hint 1 (hidden):

I have a solution, not my own, which is described as "horribly asymmetric".

Hint 2 (hidden):

Sometimes I have had a request for a really hard puzzle. I think this may be so described. Perhaps this is a puzzle which can be solved only by computer. But there are 64C14 = 4.7856E13 ways to place 14 queens on a chessboard (before allowing for rotations and reflections) so I suggest this can't be solved by brute force. But if there was ever a place for a genius programmer to step forward, surely that place is the Lemon Fool.

Cinelli

[Gengulphus]

Since a week has gone by and there are no replies, I think I had better give a hint or two.

Hint 1 (hidden):

I have a solution, not my own, which is described as "horribly asymmetric".

Hint 2 (hidden):

Sometimes I have had a request for a really hard puzzle. I think this may be so described. Perhaps this is a puzzle which can be solved only by computer. But there are 64C14 = 4.7856E13 ways to place 14 queens on a chessboard (before allowing for rotations and reflections) so I suggest this can't be solved by brute force. But if there was ever a place for a genius programmer to step forward, surely that place is the Lemon Fool.

Spoiler...

Results of a program I've thrown together follow this explanation - there are two basic solutions, each of which appears in eight reflected/rotated variants. The program takes just over 15 seconds to run, and I only applied standard techniques for such computer searches - i.e. no particular genius required!

The standard technique concerned is just to build up the solution in stages, rejecting candidate partial solutions as soon as one can. In particular, I numbered the squares of the chessboard 0-63 (better than 1-64 when using binary arithmetic) and built up the candidate solutions by adding the lowest-numbered queen at each stage. So the first stage produced 51 candidates, with the lowest-numbered queen in positions 0-50, both ends inclusive (it cannot be in positions 51-63, as those doesn't leave space for 13 higher-numbered queens. It's not possible to reject any of the candidates at that stage, as the single queen we've added cannot be under attack.

Then the second stage adds the second lowest-numbered queen which can be in any position from the position of the lowest-numbered queen plus 1 up to 51, both ends inclusive (it cannot be in positions 52-63, as those don't leave space for 12 higher-numbered queens). It's still not possible to reject any of the candidates, since each of the two queens we've added is under at most one attack. So the number of candidates left at this stage is the number of ways of placing 2 queens on 52 squares, i.e. 52C2 = 52*51/2 = 2613.

Then the third stage adds the third lowest-numbered queen which can be in any position from the position of the second lowest-numbered queen plus 1 up to 52, both ends inclusive (it cannot be in positions 53-63, as those don't leave space for 11 higher-numbered queens). It's still not possible to reject any of the candidates, since each of the two queens we've added is under at most two attacks. So the number of candidates left at this stage is the number of ways of placing 3 queens on 53 squares, i.e. 53C3 = 53*52*51/6 = 23426.

Then the fourth stage adds the fourth lowest-numbered queen which can be in any position from the position of the third lowest-numbered queen plus 1 up to 53, both ends inclusive (it cannot be in positions 54-63, as those don't leave space for 10 higher-numbered queens). That would increase the number of candidates to the number of ways of placing 4 queens on 54 squares, i.e. 54C4 = 54*53*52*51/24 = 316251, but we can now reject any candidate in which at least one of the queens is under attack from all three others, since adding further queens certainly won't reduce the number of attacks on that queen. I won't bother trying to count the number of 4-queen positions in which at least one queen is under attack from all three others myself, but the program results say that 278315 candidates got through the 4th stage test, so 316251-278315 = 37936 candidates must have been rejected for that reason. That basically means that the fourth stage test reduces the number of candidates by just under 12.0%.

And so it goes on, The combined result of the fourth and fifth stage tests is to reduce the number of candidates from 55C5 = 55*54*53*52*51/120 = 3478761 to 2134822, or by about 38.6%. That's the result of 'compounding' a 12.0% reduction with a 30.3% reduction, so in some sense the fifth stage test - reduces the number of candidates remaining by about 30.3%. That's larger than the reduction caused by the fourth stage test - which shouldn't be surprising, because it's reasonable to expect four existing queens on the board to be more likely than three existing queens to subject a newly added queen to at least 3 attacks, and also more likely for the newly-added queen to increase the number of attacks on at least one of them to three.

Anyway, the largest number of candidates remaining is 57428618 after the eight stage test, and from then on the number of candidates remaining drops until it reaches just 4970 after the 13th stage test. Then the program finishes the search with a 14th stage, which uses a more stringent test: rather than only rejecting candidates if they contain a queen that is subject to at least three attacks, it rejects them if they contain a queen that isn't subject to precisely two attacks. I.e. in the 1st to 13th stages, the acceptable numbers of attacks on each queen are 0, 1 and 2 (which is automatically the case in the 1st to 3rd stages), but in the 14th stage stage, the only acceptable number is 2. (I'll note that I could have made the acceptable numbers in the 13th stage be just 1 and 2, since adding the 14th queen can add at most one to the attacks on each of the 1st to 13th queens. That's a trick I missed when writing the program - but it would have had a negligible effect on the running time of the program, as it couldn't have rejected more than (or even as many as) the 4970 candidates that got through the actual program's 13th stage test, an absolutely tiny number compared with the tens of millions of candidates processed for several earlier stages.

One other thing to say is that it should be possible to cut the number of cases the computer would have to check by a factor of about 8 (i.e. to around 2 seconds on my desktop) by 'factoring out' the eight reflectional and rotational symmetries of the board. Not something I'm going to try, though - that sort of 'factoring out' tends to require a lot more work of designing, coding and debugging the program, and it's not worth it to reduce a search time of 15 second to 2 seconds! (On a more difficult search that required 15 months, reducing that to 2 months would of course be a rather different matter!)

As regards solving it without computer assistance, by the way, I had a good go at it, but every approach I tried basically ran into a 'combinatorial explosion'. Maybe there's a way to solve it by hand that doesn't require one to check hundreds or thousands of cases, subcases, subsubcases, etc, but if so, I haven't found it and I've run out of ideas about how to find it.

Finally, the program output:

Solution: QQQ.Q.Q.
          .......Q
          .......Q
          Q.......
          .......Q
          Q.......
          .....Q..
          Q..Q.Q..

Solution: QQ.Q....
          ....Q..Q
          Q.......
          .......Q
          Q.......
          ..Q....Q
          Q....Q..
          ..Q...Q.

Solution: Q.Q.Q.Q.
          Q.......
          .....Q.Q
          Q.......
          .Q......
          ......Q.
          .......Q
          .Q.Q.Q..

Solution: Q.Q.Q..Q
          .......Q
          .......Q
          Q.......
          .......Q
          QQ......
          .......Q
          ...Q.QQ.

Solution: Q..Q.Q.Q
          Q.......
          Q.......
          .......Q
          Q.......
          ......QQ
          Q.......
          .QQ.Q...

Solution: Q..Q.Q..
          .....Q..
          Q.......
          .......Q
          Q.......
          .......Q
          .......Q
          QQQ.Q.Q.

Solution: .QQ.Q...
          Q.......
          ......QQ
          Q.......
          .......Q
          Q.......
          Q.......
          Q..Q.Q.Q

Solution: .Q.Q.QQQ
          Q.......
          Q.......
          .......Q
          Q.......
          .......Q
          ..Q.....
          ..Q.Q..Q

Solution: .Q.Q.Q.Q
          .......Q
          Q.Q.....
          .......Q
          ......Q.
          .Q......
          Q.......
          ..Q.Q.Q.

Solution: .Q.Q.Q..
          .......Q
          ......Q.
          .Q......
          Q.......
          .....Q.Q
          Q.......
          Q.Q.Q.Q.

Solution: .Q...Q..
          ..Q....Q
          Q....Q..
          .......Q
          Q.......
          .......Q
          Q..Q....
          ....Q.QQ

Solution: ..Q.Q.Q.
          Q.......
          .Q......
          ......Q.
          .......Q
          Q.Q.....
          .......Q
          .Q.Q.Q.Q

Solution: ..Q.Q..Q
          ..Q.....
          .......Q
          Q.......
          .......Q
          Q.......
          Q.......
          .Q.Q.QQQ

Solution: ..Q...Q.
          Q....Q..
          ..Q....Q
          Q.......
          .......Q
          Q.......
          ....Q..Q
          QQ.Q....

Solution: ...Q.QQ.
          .......Q
          QQ......
          .......Q
          Q.......
          .......Q
          .......Q
          Q.Q.Q..Q

Solution: ....Q.QQ
          Q..Q....
          .......Q
          Q.......
          .......Q
          Q....Q..
          ..Q....Q
          .Q...Q..

51 positions passed loop 1 test
1326 positions passed loop 2 test
23426 positions passed loop 3 test
278315 positions passed loop 4 test
2134822 positions passed loop 5 test
10328130 positions passed loop 6 test
31715697 positions passed loop 7 test
57428618 positions passed loop 8 test
56712788 positions passed loop 9 test
27093783 positions passed loop 10 test
5155869 positions passed loop 11 test
306517 positions passed loop 12 test
4970 positions passed loop 13 test
16 positions passed loop 14 test
Search completed

Gengulphus

[mark88man]

excellent work, interesting puzzle and non-obvious solution