Euler's
36 officers problem has been in the news recently, following the passing of the last of 'Euler's Spoilers'.
It notoriously has no solution for the 6x6 square with 6 officers (colonel, lieutenant-colonel, major, captain, lieutenant, and sub-lieutenant) and 6 regiments.
One possible modification, while still keeping 6 regiments, would be to allow substitution of a junior officer (or officers) in one or more of the regiments by a new rank - say, Sensitivity Counsellor, or SC - more reflective of the needs and aspirations of a modern-day military.
What is the minimum number of SC's needed to make the problem solvable?
I used a tree search for the 2 SC solution, where I placed the 36 officers with 2 arbitrary substitutions into a matrix one at a time, going back up the tree when no placement could be found (to advance previous placements, last entered, first advanced) until a solution was found. But doing the 1 substitution search proved much longer computer time-wise to find a solution. (Still at it).
I note the following: If a solution is good, any two rows may be exchanged and likewise any two columns. Since all cell elements are 2-tuples, there is no problem with just leaving an arbitrary element in the top left corner and never advancing it. If no solution occurs, then there is none.
To solve the time problem for the 1 SC question, I am experimenting with a different algorithm. Here, the rows for the one SC case may be set up by drawing them unsubstituted (No SC) without repetition from a pool of 720 (= 6!) nominally legal rows, and then substituting in an SC at a cell which is involved in a single one pairwise conflict. A second conflict is fatal to the test case. (I have a feeling that conflicting pairs must come in even numbers;
2 pairs, 4 pairs, etc. One clue for this comes as my 2 GGs substitute
for an AA in one row and a BB in another in both cases. If true,
the 1 SC solution may not exist.)
But, recall that even Euler had wrong suspicions about his "even-odd" Latin Squares, opinions which were "spoiled" as truth prevailed.
Regarding the second algorithm, drawing these 6 rows from pools, in fact, requires only drawing each from a set of 120 (=5!), one set for each 1st column officer type. I will see if this "pool" method works faster than the tree search... but I worry 120*119...*115 > 10^12 matrices to test all cases may still be found prohibitive.
Edited on May 26, 2020, 2:25 am
solution methods
