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 postHaving 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