The New Sudoku Players' Forum

[simon_blow_snow]

Excellent approach dyitto! I think I might have gone down that road manually before, but could not find anything with just my brain. Hopefully with a computer doing an exhaustive search something might come up. But from my experience it is NOT easy linking groups of different sizes.

Here is a quick 17 RSCs scenario using your approach:


Assign one RSC as the top level "root" (Z), which is linked to 4 other RSCs (A,B,C,D) - the middle level "moms". Each mom is linked to 3 other bottom level RSCs - "kids" (A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3):

Code: Select all

      _____________Z_____________
     /         /       \         \
    A         B         C         D
   /|\       /|\       /|\       /|\
  / | \     / | \     / | \     / | \
 /  |  \   /  |  \   /  |  \   /  |  \
A1 A2  A3 B1 B2  B3 C1  C2 C3 D1  D2 D3


As for additional links among "kids", each kid is linked to the same index kids of adjacent groups (A & D are considered adjacent) and different index kids of the groups 2 steps away. E.g. B2 is linked to A2,C2,D1,D3.


Verification:

Obviously the root Z is connected to all other RSCs.

Each mom is directly linked to Z and its own kids. Z bridges it to all other moms. Its own kids bridge it to all other kids.

Each kid is directly linked to its own mom and 1 kids each from the 2 neighbour groups, and 2 kids from the opposite group. Its mom bridges it to Z and other kids of the same group. The linked kids bridge it to other moms and all other kids (e.g. for B2, the linked kids A2,C2 bridge it to A,C,D2, while D1,D3 bridge it to D,A1,A3,C1,C3).


Here is the SCM:

Code: Select all

   Z  A  B  C  D A1 A2 A3 B1 B2 B3 C1 C2 C3 D1 D2 D3
Z  .  1  1  1  1  .  .  .  .  .  .  .  .  .  .  .  .
A  1  .  .  .  .  1  1  1  .  .  .  .  .  .  .  .  .
B  1  .  .  .  .  .  .  .  1  1  1  .  .  .  .  .  .
C  1  .  .  .  .  .  .  .  .  .  .  1  1  1  .  .  .
D  1  .  .  .  .  .  .  .  .  .  .  .  .  .  1  1  1
A1 .  1  .  .  .  .  .  .  1  .  .  .  1  1  1  .  .
A2 .  1  .  .  .  .  .  .  .  1  .  1  .  1  .  1  .
A3 .  1  .  .  .  .  .  .  .  .  1  1  1  .  .  .  1
B1 .  .  1  .  .  1  .  .  .  .  .  1  .  .  .  1  1
B2 .  .  1  .  .  .  1  .  .  .  .  .  1  .  1  .  1
B3 .  .  1  .  .  .  .  1  .  .  .  .  .  1  1  1  .
C1 .  .  .  1  .  .  1  1  1  .  .  .  .  .  1  .  .
C2 .  .  .  1  .  1  .  1  .  1  .  .  .  .  .  1  .
C3 .  .  .  1  .  1  1  .  .  .  1  .  .  .  .  .  1
D1 .  .  .  .  1  1  .  .  .  1  1  1  .  .  .  .  .
D2 .  .  .  .  1  .  1  .  1  .  1  .  1  .  .  .  .
D3 .  .  .  .  1  .  .  1  1  1  .  .  .  1  .  .  .

   Z  A  B  C  D A1 A2 A3 B1 B2 B3 C1 C2 C3 D1 D2 D3
Z  0  1  1  1  1  2  2  2  2  2  2  2  2  2  2  2  2
A  1  0  2  2  2  1  1  1  2  2  2  2  2  2  2  2  2
B  1  2  0  2  2  2  2  2  1  1  1  2  2  2  2  2  2
C  1  2  2  0  2  2  2  2  2  2  2  1  1  1  2  2  2
D  1  2  2  2  0  2  2  2  2  2  2  2  2  2  1  1  1
A1 2  1  2  2  2  0  2  2  1  2  2  2  1  1  1  2  2
A2 2  1  2  2  2  2  0  2  2  1  2  1  2  1  2  1  2
A3 2  1  2  2  2  2  2  0  2  2  1  1  1  2  2  2  1
B1 2  2  1  2  2  1  2  2  0  2  2  1  2  2  2  1  1
B2 2  2  1  2  2  2  1  2  2  0  2  2  1  2  1  2  1
B3 2  2  1  2  2  2  2  1  2  2  0  2  2  1  1  1  2
C1 2  2  2  1  2  2  1  1  1  2  2  0  2  2  1  2  2
C2 2  2  2  1  2  1  2  1  2  1  2  2  0  2  2  1  2
C3 2  2  2  1  2  1  1  2  2  2  1  2  2  0  2  2  1
D1 2  2  2  2  1  1  2  2  2  1  1  1  2  2  0  2  2
D2 2  2  2  2  1  2  1  2  1  2  1  2  1  2  2  0  2
D3 2  2  2  2  1  2  2  1  1  1  2  2  2  1  2  2  0


Note in this scenario 5 of the nodes (Z,A,B,C,D) have 4 direct links only, as we shown earlier, for (17,5) some nodes must use fewer than the maximum allowed 5 direct links because 17*5=85 is an odd number.

[dyitto]

My 19-5 search wasn't ready unfortunately - I had to terminate it.

For 17/5 I get 10 solutions starting from your intitial graph:

Code: Select all

SCProblem started : 20-2-2011 9:19:57

Initial graph
=====================================
0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


Permanent links
=====================================
0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;1;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;1;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;1;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;1;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;1;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;1;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;1;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;1;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;1;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;1;0;0;0;1;1;1;0;0;0;0;0;0
1;1;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;1;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;1;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;1;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;1;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;1;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;1;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;1;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;1;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0;0;1;1;1;0;0;0
1;0;1;0;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0


0;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;1;1;1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;0;0;0;0;0;0
1;0;0;0;1;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;1;0;0;0;0;0;0;0;0;0;0;1;1;1
0;1;0;0;0;0;0;0;1;0;0;0;1;1;1;0;0
0;1;0;0;0;0;0;0;0;1;0;1;0;1;0;1;0
0;1;0;0;0;0;0;0;0;0;1;1;1;0;0;0;1
0;0;1;0;0;1;0;0;0;0;0;1;0;0;0;1;1
0;0;1;0;0;0;1;0;0;0;0;0;1;0;1;0;1
0;0;1;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;0;0;1;0;0;1;1;1;0;0;0;0;0;1;0;0
0;0;0;1;0;1;0;1;0;1;0;0;0;0;0;1;0
0;0;0;1;0;1;1;0;0;0;1;0;0;0;0;0;1
0;0;0;0;1;1;0;0;0;1;1;1;0;0;0;0;0
0;0;0;0;1;0;1;0;1;0;1;0;1;0;0;0;0
0;0;0;0;1;0;0;1;1;1;0;0;0;1;0;0;0



SCProblem finished : 20-2-2011 9:19:57


[simon_blow_snow]

Thanks dyitto for the nice tool. But for (19,5) because 19 is such a tough prime, I find it hard to envision any particularly useful tree structure to try on so down the line I still think a thorough brute-force algorithm is the way to determine this scenario (possible or not).

While we are there I will throw in an alternative arrangement for 17 RSCs, using the same 3-level tree structure approach:


Assign TWO RSCs as the top level "roots" (X,Y) (or one can consider them as "grandpa & grandma" ), which are both linked to 5 other RSCs (A,B,C,D,E) - the middle level "moms". Each mom is linked to 2 other bottom level RSCs - "kids" (A1,A2,B1,B2,C1,C2,D1,D2,E1,E2).

Code: Select all

   _________X___Y_________
  //    //   \ /   \\    \\
  A     B     C     D     E
 / \   / \   / \   / \   / \
A1 A2 B1 B2 C1 C2 D1 D2 E1 E2


As for additional links among "kids", each kid is linked to the same index kids of adjacent groups (A & E are considered adjacent) and different index kids of the groups 2 steps away. E.g. B2 is linked to A2,C2,D1,E1.


Verification:

Obviously the roots X,Y are connected to all other RSCs.

Each mom is directly linked to X,Y and its own kids. X or Y bridges it to all other moms. Its own kids bridge it to all other kids.

Each kid is directly linked to its own mom and 1 kids each from the 2 neighbour groups, and 1 kids each from the 2 distant groups. Its mom bridges it to X,Y and the other kid of the same group. The linked kids bridge it to other moms and all other kids (e.g. for B2, the linked kids A2,C2 bridge it to A,C,D2,E2 while D1,E1 bridge it to D,E,A1,C1).


Here is the SCM:

Code: Select all

   X  Y  A  B  C  D  E A1 A2 B1 B2 C1 C2 D1 D2 E1 E2
X  .  .  1  1  1  1  1  .  .  .  .  .  .  .  .  .  .
Y  .  .  1  1  1  1  1  .  .  .  .  .  .  .  .  .  .
A  1  1  .  .  .  .  .  1  1  .  .  .  .  .  .  .  .
B  1  1  .  .  .  .  .  .  .  1  1  .  .  .  .  .  .
C  1  1  .  .  .  .  .  .  .  .  .  1  1  .  .  .  .
D  1  1  .  .  .  .  .  .  .  .  .  .  .  1  1  .  .
E  1  1  .  .  .  .  .  .  .  .  .  .  .  .  .  1  1
A1 .  .  1  .  .  .  .  .  .  1  .  .  1  .  1  1  .
A2 .  .  1  .  .  .  .  .  .  .  1  1  .  1  .  .  1
B1 .  .  .  1  .  .  .  1  .  .  .  1  .  .  1  .  1
B2 .  .  .  1  .  .  .  .  1  .  .  .  1  1  .  1  .
C1 .  .  .  .  1  .  .  .  1  1  .  .  .  1  .  .  1
C2 .  .  .  .  1  .  .  1  .  .  1  .  .  .  1  1  .
D1 .  .  .  .  .  1  .  .  1  .  1  1  .  .  .  1  .
D2 .  .  .  .  .  1  .  1  .  1  .  .  1  .  .  .  1
E1 .  .  .  .  .  .  1  1  .  .  1  .  1  1  .  .  .
E2 .  .  .  .  .  .  1  .  1  1  .  1  .  .  1  .  .

   X  Y  A  B  C  D  E A1 A2 B1 B2 C1 C2 D1 D2 E1 E2
X  0  2  1  1  1  1  1  2  2  2  2  2  2  2  2  2  2
Y  2  0  1  1  1  1  1  2  2  2  2  2  2  2  2  2  2
A  1  1  0  2  2  2  2  1  1  2  2  2  2  2  2  2  2
B  1  1  2  0  2  2  2  2  2  1  1  2  2  2  2  2  2
C  1  1  2  2  0  2  2  2  2  2  2  1  1  2  2  2  2
D  1  1  2  2  2  0  2  2  2  2  2  2  2  1  1  2  2
E  1  1  2  2  2  2  0  2  2  2  2  2  2  2  2  1  1
A1 2  2  1  2  2  2  2  0  2  1  2  2  1  2  1  1  2
A2 2  2  1  2  2  2  2  2  0  2  1  1  2  1  2  2  1
B1 2  2  2  1  2  2  2  1  2  0  2  1  2  2  1  2  1
B2 2  2  2  1  2  2  2  2  1  2  0  2  1  1  2  1  2
C1 2  2  2  2  1  2  2  2  1  1  2  0  2  1  2  2  1
C2 2  2  2  2  1  2  2  1  2  2  1  2  0  2  1  1  2
D1 2  2  2  2  2  1  2  2  1  2  1  1  2  0  2  1  2
D2 2  2  2  2  2  1  2  1  2  1  2  2  1  2  0  2  1
E1 2  2  2  2  2  2  1  1  2  2  1  2  1  1  2  0  2
E2 2  2  2  2  2  2  1  2  1  1  2  1  2  2  1  2  0


Note that once again 5 of the nodes (A,B,C,D,E) have 4 direct links only, giving it the same amount of "link efficiency" as the previous arrangement.

Of course, if we remove one of the roots (X or Y), this automatically reduces to an alternative arrangement for 16 RSCs, and is more "link efficient" than the previous one, which uses up all 5 RPDs on each RSC.

And needless to say, if we add one extra root (Z), this becomes a very straight forward arrangement for 18 RSCs, which uses up all 5 RPDs on each RSC. However, I will later provide 2 alternative 18 RSCs scenario, which demonstrate the number of possible arrangements in some scenarios (and they are all human understandable instead of some computer generated random arrangements).

And come to think of it, from the first 17 RSCs arrangement (the one with 1 root, 4 moms and 12 kids) can also become an arrangement 18 RSCs by adding an additional root, and is more link efficient as the 2 roots have 4 direct links only. So it seems the possibility is endless once a certain structure is established. Just not for the (19,5) case though.

[dyitto]

I've tried a calculation for run-times.

Checking all possibilities for 9/3 takes 154 seconds.

A 9/3 grid contains at most 13 edges - giving 2^13 graphs to investigate.
A 19/5 grid contains at most 47 edges.
In my initial tree 22 links have been pinned to one present/absent state, so there are 25 edges left to switch on/off - giving 2^25 graphs to investigate.

That means the 19/5 search will take 4.096 times as much as the 9/3 search.
Conclusion: the 19/5 search will take 7 - 8 days.

But: without limiting the search to an initial tree: a similar calculation will end up to 84.000 years.

That is, when using my current tool.
Shall we wait for the quantum computer?

[simon_blow_snow]

Shall we wait for the quantum computer?

LOL thanks for putting things back into perspective. I should not underestimate the exponentially growing complexity of this problem.

I suggest we wait a little bit for Bryan to come back and see if he can offer some extra after his break.


Meanwhile, I thought I had an arrangement for the 18 RSCs scenario with three circles of 6 (i.e. hexagons) but I've lost the plot. Therefore only 1 alternative arrangement for 18 RSCs which does not use the tree structure:


Divide them into two groups of 9 (A1-A9, B1-B9) and arrange each group into a circle. For group A, link all neighbours and all RSCs 4 steps apart (e.g. A1 is linked to A2,A5,A6,A9, A4 to A3,A5,A8,A9). For group B, link all RSCs 2 or 3 steps apart (e.g. B1 is linked to B3,B4,B7,B8, B5 to B2,B3,B7,B8). Finally, link RSCs with the same index across the two groups.


Verification:

It is obvious that each group is interconnected altogether. Also each RSC has bridged connection to 4 RSCs in the other group via its 4 PDs in the same group, while its lone PD in the other group bridges it to the remaining 4 RSCs in that group.


SCM:

Code: Select all

   A1 A2 A3 A4 A5 A6 A7 A8 A9 B1 B2 B3 B4 B5 B6 B7 B8 B9
A1  .  1  .  .  1  1  .  .  1  1  .  .  .  .  .  .  .  .
A2  1  .  1  .  .  1  1  .  .  .  1  .  .  .  .  .  .  .
A3  .  1  .  1  .  .  1  1  .  .  .  1  .  .  .  .  .  .
A4  .  .  1  .  1  .  .  1  1  .  .  .  1  .  .  .  .  .
A5  1  .  .  1  .  1  .  .  1  .  .  .  .  1  .  .  .  .
A6  1  1  .  .  1  .  1  .  .  .  .  .  .  .  1  .  .  .
A7  .  1  1  .  .  1  .  1  .  .  .  .  .  .  .  1  .  .
A8  .  .  1  1  .  .  1  .  1  .  .  .  .  .  .  .  1  .
A9  1  .  .  1  1  .  .  1  .  .  .  .  .  .  .  .  .  1
B1  1  .  .  .  .  .  .  .  .  .  .  1  1  .  .  1  1  .
B2  .  1  .  .  .  .  .  .  .  .  .  .  1  1  .  .  1  1
B3  .  .  1  .  .  .  .  .  .  1  .  .  .  1  1  .  .  1
B4  .  .  .  1  .  .  .  .  .  1  1  .  .  .  1  1  .  .
B5  .  .  .  .  1  .  .  .  .  .  1  1  .  .  .  1  1  .
B6  .  .  .  .  .  1  .  .  .  .  .  1  1  .  .  .  1  1
B7  .  .  .  .  .  .  1  .  .  1  .  .  1  1  .  .  .  1
B8  .  .  .  .  .  .  .  1  .  1  1  .  .  1  1  .  .  .
B9  .  .  .  .  .  .  .  .  1  .  1  1  .  .  1  1  .  .

   A1 A2 A3 A4 A5 A6 A7 A8 A9 B1 B2 B3 B4 B5 B6 B7 B8 B9
A1  0  1  2  2  1  1  2  2  1  1  2  2  2  2  2  2  2  2
A2  1  0  1  2  2  1  1  2  2  2  1  2  2  2  2  2  2  2
A3  2  1  0  1  2  2  1  1  2  2  2  1  2  2  2  2  2  2
A4  2  2  1  0  1  2  2  1  1  2  2  2  1  2  2  2  2  2
A5  1  2  2  1  0  1  2  2  1  2  2  2  2  1  2  2  2  2
A6  1  1  2  2  1  0  1  2  2  2  2  2  2  2  1  2  2  2
A7  2  1  1  2  2  1  0  1  2  2  2  2  2  2  2  1  2  2
A8  2  2  1  1  2  2  1  0  1  2  2  2  2  2  2  2  1  2
A9  1  2  2  1  1  2  2  1  0  2  2  2  2  2  2  2  2  1
B1  1  2  2  2  2  2  2  2  2  0  2  1  1  2  2  1  1  2
B2  2  1  2  2  2  2  2  2  2  2  0  2  1  1  2  2  1  1
B3  2  2  1  2  2  2  2  2  2  1  2  0  2  1  1  2  2  1
B4  2  2  2  1  2  2  2  2  2  1  1  2  0  2  1  1  2  2
B5  2  2  2  2  1  2  2  2  2  2  1  1  2  0  2  1  1  2
B6  2  2  2  2  2  1  2  2  2  2  2  1  1  2  0  2  1  1
B7  2  2  2  2  2  2  1  2  2  1  2  2  1  1  2  0  2  1
B8  2  2  2  2  2  2  2  1  2  1  1  2  2  1  1  2  0  2
B9  2  2  2  2  2  2  2  2  1  2  1  1  2  2  1  1  2  0


[BryanL]

Shall we wait for the quantum computer?

LOL thanks for putting things back into perspective. I should not underestimate the exponentially growing complexity of this problem.

I suggest we wait a little bit for Bryan to come back and see if he can offer some extra after his break.

Hi, i have a little time to follow the thread.

dyitto, i never looked closely at your code but looking at your timings suggests some serious slow points.

I know the combinations explodes with higher n, x but it seemed slow for even small n, x...

Maybe back onto this on Monday...

[dyitto]

Let's zoom into the part where we have a certain graph, and we want to check if each pair of nodes is linked or separated one more step.
What would be the fastest method? Perhaps in pseudocode?

[dyitto]

I've tried a different method:

Code: Select all

function TGraph.MaxDistanceLTEq2: boolean;
  var n1, n2, n3: integer;
begin
  //NOTE the assumption here is that the graph is (actually) undirected
  SCOK := InitOneWayConnected;

  for n1 := 1 to NodeCount - 2 do
    for n2 := n1 + 1 to NodeCount - 1 do
      for n3 := n2 + 1 to NodeCount do
        if (OneWayConnected[n1,n2] and OneWayConnected[n1,n3]) or
           (OneWayConnected[n1,n2] and OneWayConnected[n2,n3]) or
           (OneWayConnected[n1,n3] and OneWayConnected[n2,n3]) then
        begin
          SCOK[n1,n2] := true;
          SCOK[n1,n3] := true;
          SCOK[n2,n3] := true;
        end;

  result := true;
  for n1 := 1 to NodeCount - 1 do
    for n2 := n1 + 1 to NodeCount do
      if not (OneWayConnected[n1,n2] or SCOK[n1,n2]) then
      begin
        result := false;
        exit;
      end;
end;


But that's even slower than the current project.

Also I've tried to skip the distance computing in graphs that allow yet one more link.
(Why compute a distance when we're about to add yet another link and do it again?)
This may increase speed with about 40% - not spectacular anyway.

[RW]

[Disclaimer: I'm not a programmer so I have no clue if this is a good idea or not...]

Wouldn't it be possible to keep track of the validity of the solution just by counting closed triangles and squares? When adding links, whenever a triangle or square is formed (starting from one node you can get back to the same node by following 3 or 4 links, meaning two children of one link see each other or the same fouth node) add +1 to the "loop count" of each corner node of that triangle/square. In the 19/5 problem, if the "loop count" reaches 8 for any node, then you know that you cannot find a solution anymore.

There shouldn't be any need to do any other checks or distance counts than this. If you manage to place all links without getting a loop count of 8 or higher for any node, then the puzzle is solved.

RW

[dyitto]

Also I've tried to skip the distance computing in graphs that allow yet one more link.
(Why compute a distance when we're about to add yet another link and do it again?)
This may increase speed with about 40% - not spectacular anyway.

This improvement is now available here.

RW: I'll take a look at your suggestion.

[dyitto]

For example, 19 RSCs (5 PDs @) must be the single most difficult problem for me. I could not prove the impossibility, yet also could not find any working arrangement. I have found solutions up to 24 RSCs but with 5 fewer RSCs it seems so much more difficult!

Code: Select all

0;1;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;1;1;1;0;0;0;0;1;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;1;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;1;0;1;1;1;0;0;0;0;0
1;0;0;0;0;0;1;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;1;1;1
0;1;0;0;1;0;0;0;0;0;1;1;0;0;0;0;0;0;1
0;1;0;0;0;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;1;1;0;0;0;0;0;0;0;0;0;1;0;1;0;1;0;0
0;0;1;1;0;0;0;1;0;0;0;0;0;0;1;0;0;0;1
0;0;1;0;0;0;1;0;0;0;0;0;0;1;0;1;0;1;0
0;0;1;1;0;0;1;0;0;0;0;0;0;0;1;0;1;0;0
0;0;0;1;0;0;0;0;1;0;0;0;0;0;0;1;0;1;1
0;1;0;1;1;1;0;0;0;0;1;0;0;0;0;0;0;0;0
0;0;0;0;1;0;0;0;1;1;0;1;0;0;0;0;0;1;0
0;0;0;0;1;0;0;1;0;0;1;0;1;0;0;0;1;0;0
0;0;0;0;0;1;0;1;1;0;0;1;0;0;0;1;0;0;0
0;0;0;0;0;1;0;1;0;0;1;0;1;0;1;0;0;0;0
0;0;0;0;0;1;1;0;0;1;0;0;1;0;0;0;0;0;0


[simon_blow_snow]

Code: Select all

0;1;1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;1;1;1;0;0;0;0;1;0;0;0;0;0
1;0;0;0;0;0;0;0;1;1;1;1;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;1;0;1;1;1;0;0;0;0;0
1;0;0;0;0;0;1;0;0;0;0;0;0;1;1;1;0;0;0
1;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;1;1;1
0;1;0;0;1;0;0;0;0;0;1;1;0;0;0;0;0;0;1
0;1;0;0;0;0;0;0;0;1;0;0;0;0;0;1;1;1;0
0;1;1;0;0;0;0;0;0;0;0;0;1;0;1;0;1;0;0
0;0;1;1;0;0;0;1;0;0;0;0;0;0;1;0;0;0;1
0;0;1;0;0;0;1;0;0;0;0;0;0;1;0;1;0;1;0
0;0;1;1;0;0;1;0;0;0;0;0;0;0;1;0;1;0;0
0;0;0;1;0;0;0;0;1;0;0;0;0;0;0;1;0;1;1
0;1;0;1;1;1;0;0;0;0;1;0;0;0;0;0;0;0;0
0;0;0;0;1;0;0;0;1;1;0;1;0;0;0;0;0;1;0
0;0;0;0;1;0;0;1;0;0;1;0;1;0;0;0;1;0;0
0;0;0;0;0;1;0;1;1;0;0;1;0;0;0;1;0;0;0
0;0;0;0;0;1;0;1;0;0;1;0;1;0;1;0;0;0;0
0;0;0;0;0;1;1;0;0;1;0;0;1;0;0;0;0;0;0


Incredible! So it IS possible after all!

Thanks so much!

[dyitto]

I found it using a new trial & error random search routine.
With the possibility to limit the search to a user-defined scenario.

This was the actual scenario:

Code: Select all

                      A                                (grandmom)

     /       /        |         \      \

   B         C        D         E        F             (kids)

 / | \     /   \    / | \     /   \    / | \

B1 B2 B3   C1 C2   D1 D2 D3   E1 E2   F1 F2 F3         (grandchildren)


Further links only allowed between nieces / nephews, for example:
B & C1
B1 & C1

Actually the result was found within a second .

[dyitto]

I forgot to mention that the random search routine always prefers to link nodes that at that moment have the maximum mutual distance in the graph.
I've uploaded the latest version.