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?

Thanks for the suggestion. Yes - I have been working on just that for a couple of days - exactly what you said. I got the code finished yesterday - it's a hybrid code - a fixed top row and a tree search through the rest. To test it I used the 2 SC case that I solved previously with the pure tree search. However, the hybrid code ran slower (i.e. did not finish in a reasonable time) than the pure tree. (I started guessing that maybe it mattered in what order I placed the SC substitutions initially, as to how soon it gets the first success. I moved their introduction to early and still it only manage to place 35 men in 4 hours.... While the pure tree solved same case in minutes.

Hoping that the code (code is here) was good, I tried placing the SC's in the middle, and not at the beginning nor the end of the tree search. That turned out to be the invaluable stomach digestif for the engine and allowed for a solution within a few minutes. Here is a second 2-SC (where SC is called GG here) solution. Note the "stiff" first row:

 success! board count=           36

1_AA  2_BB  3_CC  4_DD  5_EE  6_FF

6_EE  3_FF  2_AA  5_BB  4_GG  1_DD

4_FF  6_CC  1_BB  3_EE  2_DD  5_AA

2_CC  5_DD  4_EE  6_AA  1_FF  3_BB

3_DD  4_AA  5_FF  1_CC  6_BB  2_EE

5_GG  1_EE  6_DD  2_FF  3_AA  4_CC

Edited on May 26, 2020, 6:29 pm

Posted by Steven Lord on 2020-05-26 12:42:15