Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to kiloran,Anonymous,Howard,Gostevie,JuanDB, for Donating to support the site

Queens

cinelli
Lemon Slice
Posts: 383
Joined: November 9th, 2016, 11:33 am
Has thanked: 131 times
Been thanked: 77 times

Queens

#401034

Postby cinelli » April 2nd, 2021, 10:07 am

.--- --- --- --- --- --- --- ---
| 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
Lemon Slice
Posts: 383
Joined: November 9th, 2016, 11:33 am
Has thanked: 131 times
Been thanked: 77 times

Re: Queens

#402868

Postby cinelli » April 9th, 2021, 11:54 am

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
Lemon Quarter
Posts: 3922
Joined: November 4th, 2016, 1:17 am
Been thanked: 2269 times

Re: Queens

#403257

Postby Gengulphus » April 10th, 2021, 6:26 pm

cinelli wrote: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
2 Lemon pips
Posts: 122
Joined: January 28th, 2017, 11:58 am
Has thanked: 143 times
Been thanked: 44 times

Re: Queens

#403259

Postby mark88man » April 10th, 2021, 6:35 pm

excellent work, interesting puzzle and non-obvious solution

cinelli
Lemon Slice
Posts: 383
Joined: November 9th, 2016, 11:33 am
Has thanked: 131 times
Been thanked: 77 times

Re: Queens

#403550

Postby cinelli » April 12th, 2021, 10:20 am

Bravo, Gengulphus. The more I think about it, the more I realise what an achievement this is to find a solution to this problem. I had felt a little guilty, having set a problem which I couldn't myself solve. In fact I was starting to write a program when your solution popped up.

I no longer have access to the source material but the solution I noted is by Scott Kim and is as follows:

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

Scott Kim has his own website and has given a TED talk on puzzles. The above corresponds to Gengulphus's first solution.

Cinelli

Gengulphus
Lemon Quarter
Posts: 3922
Joined: November 4th, 2016, 1:17 am
Been thanked: 2269 times

Re: Queens

#405494

Postby Gengulphus » April 19th, 2021, 11:42 pm

cinelli wrote:Bravo, Gengulphus. The more I think about it, the more I realise what an achievement this is to find a solution to this problem. I had felt a little guilty, having set a problem which I couldn't myself solve. In fact I was starting to write a program when your solution popped up.

I no longer have access to the source material but the solution I noted is by Scott Kim and is as follows:

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

Scott Kim has his own website and has given a TED talk on puzzles. The above corresponds to Gengulphus's first solution.

I've recently realised that there is a reasonably feasible way for an unaided human to find that solution (though not the other one). It's not a deductive solution - it doesn't analyse the puzzle exhaustively (which is why it doesn't find the other solution) - but instead it requires a bit of inspiration...

The first part of that inspiration is to realise that the diagonal attacks of the queen constrain the available solutions quite a lot - there are quite a few times when playing around with the possibilities when I found that something that looked quite good at first sight had a diagonal attack I'd overlooked that spoiled it. And it's dead easy to find solutions with 16 rooks in the corresponding problem about rooks each attacking precisely two other rooks - as two examples of such solutions (there are many more):

+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | R | R | | R | | R | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | R | | R | | R | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

(A spin-off puzzle: do such solutions exist with more than 16 rooks?)

The second part of that inspiration is to realise that if one defines a diagonal through the board to be short if it has 4 or fewer squares on it and long if it has 5 or more squares on it, there are 14 long diagonals, 7 in each of the NE-SW and NW-SE directions:

+---+---+---+---+---+---+---+---+
| \ | \ | \ | \ | / | / | / | / |
+---+---+---+---+---+---+---+---+
| \ | \ | \ | X | X | / | / | / |
+---+---+---+---+---+---+---+---+
| \ | \ | X | X | X | X | / | / |
+---+---+---+---+---+---+---+---+
| \ | X | X | X | X | X | X | / |
+---+---+---+---+---+---+---+---+
| / | X | X | X | X | X | X | \ |
+---+---+---+---+---+---+---+---+
| / | / | X | X | X | X | \ | \ |
+---+---+---+---+---+---+---+---+
| / | / | / | X | X | \ | \ | \ |
+---+---+---+---+---+---+---+---+
| / | / | / | / | \ | \ | \ | \ |
+---+---+---+---+---+---+---+---+

That suggests that we could avoid a lot of unintended diagonal attacks if we look for solutions with one queen on each of the long diagonals. The central 'diamond' of squares marked with 'X's for being on two long diagonals are obviously forbidden territory in such solutions, which suggests a solution in which the queen-to-queen attacks loop around that central diamond (this is a third bit of inspiration, since it's not the only conceivable possibility). So basically, we'd be looking for each of the four corners of the board:

:   :   :   :   :   
+---+...:...:...:...
| | : : :
+---+---+...:...:...
| | | : :
+---+---+---+...:...
| | | | :
+---+---+---+---+...
| | | | |
+---+---+---+---+...

to have an entry queen and an exit queen which are each attacked just once from within the corner (or a single queen that serves both roles and is not attacked at all from within the corner), leaving their other attacks available to connect to the adjacent corners, and that are connected to each other by a chain of zero (if they're the same queen) or more attacks within the corner. Investigating the possibilities, using 'Q' to mark the entry and exit queens, 'q' to mark other queens in the chain and 'x' to mark squares that definitely do not contain queens, we can split into cases where the entry and exit queens are the same queen and where they are different queens.

If the entry and exit queens are the same queen, up to symmetry there is one possibility for that queen to be on a length-5 diagonal, one for it to be on a length-6 diagonal, and two each for it to be on a length-7 diagonal or a length-8 diagonal. Labelling those cases, and in each case, marking all other squares that are attacked by the entry/exit queen with 'x's because both of that queen's attacks go to other corners:

Case A                     Case B                     Case C
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | x | : : | Q | x | : : | x | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | | x | : | x | x | | : | Q | x | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | | | x | | x | | x | | | x | x | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case D Case E Case F
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | Q | : : | x | | : : | x | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | x | : | x | x | | : | x | Q | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | | x | | Q | x | x | x | | x | x | x | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

If the entry and exit queens are different queens, they might:

G: be on different length-5 diagonals
H, I: be on a length-5 diagonal and a length-6 diagonal
J, K, L, M: be on a length-5 diagonal and a length-7 diagonal
N, O: be on a length-5 diagonal and the length-8 diagonal
P: be on different length-6 diagonals
Q, R, S, T: be on a length-6 diagonal and a length-7 diagonal
U, V: be on a length-6 diagonal and the length-8 diagonal
W, X, Y: be on different length-7 diagonals
Z, AA, AB, AC: be on a length-7 diagonal and the length-8 diagonal

This classification produces the following configurations up to symmetry. In many cases, the entry and exit queens attack each other, in which case we've accounted for all of their attacks and so can mark all other squares that attack either one of them with 'x's, except those where a queen would interpose itself in the attack between them:

Case G                     Case H                     Case I
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | | : : | Q | x | : : | | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | | | : | x | x | x | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | Q | | x | | x | x | | | | Q | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case J Case K Case L
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | x | : : | x | Q | : : | | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| Q | x | x | : | x | x | x | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | | x | | x | x | | x | | | Q | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case M Case N Case O
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | | : : | | x | : : | | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | Q | : | | x | x | : | | Q | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | x | | Q | x | x | x | | | | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case P Case Q Case R
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | x | : : | Q | x | : : | Q | Q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | | x | : | Q | x | x | : | x | x | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | Q | x | | x | x | x | | | x | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case S Case T Case U
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| | : : : | | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | | : : | Q | | : : | Q | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | | | : | | | Q | : | | x | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | Q | | | | | | | | | Q | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case V Case W Case X
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | x | : : | x | x | : : | x | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | Q | x | : | Q | x | x | : | Q | | Q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | | | x | Q | x | x | | x | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case Y Case Z Case AA
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | Q | : : | x | x | : : | x | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | Q | : | Q | x | x | : | Q | Q | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | x | x | x | | Q | x | x | x | | x | x | x | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case AB Case AC
: : : : : : : : : :
+---+...:...:...:... +---+...:...:...:...
| | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:...
| | Q | : : | x | Q | : :
+---+---+---+...:... +---+---+---+...:...
| | | | : | x | Q | x | :
+---+---+---+---+... +---+---+---+---+...
| Q | | | | | x | x | x | x |
+---+---+---+---+... +---+---+---+---+...

In the cases where the entry and exit queens don't attack each other (cases I, L, O, S, T and AB), we need to add one or more further queens to connect them to each other. The possible configurations can easily be determined by trying each possibility in which a further queen attacks the entry queen (which I shall assume is the one of the entry and exit queens on the northwest-most long diagonal). If it also attacks the exit queen, we've completed the chain and can mark all remaining squares that attack any one of the chain of queens with 'x's (unless it interposes itself in the chain); otherwise we try to add a further queen and repeat as necessary. For case I, this produces the following configurations, marking the extra queens with lower-case 'q's to distinguish them from the entry and exit queens, and also marking squares that would be used by already-considered queens with '*'s to indicate they don't need to be considered again:

First queen considered completes the chain, but allows another to be interposed for a longer chain:

Case I1                    Case I2
: : : : : : : : : :
+---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:...
| q | x | : : | q | x | : :
+---+---+---+...:... +---+---+---+...:...
| x | | x | : | x | q | x | :
+---+---+---+---+... +---+---+---+---+...
| x | x | Q | x | | x | x | Q | x |
+---+---+---+---+... +---+---+---+---+...

Second queen considered completes the chain, but allows another to be interposed for a longer chain:

Case I3                    Case I4
: : : : : : : : : :
+---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:...
| * | | : : | * | q | : :
+---+---+---+...:... +---+---+---+...:...
| x | x | q | : | x | x | q | :
+---+---+---+---+... +---+---+---+---+...
| x | x | Q | x | | x | x | Q | x |
+---+---+---+---+... +---+---+---+---+...

Third queen considered completes the chain, but allows either (but not both) of two more to be interposed for a longer chain:

Case I5                    Case I6                    Case I7
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| * | x | : : | * | x | : : | * | x | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | x | * | : | q | x | * | : | x | x | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| q | | Q | x | | q | x | Q | x | | q | q | Q | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Fourth queen considered completes the chain, but allows another to be interposed for a longer chain:

Case I8                    Case I9
: : : : : : : : : :
+---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:...
| * | | : : | * | q | : :
+---+---+---+...:... +---+---+---+...:...
| x | x | * | : | x | x | * | :
+---+---+---+---+... +---+---+---+---+...
| * | x | Q | q | | * | x | Q | q |
+---+---+---+---+... +---+---+---+---+...

Fifth queen considered extends the chain from the entry queen, but then one of the remaining two squares (and not both of them) is needed to complete it:

(Incomplete case)          Case I10                   Case I11
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| * | q | : : | * | q | : : | * | q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | | * | : | x | q | * | : | x | * | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| * | | Q | * | | * | x | Q | * | | * | q | Q | * |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

There is only one remaining way to extend the chain from the entry square, and then one of the remaining two squares (and not both of them) is needed to complete it:

(Incomplete case)          Case I12                    Case I13
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| * | * | : : | * | * | : : | * | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| q | | * | : | q | q | * | : | q | * | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| * | | Q | * | | * | x | Q | * | | * | q | Q | * |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Dealing similarly (but with somewhat less detailed explanations) with the other cases where the chain from entry to exit queen needs to be completed, case L expands to the following cases, where one case is described as invalid because it has two queens on the same long diagonal:

Case L1                    Case L2                    (Invalid case)
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | q | : : | x | q | : : | x | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | | x | : | x | q | x | : | x | x | q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | Q | x | x | | x | Q | x | x | | x | Q | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
: : : : : : : : : : : : : : :

Case L3 Case L4 Case L5
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x| * | : : | x | * | : : | | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | * | : | x | x | * | : | q | x | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | Q | | q | | x | Q | q | q | | x | Q | x | * |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case L6 Case L7 Case L8
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| q | * | : : | | * | : : | q | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| q | x | * | : | * | x | * | : | * | x | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | Q | x | * | | q | Q | x | * | | q | Q | x | * |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

(Incomplete case) Case L9 Case L10
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| q | * | : : | q | * | : : | q | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| * | | * | : | * | q | * | : | * | * | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| * | Q | | * | | * | Q | x | * | | * | Q | q | * |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case O expands to the following cases:

Case O1                    Case O2                    Case O3
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| q | x | : : | * | q | : : | * | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | Q | x | : | x | Q | x | : | q | Q | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | x | | x | x | x | x | | x | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case O4 Case O5
+---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:...
| * | * | : : | * | * | : :
+---+---+---+...:... +---+---+---+...:...
| * | Q | q | : | * | Q | * | :
+---+---+---+---+... +---+---+---+---+...
| x | x | x | x | | q | x | x | x |
+---+---+---+---+... +---+---+---+---+...

(Incomplete case) Case O6 Case O7
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| * | * | : : | * | * | : : | * | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| * | Q | * | : | * | Q | * | : | * | Q | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| * | | | q | | * | x | q | q | | * | q | * | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case S expands to the following cases:

Case S1                    Case S2                    Case S3
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | x | : : | Q | x | : : | Q | q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| q | x | x | : | * | q | x | : | * | * | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | Q | x | x | | x | Q | x | x | | x | Q | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case S4 Case S5
+---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : :
+---+---+...:...:... +---+---+...:...:...
| Q | * | : : | Q | * | : :
+---+---+---+...:... +---+---+---+...:...
| * | * | x | : | * | * | x | :
+---+---+---+---+... +---+---+---+---+...
| q | Q | x | x | | * | Q | q | x |
+---+---+---+---+... +---+---+---+---+...

(Incomplete case) (Invalid case) Case S6
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| q | : : : | q | : : : | q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | * | : : | Q | * | : : | Q | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| * | * | | : | * | * | q | : | * | * | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| * | Q | * | | | * | Q | * | x | | * | Q | * | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case T expands to the following cases:

Case T1                    Case T2                    Case T3
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | q | : : | Q | * | : : | Q | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | Q | : | x | q | Q | : | x | * | Q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | x | | x | x | x | x | | x | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case T4 Case T5
+---+...:...:...:... +---+...:...:...:...
| * | : : : | * | : : :
+---+---+...:...:... +---+---+...:...:...
| Q | * | : : | Q | * | : :
+---+---+---+...:... +---+---+---+...:...
| q | * | Q | : | * | * | Q | :
+---+---+---+---+... +---+---+---+---+...
| x| x | x | x | | x | x | q | x |
+---+---+---+---+... +---+---+---+---+...

(Incomplete case) (Invalid case) Case T6
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| * | : : : | * | : : : | * | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | * | : : | Q | * | : : | Q | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| * | * | Q | : | * | * | Q | : | * | * | Q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| q | | * | | | q | q | * | | | q | * | * | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

And finally case AB expands to the following cases:

(Invalid case)             (Invalid case)             Case AB1
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| x | : : : | x | : : : | | x : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | Q | : : | x | Q | : : | q | Q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| q | x | x | : | * | q | x | : | * | * | x | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| Q | x | x | x | | Q | x | x | x | | Q | x | x | x |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case AB2 Case AB3
+---+...:...:...:... +---+...:...:...:...
| q | : : : | * | : : :
+---+---+...:...:... +---+---+...:...:...
| * | Q | : : | * | Q | : :
+---+---+---+...:... +---+---+---+...:...
| * | * | x | : | * | * | x | :
+---+---+---+---+... +---+---+---+---+...
| Q | x | x | x | | Q | q | x | x |
+---+---+---+---+... +---+---+---+---+...

(Incomplete case) Case AB4 Case AB5
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| * | : : : | * | : : : | * | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| * | Q | : : | * | Q | : : | * | Q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| * | * | q | : | * | * | q | : | * | * | q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| Q | * | | | | Q | * | q | x | | Q | * | * | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case AB6 Case AB7
+---+...:...:...:... +---+...:...:...:...
| * | : : : | * | : : :
+---+---+...:...:... +---+---+...:...:...
| * | Q | : : | * | Q | : :
+---+---+---+...:... +---+---+---+...:...
| * | * | * | : | * | * | * | :
+---+---+---+---+... +---+---+---+---+...
| Q | * | | q | | Q | * | q | q |
+---+---+---+---+... +---+---+---+---+...

So we've now deduced that in the class of solutions we're looking for, each corner must contain one of the configurations A-H, I1-I13, J-K, L1-L10, M-N, O1-O7, P-R, S1-S6, T1-T6, U-Z, AA, AB1-AB7 and AC. For the 'letters-and-numbers' configurations I1-I11, L1-L10, O1-O7, S1-S6, T1-T6 and AB1-AB7, the possibilities for blank squares to be filled with further queens have been fully investigated in the above analysis, so the numbers of queens in such configurations are the numbers of queens actually shown in the configuration diagrams: the highest such number is 4. For the 'letters-only' configurations A-H, J-K, M-N, P-R, U-Z, AA and AC, the possibilities for blank squares to be filled with further queens haven't been investigated, so as a first approximation, the numbers of queens in such configurations are at most the number of queens plus the number of blank squares shown in the configuration diagrams. This is 4 or less in every such configuration diagram except G, where it reaches 5. But further analysis of that diagram produces the following cases, bearing in mind that the two blank squares on the main diagonal are symmetrically equivalent to each other, so we only need to consider the possibilities that 0, 1 or 2 of them are occupied by queens:

Case G1                    Case G2                    Case G3
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| x | q | : : | x | q | : : | x | * | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| x | x | q | : | x | x | * | : | x | q | * | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| x | x | x | Q | | x | x | x | Q | | x | x | x | Q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case G4
: : : : :
+---+...:...:...:...
| Q | : : :
+---+---+...:...:...
| x | * | : :
+---+---+---+...:...
| x | * | * | :
+---+---+---+---+...
| x | x | x | Q |
+---+---+---+---+...

So in fact, in the class of solutions we're looking for, the number of queens in each corner is at most 4, and because every pair of opposite corners must contain a total of exactly 7 queens in order to occupy each of the 7 long diagonals that pass through those two corners exactly once, the division of queens into corners must be as follows (or a rotation of it):

+---+---+---+---+---+---+---+---+
| | |
+ 3 +---+---+ 3 +
| | X | X | |
+ +---+---+---+---+ +
| | X | X | X | X | |
+ +---+---+---+---+---+---+ +
| | X | X | X | X | X | X | |
+---+---+---+---+---+---+---+---+
| | X | X | X | X | X | X | |
+ +---+---+---+---+---+---+ +
| | X | X | X | X | |
+ +---+---+---+---+ +
| | X | X | |
+ 4 +---+---+ 4 +
| | |
+---+---+---+---+---+---+---+---+

The next stage is to look for pairs of 4-queen configurations that can make up the bottom half of that board. At this point, we need to check up on which configurations can contain 4 queens: it's easy to establish that they are the following:

Derived from case A: Case A1 below - which has the oddity that its three extra queens aren't on the path between its identical entry and exit squares, but form a separate loop.
Derived from case B: None - it can have 3 queens added, but the result is invalid due to having two queens on the same long diagonal.
Derived from cases C-F, H, J, K, P-R, V-Z, AA and Ac: None - not enough blank squares available.
Derived from case G: Case G1 above.
Derived from case I: Cases I2, I4, I6, I7, I9, I10, I11, I12 and I13 above.
Derived from case L: Cases L2, L4, L6, L8, L9 and L10 above.
Derived from case N: Case N1 below.
Derived from case O: Cases O6 and O7 above.
Derived from case S: Case S6 above.
Derived from case T: Case T6 above.
Derived from case U: None - two spaces exist where queens can be placed, but they cannot both be occupied by queens without one of them being attacked three times.
Derived from case AB: Cases AB4, AB5 and AB7 above.

In the following diagrams of all of those 4-queen configurations, I'm just showing squares as 'Q' for an entry/exit queen, 'q' for another queen, or blank for no queen - 'x's and '*'s have been made blank as the reasons why the squares don't contain queens are no longer relevant:

Case A1                    Case G1                     Case I2
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | | : : | | q | : : | q | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | q | | : | | | q | : | | q | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | q | q | | | | | | Q | | | | Q | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case I4 Case I6 Case I7
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | q | : : | | | : : | | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | | q | : | q | | | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | | Q | | | q | | Q | | | q | q | Q | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case I9 Case I10 Case I11
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | q | : : | | q | : : | | q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | | | : | | q | | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | | Q | q | | | | Q | | | | q | Q | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case I12 Case I13 Case L2
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | | : : | | | : : | | q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| q | q | | : | q | | | : | | q | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | | Q | | | | q | Q | | | | Q | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case L4 Case L6 Case L8
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | | : : | q | | : : | q | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | | | : | q | | | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | Q | q | q | | | Q | | | | q | Q | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case L9 Case L10 Case N1
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | Q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| q | | : : | q | | : : | q | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | q | | : | | | | : | q | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | Q | | | | | Q | q | | | Q | | | |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case O6 Case O7 Case S6
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| Q | : : : | Q | : : : | q | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| | | : : | | | : : | Q | | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | Q | | : | | Q | | : | | | | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| | | q | q | | | q | | q | | | Q | | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case T6 Case AB4 Case AB5
: : : : : : : : : : : : : : :
+---+...:...:...:... +---+...:...:...:... +---+...:...:...:...
| | : : : | | : : : | | : : :
+---+---+...:...:... +---+---+...:...:... +---+---+...:...:...
| Q | | : : | | Q | : : | | Q | : :
+---+---+---+...:... +---+---+---+...:... +---+---+---+...:...
| | | Q | : | | | q | : | | | q | :
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...
| q | | | q | | Q | | q | | | Q | | | q |
+---+---+---+---+... +---+---+---+---+... +---+---+---+---+...

Case AB7
: : : : :
+---+...:...:...:...
| | : : :
+---+---+...:...:...
| | Q | : :
+---+---+---+...:...
| | | | :
+---+---+---+---+...
| Q | | q | q |
+---+---+---+---+...

The solution continues in the next post, as this post is getting close to the size limit of 50,000 characters for posts...

Gengulphus

Gengulphus
Lemon Quarter
Posts: 3922
Joined: November 4th, 2016, 1:17 am
Been thanked: 2269 times

Re: Queens

#405495

Postby Gengulphus » April 19th, 2021, 11:43 pm

The solution for 'one queen per long diagonal' with the queen-to-queen path wrapping around the 'central diamond' of squares that are on two long diagonals - continued from previous post

Having listed those 25 possible 4-queen configurations for the bottom left and bottom right corners of the board, we can now classify them according to how those two corners are connected to each other. When doing this, I shall call the configuration in the diagram by its case name in the list of configuration diagrams at the end of the previous post if it appears as shown in the bottom left corner or reflected left-right in the bottom right corner. I will describe the results of diagonally reflecting those two by the case name primed. So for example, configuration N1 refers to a vertical row of four queens down the leftmost column of the bottom left corner or the rightmost column of the bottom right corner, while configuration N1' refers to a horizontal row of four queens along the bottom row of either corner.

Consider the horizontal attack between the bottom left and bottom right corners. Since we're looking for a "wraps round central diamond' queen-to-queen path, there's just one such attack, between an entry/exit queen of the bottom left corner and an entry/exit queen of the bottom right corner, with the other entry/exit queens of each of those corners attacks vertically into the top left or top right corners respectively.

We'll categorise how each of the bottom left and bottom right corners uses the 4-queen configuration it contains with a 4-character code, indicating what horizontal attacks there are between them. The first character indicates what horizontal attacks exist between them on the bottom row, the second what attacks exist between them on the next row up, the third character what attacks exist between them on the row above that, and the fourth character what attacks exist between them on their top row. The row on which the entry/exit queen of one attacks the exit/entry queen of the other (and vice versa) must clearly be the same row for both corners: we will use the letter 'e' for that row in both corners' categories. All the other rows (including if different the one containing the entry/exit queen that is not involved in that horizontal attack, which must attack vertically into the corner above it) are given the letter 'x' if they contain a queen or a hyphen '-' if they don't. If both the bottom left and bottom right corners have an 'x' on the same row, that indicates a pair of mutually-attacking queens that increase the number of attacks on each of them beyond two. So basically, we require the categories of the bottom left and bottom right corners to be compatible with each other, in the sense that their 'e's are in the same position and they don't both have an 'x' in the same position - which implies that they have at most three 'x's between them, and thus that at least one of them has no 'x's or one 'x'.

For each of the 25 configurations and their primed versions (which exist for all of them except G1, as that is the only one of them which is identical to its reflection in the diagonal), we can read off its possible categories from its diagram. It can have up to two such categories, which are determined by picking one of its entry/exit queens to be on the 'e' row and all its other queens to be on 'x' rows. This process might only produce one category (or even in principle no categories, though that doesn't in fact happen), for a number of reasons: the configuration might only have one entry/exit queen (applies to configuration A1 only); the chosen entry/exit queen might be 'shielded' by another queen to its right (applies to configurations I4', I9, L2', L4, L9, L10, N1', S6, S6', AB4, AB5, AB7); or the non-chosen entry/exit queen might be 'shielded' by another queen above it (applies to configurations I4, I9', L2, L4', L9', L10', N1, S6, S6', AB4', AB5', AB7'). Working out the possible categories for each of the 25 configurations and their 24 primed versions and adding them to lists of the configurations that can produce each conceivable category produces the following:

---e: none
--xe: none
-x-e: none
-xxe: none
x--e: I7, L4
x-xe: I9, I11, L8, L10
xx-e: A1, I6, I12, I13, O6, O7
xxxe: G1, I2, I10, L6

--e-: none
--ex: none
-xe-: none
-xex: none
x-e-: I6', AB7
x-ex: S6, T6'
xxe-: I2', I7', I10', I11', I12', I13', T6, AB4, AB5
xxex: I9'

-e--: none
-e-x: none
-ex-: none
-exx: none
xe--: L6', L8'
xe-x: O6, O7, O7', S6'
xex-: L10', T6
xexx: L4', O6'

e---: N1'
e--x: I7
e-x-: I6'
e-xx: I11, L8, T6'
ex--: L2', L6', L8', L9'
ex-x: I6, I12, I13, O7'
exx-: A1', I2', I4', I7', I10', I11', I12', I13', AB4'
exxx: G1, I2, I4, I10, L2, L6, L9, N1, O6', AB5', AB7'

We want to find the compatible combinations of the configurations in the bottom left and bottom right corners. Since a compatible combination must have the 'e's in the same position, every compatible combination must involve two configurations from the same group of eight lines in the above listing. Since compatible combinations must not have 'x's in the same position and every configuration in the first, second and third groups has an 'x' in the first position, compatible combinations must involve two configurations from the last group. As observed above, a compatible combination must involve a configuration in a category with no 'x's or one 'x', i.e. a configuration in one of the categories e---, e--x, e-x- or ex--. So every compatible combination must involve one of the configurations N1', I6', I7, L2', L6', L8' and L9'.

Cases where N1' are involved are have no limitations on the other configuration other than that it comes from one of the categories in the last group. That's 34 different possible other configurations accompanying the N1' configuration - a rather large number of cases to consider! So let's see where we can get simply from the assumption that at least one of the bottom corners contains the N1' configuration. By reflecting the board left-right if necessary, we can assume that it's the bottom left corner, which gives us the following diagram, in which 'q' denotes a queen with both of its attacks fully known, 'Q' a queen with one of its attacks fully known and the direction of the other known (from above for the left 'Q', the right for the right 'Q') and 'x' denotes squares that cannot contain a queen because we've already fully determined the corner's queens, because a queen on them would attack a known queen for the third time and/or because a queen on the would be a second queen on a long diagonal:

+---+---+---+---+---+---+---+---+
| | x | x | x | | | | x |
+---+---+---+---+---+---+---+---+
| | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| x | x | x | | * | * | |
+---+---+---+---+---+---+---+---+
| Q | q | q | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

Note that if two or more of the asterisked squares in the bottom right corner contain queens, then (bearing in mind the fact that no two of them will be on the same long diagonal) two or more of the still-open squares in the top left corner will be prohibited from containing a queen by the 'one queen per long diagonal' rule we've adopted. That would leave two or fewer squares available to contain queens in the top left corner, which would be inconsistent with our earlier deduction that the top left and top right corners must each contain three queens.

So, which of the possible configurations in the bottom right corner don't contain two or more queens in the asterisked squares? This is most quickly answered by scanning the 25 possible 4-queen configurations and their primed versions for ones that contain less than two queens in the asterisked squares. There are just three of them, namely L4', L6 and N1, and only L6 and N1 feature in the last group of configurations. So the bottom right corner's queens are as shown in the following diagram, with one of the 'q?' queens present and the other not (one choice produces the L6 configuration, the other the N1 configuration):

+---+---+---+---+---+---+---+---+
| | x | x | x | | | | x |
+---+---+---+---+---+---+---+---+
| | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | Q |
+---+---+ +---+---+
| x | x | | x | q |
+---+---+---+ +---+---+---+
| x | x | x | | x | x | q |
+---+---+---+---+---+---+---+---+
| Q | q | q | Q | x | x | q?| q?|
+---+---+---+---+---+---+---+---+

But it's impossible to place a second queen that attacks the 'Q' queen in the rightmost column from above, as would be required for a solution of the type we've looking for (indeed, it's impossible to place another queen anywhere in that diagram that attacks that 'Q' queen a second time, but that's more than we need for this search).

So there's no solution of the type we're looking for that has configuration N1' in either of the bottom corners.

Now suppose that bottom left or bottom right corner contains the L6' configuration (chosen because it only differs from N1' with regard to a single queen's position), and neither of those corners contains N1', since we've already disposed of that case. Again, we can use the left-right symmetry of the board to place it in the bottom left corner, resulting in the following board:

+---+---+---+---+---+---+---+---+
| | x | x | x | | | x | |
+---+---+---+---+---+---+---+---+
| | x | x | | x | | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| x | q | q | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

The three 'x's on the next-to-bottom row of the bottom right corner are because although we only fully know one of the attacks on the leftmost column's 'Q' queen, we do know that the other attack on it comes from above. So if one of the three bottom right corner 'x' squares held a queen, we would have three attacks on the leftmost column's 'Q' queen.

Again, if two or more of the asterisked squares contained a queen, our 'one queen per long diagonal' rule would rule out all but at most two squares in the top left corner. So we need to find 4-queen configurations with at most one queen in the bottom row and no queen in the row above it. But that forces the bottom right corner configuration to contain three queens in the three blank squares in that corner, which all attack each other, and one queen on an asterisked square, which necessarily attacks one of the three queens, raising the number of attacks on that queen to three. So neither of the bottom corners can contain L6'. Next consider L9' - a similar argument shows that after using the left-right symmetry of the board if needed, a board that uses L9' (and neither N1' nor L6') must match the following diagram:

+---+---+---+---+---+---+---+---+
| | x | x | x | | | x | x |
+---+---+---+---+---+---+---+---+
| | x | x | | x | x | |
+---+---+---+ +---+---+---+
| | x | | | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| Q | q | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| x | x | q | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

Exactly the same argument as for L6' establishes that we cannot fit a 4-queen configuration into the bottom right corner. and the same applies again if we have L2' (and none of N1', L6' or L9') in either bottom corner:

+---+---+---+---+---+---+---+---+
| | x | x | x | | | x | x |
+---+---+---+---+---+---+---+---+
| | x | x | | x | x | x |
+---+---+---+ +---+---+---+
| | x | | x | |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| Q | q | q | | x | x | x |
+---+---+---+---+---+---+---+---+
| x | x | x | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

That just leaves us with the possibilities that there is at least one L8', I6' or I7 in at least one of the bottom corners (and no N1', L2', L6' or L9' in either of them. Try L8' - the usual symmetry argument shows that up to left-right reflection, the board must be of the form:

+---+---+---+---+---+---+---+---+
| | ? | x | x | | | x | x |
+---+---+---+---+---+---+---+---+
| | | x | | x | x | |
+---+---+---+ +---+---+---+
| | | | | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| q | x | q | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

If the 'top-row square marked '?' does not contain a queen, two or more queens on the asterisked squares together with our 'one queen per long diagonal' rule will rule out two or more of the long diagonals that pass through the top left corner's blank squares, and so restrict that corner to containing two queens when it needs to contain three - but only one queen on the asterisked squares will force the 4-queen configuration in the bottom right corner to have queens on the three blank squares and one of the asterisked squares, which necessarily subjects one of those queens to three attacks.

The only way to avoid that is to put a queen on the square marked '?' - but then one of the three blank squares in the bottom right corner becomes ruled out by our 'one queen per long diagonal' rule:

+---+---+---+---+---+---+---+---+
| | Q | x | x | | | x | x |
+---+---+---+---+---+---+---+---+
| | | x | | x | x | |
+---+---+---+ +---+---+---+
| | | | | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| x | x | | | x |
+---+---+---+ +---+---+---+
| Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| q | x | q | Q | * | * | * | * |
+---+---+---+---+---+---+---+---+

But now the 4-queen configuration in the bottom right corner cannot contain 3 or more of the asterisked squares, since that would restrict the number of further queens in the top left corner to just one. So it must contain both of the blank squares and two asterisked squares. That means that it must be one of the e-xx configurations, which are I11, L8 and T6'. L8 isn't suitable, as the two queens it contains on the top two rows are orthogonally adjacent to each other, but each of I11 and T6' fits the space, resulting in the following two diagrams respectively:

+---+---+---+---+---+---+---+---+
| | Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| x| | x | | x | x | |
+---+---+---+ +---+---+---+
| x | x | | x | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | Q |
+---+---+ +---+---+
| x | x | | q | x |
+---+---+---+ +---+---+---+
| Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| q | x | q | q | x | q | q | x |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| x | Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| | x | x | | x | x | x |
+---+---+---+ +---+---+---+
| x| | | | x |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | q |
+---+---+ +---+---+
| x | x | | Q | x |
+---+---+---+ +---+---+---+
| Q | x | x | | x | x | x |
+---+---+---+---+---+---+---+---+
| q | x | q | q | x | q | x | q |
+---+---+---+---+---+---+---+---+

But neither of those boards permits us to place the required three queens in the top right square, so the L8' configuration also cannot be in either of the bottom corners, leaving us knowing that any solution of the type we're looking for must have at least one of I6' and I7 in at least one of the bottom corners.

Suppose it has I6' in one of the bottom corners. As usual, we can assume it's the bottom left corner after reflecting left-right if needed, getting the following board:

+---+---+---+---+---+---+---+---+
| | x | | x | | x | | x |
+---+---+---+---+---+---+---+---+
| | x | | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | |
+---+---+ +---+---+
| Q | x | | x | x |
+---+---+---+ +---+---+---+
| x | x | x | | | | |
+---+---+---+---+---+---+---+---+
| q | q | x | Q | | | | |
+---+---+---+---+---+---+---+---+

The category of the bottom left corner is e-x-, so the category of the bottom right corner must be e--- (configuration N1'), e--x (configuration I7), ex-- (configuration L2', L6', L8' or L9') or ex-x (configuration I6, I12, I13 or O7'). Of those ten configurations, we've already ruled out the possibilities that N1', L2', L6', L8' or L9' is in either bottom corner, so we only need to consider the possibilities that the bottom right corner contains I6, I7, I12, I13 or O7'. Furthermore, note that the top right corner contains just one empty square in each of the four rightmost columns, so if the configuration in the bottom right corner rules out further queens in two or more of those columns, we cannot put the required three queens into the top right corner. Bearing in mind the fact the 'q' queens in the bottom right corner configuration rule out further queens above them unless they're below the 'Q' queen that connects to the top right corner, and that the 'Q' queen which connects to the bottom left corner does the same, that's enough to rule out configurations I7, I12, I13 and O7' in the bottom right corner.

So the bottom right corner must contain configuration I6, which results in the following diagram:

+---+---+---+---+---+---+---+---+
| x | x | | x | | x | | x |
+---+---+---+---+---+---+---+---+
| | x | x | | x | x | x |
+---+---+---+ +---+---+---+
| x | x | | x | |
+---+---+ +---+---+
| | No queens | x |
+---+ in this +---+
| x | 'diamond' | Q |
+---+---+ +---+---+
| Q | x | | x | x |
+---+---+---+ +---+---+---+
| x | x | x | | x | x | q |
+---+---+---+---+---+---+---+---+
| q | q | x | q | x | q | x | q |
+---+---+---+---+---+---+---+---+

That contains three blank squares in each of the two top corners, which is precisely enough to house the three queens we need to add in each of those corners. But if we place queens in all of those squares, four of them will only be attacked once, so this doesn't lead to a solution of the problem.

So in any solution of the type we're looking for, at least one of the two bottom corners must contain the I7 configuration, and the usual argument about left-right reflectional symmetry allows us to assume that it's the bottom left corner:

+---+---+---+---+---+---+---+---+
| | x | x | | x | | | x |
+---+---+---+---+---+---+---+---+
| | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| | No queens | |
+---+ in this +---+
| Q | 'diamond' | x |
+---+---+ +---+---+
| x | x | | | |
+---+---+---+ +---+---+---+
| x | x | x | | | | |
+---+---+---+---+---+---+---+---+
| q | q | Q | x | | | | |
+---+---+---+---+---+---+---+---+

The category of the bottom left corner is e--x, so the category of the bottom right corner must be e--- (configuration N1'), e-x- (configuration I6'), ex-- (configuration L2', L6', L8' or L9') or exx- (configuration A1', I2', I4', I7', I10', I11', I12', I13' or AB4'). Of those fifteen configurations, we've already ruled out N1', L2', L6', L8', L9' and I6' appearing in either bottom corner. So we need to consider the nine configurations A1', I2', I4', I7', I10', I11', I12', I13' and AB4' for the bottom right corner.

We again have just four blank squares in the top right corner, so any bottom right corner configuration that eliminates two or more of them will prevent us putting the required three queens in the top right corner. That means any such configuration in which the columns of the 'Q' queen that connects to the bottom left corner and the two 'q' queens, excluding any column which is 'shielded' by the other 'Q' queen, include both of the two rightmost columns or include the third rightmost column. Inspection of the nine possible bottom right corner configurations shows that all of A1', I2', I4', I10', I11' and AB4' are eliminated by that check, so we only need to check out the I7', I12' and I13' configurations in the bottom right corner, which produce the following diagrams:

+---+---+---+---+---+---+---+---+
| x | x | x | | x | | | x |
+---+---+---+---+---+---+---+---+
| | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| x | No queens | |
+---+ in this +---+
| Q | 'diamond' | x |
+---+---+ +---+---+
| x | x | | x | Q |
+---+---+---+ +---+---+---+
| x | x | x | | x | x | q |
+---+---+---+---+---+---+---+---+
| q | q | q | x | q | x | x | q |
+---+---+---+---+---+---+---+---+

I7' in bottom right corner fails because there are just three blank squares in the top left corner of the board, so a solution must have queens on all of them. But the queen placed on the one of those squares which is on the top row can only be attacked from the right, and so cannot be attacked twice.

+---+---+---+---+---+---+---+---+
| x | x | x | | x | | x | x |
+---+---+---+---+---+---+---+---+
| x | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| x | No queens | |
+---+ in this +---+
| Q | 'diamond' | x |
+---+---+ +---+---+
| x | x | | | Q |
+---+---+---+ +---+---+---+
| x | x | x | | | q | |
+---+---+---+---+---+---+---+---+
| q | q | q | x | q | | q | |
+---+---+---+---+---+---+---+---+

I12' in bottom right corner fails because only two blank squares are left in the top left corner.

+---+---+---+---+---+---+---+---+
| | x | x | | x | | x | x |
+---+---+---+---+---+---+---+---+
| x | x | x | | | x | x |
+---+---+---+ +---+---+---+
| | x | | x | x |
+---+---+ +---+---+
| x | No queens | |
+---+ in this +---+
| Q | 'diamond' | x |
+---+---+ +---+---+
| x | x | | x | Q |
+---+---+---+ +---+---+---+
| x | x | x | | x | x | q |
+---+---+---+---+---+---+---+---+
| q | q | q | x | q | x | q | x |
+---+---+---+---+---+---+---+---+

I13' in bottom right corner succeeds because it leaves three blank squares in each of the top corners, and placing queens on each of those squares leads to a properly connected queen-to-queen path between the two 'Q' queens.

So at the end of all this, we've arrived at the single solution (up to symmetry) to the original problem augmented with our additional constraints that we have exactly one queen on each long diagonal, and that the queen-to-queen path loops around the outside of the central 'diamond' of squares that cannot hold queens because they're on two different long diagonals. It basically required some inspiration to realise that those additional constraints might be a productive area to look for a solution - and then quite a lot of deduction!

I'm pretty certain that a human solution to the problem without adding those extra constraints would require a great deal more deduction. I have investigated how I might get started on such a solution, and got far enough into it to find that without any extra constraints added, there are 180 possible symmetrically inequivalent configurations for each corner (errors and omissions excepted!) compared with the 25 such configurations I needed to deal with here. As there are four corners, the number of combinations one needs to deal can be expected to be about (180/25)^4 = over 2600 times greater than for the problem with the extra constraints...

So unless I see some ingenious simplification that reduces that number of combinations considerably, won't be trying to extend that start of a human solution to the unconstrained problem to a full solution!

Gengulphus

cinelli
Lemon Slice
Posts: 383
Joined: November 9th, 2016, 11:33 am
Has thanked: 131 times
Been thanked: 77 times

Re: Queens

#410524

Postby cinelli » May 9th, 2021, 12:28 pm

The Journal of Recreational Mathematics ran from 1968 to 2014 and it has been an occasional source for puzzles I have set here. If it was still active, Gengulphus's article would easily slot into this learned journal.

Cinelli

Gengulphus
Lemon Quarter
Posts: 3922
Joined: November 4th, 2016, 1:17 am
Been thanked: 2269 times

Re: Queens

#410581

Postby Gengulphus » May 9th, 2021, 5:04 pm

Thanks!

I will remind people that I set a spin-off puzzle in the course of writing the human solution for the "queens" puzzle above:

Gengulphus wrote:The first part of that inspiration is to realise that the diagonal attacks of the queen constrain the available solutions quite a lot - there are quite a few times when playing around with the possibilities when I found that something that looked quite good at first sight had a diagonal attack I'd overlooked that spoiled it. And it's dead easy to find solutions with 16 rooks in the corresponding problem about rooks each attacking precisely two other rooks - as two examples of such solutions (there are many more):

+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | R | R | | R | | R | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | R | | R | | R | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

(A spin-off puzzle: do such solutions exist with more than 16 rooks?)

It doesn't seem to have attracted any attention, but that may just be because it is totally dwarfed by the solution to the "queens" puzzle...

For what it's worth, assuming my solution to it is correct, it's much easier than the "queens" puzzle.

Gengulphus

cinelli
Lemon Slice
Posts: 383
Joined: November 9th, 2016, 11:33 am
Has thanked: 131 times
Been thanked: 77 times

Re: Queens

#412432

Postby cinelli » May 16th, 2021, 12:19 pm

+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | R | R | | R | | R | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| R | R | | | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | R | R | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | R | R | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | R | R | | R | | R | | R | | R | R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

I have been giving this problem some thought. I think that Gengulphus has been generous in providing two extreme solutions to his puzzle. I am borrowing ideas from graph theory for the following. If we put a vertex at the positions of all the rooks and join those vertices where one rook attacks another, the above solutions can be redrawn as follows:

+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
| R---R | | | | | | | | R---R-------R-------R-------R |
+-|-+-|-+---+---+---+---+---+---+ +-|-+---+---+---+---+---+---+-|-+
| R---R | | | | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +-|-+---+---+---+---+---+---+-|-+
| | | R---R | | | | | | R | | | | | | | | |
+---+---+-|-+-|-+---+---+---+---+ +-|-+---+---+---+---+---+---+-|-+
| | | R---R | | | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +-|-+---+---+---+---+---+---+-|-+
| | | | | R---R | | | | R | | | | | | | | |
+---+---+---+---+-|-+-|-+---+---+ +-|-+---+---+---+---+---+---+-|-+
| | | | | R---R | | | | | | | | | | | | R |
+---+---+---+---+---+---+---+---+ +-|-+---+---+---+---+---+---+-|-+
| | | | | | | R---R | | R | | | | | | | | |
+---+---+---+---+---+---+-|-+-|-+ +-|-+---+---+---+---+---+---+-|-+
| | | | | | | R---R | | R-------R-------R-------R---R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

We define the degree of a vertex as the number of edges which are incident to it. For a solution to the rooks problem the degree of all vertices must be precisely 2 and the rooks arrange themselves in closed loops. In case 1, the solution shows what we can describe as four 4-loops and in case 2, there is a single 16-loop. If we concentrate on 4-loops for the moment, they don't have to be two cells tall and wide and they don't need to be separate either. A solution with three 4x4 4-loops and one 2x2 4-loop looks like

+---+---+---+---+---+---+---+---+
| | | | | | | R---R |
+---+---+---+---+---+---+-|-+-|-+
| | | | | | | R---R |
+---+---+---+---+---+---+---+---+
| | | R-----------R | | |
+---+---+-|-+---+---+-|-+---+---+
| | R---|-------R | | | | |
+---+-|-+-|-+---+-|-+-|-+---+---+
| R---|---|---R | | | | | | |
+-|-+-|-+-|-+-|-+-|-+-|-+---+---+
| | | | | R---|---|---R | | |
+-|-+-|-+---+-|-+-|-+---+---+---+
| | | R-------|---R | | | |
+-|-+---+---+-|-+---+---+---+---+
| R-----------R | | | | |
+---+---+---+---+---+---+---+---+

This solution shows four 4-loops where the outer ones completely surround the inner ones. Neither do 4-loops need to be square. The next solution shows two 4x2 and two 2x2 4-loops.

+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
| R---------------------------R | | R-----------R | | | | |
+-|-+---+---+---+---+---+---+-|-+ +-|-+---+---+-|-+---+---+---+---+
| | | R-------------------R | | | | R-----------R | | | | |
+-|-+-|-+---+---+---+---+-|-+-|-+ +---+---+---+---+---+---+---+---+
| | | | | R-----------R | | | | | | | R---R | | | | | |
+-|-+-|-+-|-+---+---+-|-+-|-+-|-+ +---+-|-+-|-+---+---+---+---+---+
| | | | | | | R---R | | | | | | | | | R---R | | | | | |
+-|-+-|-+-|-+-|-+-|-+-|-+-|-+-|-+ +---+---+---+---+---+---+---+---+
| | | | | | | R---R | | | | | | | | | | | | R-----------R |
+-|-+-|-+-|-+---+---+-|-+-|-+-|-+ +---+---+---+---+-|-+---+---+-|-+
| | | | | R-----------R | | | | | | | | | | R-----------R |
+-|-+-|-+---+---+---+---+-|-+-|-+ +---+---+---+---+---+---+---+---+
| | | R-------------------R | | | | | | | | | R---R | |
+-|-+---+---+---+---+---+---+-|-+ +---+---+---+---+---+-|-+-|-+---+
| R---------------------------R | | | | | | | R---R | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

It is clear that solutions with just 4-loops have a maximum of 16 rooks. Since each 4-loop takes up two rows and two columns, there is no empty row or column for any more rooks.

What about n-loops for n greater than 4? I can find only one 5-loop:

+---+---+
| R---R |
+-|-+-|-+
| R | | |
+-|-+-|-+
| R---R |
+---+---+

And four 6-loops:

+---+---+---+   +---+---+---+   +---+---+   +---+---+
| R-------R | | R---R | | | R---R | | R---R |
+-|-+---+-|-+ +-|-+-|-+---+ +-|-+-|-+ +-|-+-|-+
| R | | | | | R-------R | | R | | | | R | | |
+-|-+---+-|-+ +---+-|-+-|-+ +-|-+-|-+ +-|-+-|-+
| R---R---R | | | R---R | | R | | | | | | R |
+---+---+---+ +---+---+---+ +-|-+-|-+ +-|-+-|-+
| R---R | | R---R |
+---+---+ +---+---+

Two 8-loops:

+---+---+---+---+   +---+---+---+---+
| R---R-------R | | R---R-------R |
+-|-+---+---+-|-+ +-|-+---+---+-|-+
| | | | | R | | R | | | | |
+-|-+---+---+-|-+ +-|-+---+---+-|-+
| R | | | | | | | | | | R |
+-|-+---+---+-|-+ +-|-+---+---+-|-+
| R-------R---R | | R-------R---R |
+---+---+---+---+ +---+---+---+---+

One 10-loop:

+---+---+---+---+---+
| R---R---R | | |
+-|-+---+-|-+---+---+
| R | | | | | |
+-|-+---+-|-+---+---+
| R---------------R |
+---+---+-|-+---+-|-+
| | | | | | R |
+---+---+-|-+---+-|-+
| | | R---R---R |
+---+---+---+---+---+

Two 12-loops:

+---+---+---+---+---+---+   +---+---+---+---+---+---+
| R---R-------R-------R | | R---R---R-----------R |
+-|-+---+---+---+---+-|-+ +-|-+---+---+---+---+-|-+
| | | | | | | R | | | | | | | | R |
+-|-+---+---+---+---+-|-+ +-|-+---+---+---+---+-|-+
| R | | | | | | | | | | | | | | R |
+-|-+---+---+---+---+-|-+ +-|-+---+---+---+---+-|-+
| | | | | | | R | | R | | | | | | |
+-|-+---+---+---+---+-|-+ +-|-+---+---+---+---+-|-+
| R | | | | | | | | R | | | | | | |
+-|-+---+---+---+---+-|-+ +-|-+---+---+---+---+-|-+
| R-------R-------R---R | | R-----------R---R---R |
+---+---+---+---+---+---+ +---+---+---+---+---+---+

I have found four 16-loops but feel there are many more. Very probably I have missed others too.

But where does this get us in solving Gengulphus's poser? Certainly if we wished to count solutions, classifying n-loops would be an aid because the various configurations can be combined. It is surely easier placing n-loops on the board than trying to arrange individual rooks. For example

+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
| R---R-------R---------------R | | R---R---R | | | | | |
+-|-+---+---+---+---+---+---+-|-+ +-|-+---+-|-+---+---+---+---+---+
| | | | | | | | | R | | R | | | | | | | | |
+-|-+---+---+---+---+---+---+-|-+ +-|-+---+-|-+---+---+---+---+---+
| | | | R-----------R | | | | | R-------R | | | | | |
+-|-+---+-|-+---+---+-|-+---+-|-+ +---+---+---+---+---+---+---+---+
| | | | | | | | | | | R | | | | | R---R | | | |
+-|-+---+-|-+---+---+-|-+---+-|-+ +---+---+---+-|-+-|-+---+---+---+
| R | | | | | | | | | | | | | | | R---R | | | |
+-|-+---+-|-+---+---+-|-+---+-|-+ +---+---+---+---+---+---+---+---+
| | | | R-----------R | | | | | | | | | | R-------R |
+-|-+---+---+---+---+---+---+-|-+ +---+---+---+---+---+-|-+---+-|-+
| R | | | | | | | | | | | | | | | | | | R |
+-|-+---+---+---+---+---+---+-|-+ +---+---+---+---+---+-|-+---+-|-+
| R---------------R-------R---R | | | | | | | R---R---R |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+

The first shows a 12-loop combined with a 4-loop while the second shows two 6-loops and a 4-loop.

So I haven't solved the poser but have had fun thinking about various configurations. I feel I have missed a really simple explanation.

Cinelli

9873210
2 Lemon pips
Posts: 221
Joined: December 9th, 2016, 6:44 am
Has thanked: 45 times
Been thanked: 56 times

Re: Queens

#412517

Postby 9873210 » May 16th, 2021, 6:07 pm

cinelli wrote:
What about n-loops for n greater than 4? I can find only ...
... four 6-loops:

+---+---+---+   +---+---+---+   +---+---+   +---+---+
| R-------R | | R---R | | | R---R | | R---R |
+-|-+---+-|-+ +-|-+-|-+---+ +-|-+-|-+ +-|-+-|-+
| R | | | | | R-------R | | R | | | | R | | |
+-|-+---+-|-+ +---+-|-+-|-+ +-|-+-|-+ +-|-+-|-+
| R---R---R | | | R---R | | R | | | | | | R |
+---+---+---+ +---+---+---+ +-|-+-|-+ +-|-+-|-+
| R---R | | R---R |
+---+---+ +---+---+

Two 8-loops:


+---+---+---+
| R---R | |
+-|-+-|-+---+
| | | R---R |
+-|-+---+-|-+
| R-------R |
+---+---+---+


+---+---+---+---+
| R---R | | |
+-|-+-|-+---+---+
| | | R---R | |
+-|-+---+-|-+---+
| | | | R---R |
+-|-+---+---+-|-+
| R-----------R |
+---+---+---+---+

And so on. Also for larger loops there are symmetries by swapping rows and columns and a few symmetries that are hard to describe that involve swapping rows or columns and doing some rearrangement.

9873210
2 Lemon pips
Posts: 221
Joined: December 9th, 2016, 6:44 am
Has thanked: 45 times
Been thanked: 56 times

Re: Rooks

#412520

Postby 9873210 » May 16th, 2021, 6:19 pm

I think we can prove that for any N-loop the sum of the rows + columns it occupies is N.
The rows and columns of separate loops must be distinct.
The sum of rows and columns for an 8x8 board is 16.
Therefore the maximum number of rooks is 16.
As has been demonstrated a solution with 16 rooks exists.
//

For any N-loop the sum of the rows + columns it occupies is N.

Place the rooks in order around the loop.
The first rook occupies one row and one column. SUM is 2.
Each additional rook that does not complete the loop must be in a new row or column (and an old column or row). increasing SUM by 1.'
The rook that completes the loop does not add a row or column. SUM is N.
//

9873210
2 Lemon pips
Posts: 221
Joined: December 9th, 2016, 6:44 am
Has thanked: 45 times
Been thanked: 56 times

Re: Rooks

#412529

Postby 9873210 » May 16th, 2021, 6:52 pm

9873210 wrote:I think we can prove that for any N-loop the sum of the rows + columns it occupies is N.
For any N-loop the sum of the rows + columns it occupies is N.

Place the rooks in order around the loop.
The first rook occupies one row and one column. SUM is 2.
Each additional rook that does not complete the loop must be in a new row or column (and an old column or row). increasing SUM by 1.'
The rook that completes the loop does not add a row or column. SUM is N.
//


On second thought this is not quite right. If we use the 5-Loop and go in the order below the 4th rook does not increase SUM but the 5th rook does,
Can probably fix this by making sure the last rook is a corner rook but that is going to require considering more cases than the simple induction.
+---+---+---+
| 1---5---4 |
+-|-+---+-|-+
| 2-------3 |
+---+---+---+

SteelCamel
Lemon Pip
Posts: 92
Joined: February 15th, 2017, 5:49 pm
Been thanked: 36 times

Re: Queens

#412553

Postby SteelCamel » May 16th, 2021, 9:51 pm

Inspired by Cinelli's comments about the 4-loops, I think I have a solution that doesn't require counting loops at all.

Each rook on the board always attacks in four directions. It may attack another rook, or “attack” a segment of the edge of the board – regardless of how many squares are crossed, all four attacks must terminate on another rook or on the board edge.
An edge segment (the piece of the edge adjacent to one square) can be "attacked" from one direction only – the row or column it terminates. It may be attacked by one rook (the nearest one in that row/column), or the row/column may be empty.

By the rules of the challenge, every rook must attack exactly two other rooks. Which means that every rook must also attack two edge segments of the board, since it must attack four things in total. There are eight edge segments along each side of the board, making 32 in total. Sixteen rooks will attack all 32 segments. A seventeenth rook would need to attack another two edge segments, in the two directions it’s not attacking rooks, but there are no segments left. So the seventeenth rook cannot be placed, and there are no solutions to the puzzle with more than sixteen rooks.


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 2 guests