The New Sudoku Players' Forum

[dyitto]

.Ah we speak the same language..

The complete project can be found here. If you might find it convenient to
pick up that one and add your DLX approach in there.

.Beauty for my eyes to see. .

Part of the credits are for a colleague of mine.

.have you started with the simplest cases and confirmed the numbers?.

Code: Select all

maxlink   nodes   solutions
1         2       1
1         3       0
2         3       4
1         4       0
2         4       3
3         4       26
1         5       0
2         5       12
3         5       112
4         5       368
1         6       0
2         6       0
3         6       790
4         6       5605
5         6       10924
1         7       0
2         7       0
3         7       2730
4         7       120620
5         7       466588
6         7       676456


For example the 12 solutions for 5/2:

Code: Select all

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


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


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


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


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


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


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


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


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


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


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


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


I wish I had an accomodation to run a program undisturbed for some substantial amount of time. But my almost-2yrs-old son likes to press buttons - especially the on-off-button of my computer.

[simon_blow_snow]

Are you saying there is no arrangement for 16, 17 agents with GSCs and 25, 26 agents with RSCs, or you just haven't found them yet?

Obviously RSCs cannot support 23 or 25 agents, if you follow the same reasoning of BSCs not supporting 9 agents.

Also I am quite certain that GSCs for 16/17 agents and RSCs for 26 agents are mathematically impossible, and it have been proven by graph theorists over the years.

However it would be much better if the programming experts can prove it via brute force!

I have never been interested in the actual number of possible solutions for each scenario. Once I found a working arrangement or proved the impossibility I felt satisfied. But fingers crossed your programs will return some fruitful results using this approach!

[simon_blow_snow]

On to GSCs (max 4 links):


To connect 9 GSCs altogether, just divide them into 3 groups: A1,A2,A3,B1,B2,B3,C1,C2,C3. All GSCs with same letter or same index are directly linked. Here is the SCM:

Code: Select all

   A1 A2 A3 B1 B2 B3 C1 C2 C3
A1  .  1  1  1  .  .  1  .  .
A2  1  .  1  .  1  .  .  1  .
A3  1  1  .  .  .  1  .  .  1
B1  1  .  .  .  1  1  1  .  .
B2  .  1  .  1  .  1  .  1  .
B3  .  .  1  1  1  .  .  .  1
C1  1  .  .  1  .  .  .  1  1
C2  .  1  .  .  1  .  1  .  1
C3  .  .  1  .  .  1  1  1  .

   A1 A2 A3 B1 B2 B3 C1 C2 C3
A1  0  1  1  1  2  2  1  2  2
A2  1  0  1  2  1  2  2  1  2
A3  1  1  0  2  2  1  2  2  1
B1  1  2  2  0  1  1  1  2  2
B2  2  1  2  1  0  1  2  1  2
B3  2  2  1  1  1  0  2  2  1
C1  1  2  2  1  2  2  0  1  1
C2  2  1  2  2  1  2  1  0  1
C3  2  2  1  2  2  1  1  1  0


To connect 11 GSCs altogether, arrange them in a circle. Then each GSC is directly linked to its immediate neighbour, plus the 4th & 7th away (from both directions). Here is the SCM:

Code: Select all

  A B C D E F G H I J K
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 . .
F . 1 . . 1 . 1 . . 1 .
G . . 1 . . 1 . 1 . . 1
H 1 . . 1 . . 1 . 1 . .
I . 1 . . 1 . . 1 . 1 .
J . . 1 . . 1 . . 1 . 1
K 1 . . 1 . . 1 . . 1 .

  A B C D E F G H I J K
A 0 1 2 2 1 2 2 1 2 2 1
B 1 0 1 2 2 1 2 2 1 2 2
C 2 1 0 1 2 2 1 2 2 1 2
D 2 2 1 0 1 2 2 1 2 2 1
E 1 2 2 1 0 1 2 2 1 2 2
F 2 1 2 2 1 0 1 2 2 1 2
G 2 2 1 2 2 1 0 1 2 2 1
H 1 2 2 1 2 2 1 0 1 2 2
I 2 1 2 2 1 2 2 1 0 1 2
J 2 2 1 2 2 1 2 2 1 0 1
K 1 2 2 1 2 2 1 2 2 1 0


To connect 12 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6. Each group is arranged in a circle, with links between neighbours. Then add links across the 2 groups between GSCs with the same index (mod 3). For example, A1 is linked to A2,A6,B1,B4. B5 is linked to B4,B6,A2,A5. Here is the SCM:

Code: Select all

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6
A1  .  1  .  .  .  1  1  .  .  1  .  .
A2  1  .  1  .  .  .  .  1  .  .  1  .
A3  .  1  .  1  .  .  .  .  1  .  .  1
A4  .  .  1  .  1  .  1  .  .  1  .  .
A5  .  .  .  1  .  1  .  1  .  .  1  .
A6  1  .  .  .  1  .  .  .  1  .  .  1
B1  1  .  .  1  .  .  .  1  .  .  .  1
B2  .  1  .  .  1  .  1  .  1  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .
B4  1  .  .  1  .  .  .  .  1  .  1  .
B5  .  1  .  .  1  .  .  .  .  1  .  1
B6  .  .  1  .  .  1  1  .  .  .  1  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6
A1  0  1  2  2  2  1  1  2  2  1  2  2
A2  1  0  1  2  2  2  2  1  2  2  1  2
A3  2  1  0  1  2  2  2  2  1  2  2  1
A4  2  2  1  0  1  2  1  2  2  1  2  2
A5  2  2  2  1  0  1  2  1  2  2  1  2
A6  1  2  2  2  1  0  2  2  1  2  2  1
B1  1  2  2  1  2  2  0  1  2  2  2  1
B2  2  1  2  2  1  2  1  0  1  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2
B4  1  2  2  1  2  2  2  2  1  0  1  2
B5  2  1  2  2  1  2  2  2  2  1  0  1
B6  2  2  1  2  2  1  1  2  2  2  1  0


Next time I will show how GSCs can support 13,14,15 agents.

Or if you guys want, try to work them out yourself. They are nice mental exercises (for human brains or computers)!

[dyitto]

1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?

The answer is impossible, and it can be proved quite easily.

Firstly we have to consider the total number of "registered PDs" (RPDs) on all 9 BSCs. Note that each direct link would account for 2 RPDs (one on each end). Say there are L direct links, then the total number of RPDs would be 2L, which must be an even number.

Now recall that each BSC can hold a maximum of 3 RPDs. If all 9 BSCs were to use the maximum, then the total number of RPDs would be 9*3=27, which would be an odd number, impossible. Therefore at least one BSC (say X) must hold fewer than 3 RPDs, i.e. have a maximum of 2 PDs. In turn these 2 PDs would allow a further 2*2=4 BSCs to have "bridged communication" with X. In total, X can only establish communication with a maximum of 2+4=6 other BSCs, making the remaining two "out of reach" from X's standpoint.

Hence, 9 BSCs cannot be connected altogether.

Do you agree that his generalizes to:
- If a graph has N nodes, and each of the nodes has exactly M links, then the total number of edges equals (N * M) / 2.
- As a consequence, if both N and M are odd, at least one of the nodes has less then M links.
- As a consequence: if both N and M are odd, then it's impossible to connect more then 1 + M^2 - M nodes.

[simon_blow_snow]

Do you agree that his generalizes to:
- If a graph has N nodes, and each of the nodes has exactly M links, then the total number of edges equals (N * M) / 2.
- As a consequence, if both N and M are odd, at least one of the nodes has less then M links.
- As a consequence: if both N and M are odd, then it's impossible to connect more then 1 + M^2 - M nodes.

Yes more or less. It is a very neat way to present this logic. I would have specified M as the maximum number of links for each node.


Continuing the GSC scenarios:



To connect 13 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6, and label the remaining one C. Each group is arranged in a circle, with links between neighbours. The 1,4 of each group links to C directly while the 2,3,5,6 links to the GSCs in the other group with the same index (mod 3).

For example, A1 links to A2,A6,C. B5 links to B4,B6,A2,A5.

Here is the SCM:

Code: Select all

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C
A1  .  1  .  .  .  1  .  .  .  .  .  .  1
A2  1  .  1  .  .  .  .  1  .  .  1  .  .
A3  .  1  .  1  .  .  .  .  1  .  .  1  .
A4  .  .  1  .  1  .  .  .  .  .  .  .  1
A5  .  .  .  1  .  1  .  1  .  .  1  .  .
A6  1  .  .  .  1  .  .  .  1  .  .  1  .
B1  .  .  .  .  .  .  .  1  .  .  .  1  1
B2  .  1  .  .  1  .  1  .  1  .  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .  .
B4  .  .  .  .  .  .  .  .  1  .  1  .  1
B5  .  1  .  .  1  .  .  .  .  1  .  1  .
B6  .  .  1  .  .  1  1  .  .  .  1  .  .
C   1  .  .  1  .  .  1  .  .  1  .  .  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C
A1  0  1  2  2  2  1  2  2  2  2  2  2  1
A2  1  0  1  2  2  2  2  1  2  2  1  2  2
A3  2  1  0  1  2  2  2  2  1  2  2  1  2
A4  2  2  1  0  1  2  2  2  2  2  2  2  1
A5  2  2  2  1  0  1  2  1  2  2  1  2  2
A6  1  2  2  2  1  0  2  2  1  2  2  1  2
B1  2  2  2  2  2  2  0  1  2  2  2  1  1
B2  2  1  2  2  1  2  1  0  1  2  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2  2
B4  2  2  2  2  2  2  2  2  1  0  1  2  1
B5  2  1  2  2  1  2  2  2  2  1  0  1  2
B6  2  2  1  2  2  1  1  2  2  2  1  0  2
C   1  2  2  1  2  2  1  2  2  1  2  2  0


Note there is not as much redundancy as in the scenario for 12 GSCs - which leads to a simple accomodation for the 14 GSCs scenario:



To connect 14 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6, and label the remaining two C,D. Each group is arranged in a circle, with links between neighbours. The 1,4 of each group links to C,D directly while the 2,3,5,6 links to the GSCs in the other group with the same index (mod 3).

For example, A1 links to A2,A6,C,D. B5 links to B4,B6,A2,A5.

Here is the SCM:

Code: Select all

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C  D
A1  .  1  .  .  .  1  .  .  .  .  .  .  1  1
A2  1  .  1  .  .  .  .  1  .  .  1  .  .  .
A3  .  1  .  1  .  .  .  .  1  .  .  1  .  .
A4  .  .  1  .  1  .  .  .  .  .  .  .  1  1
A5  .  .  .  1  .  1  .  1  .  .  1  .  .  .
A6  1  .  .  .  1  .  .  .  1  .  .  1  .  .
B1  .  .  .  .  .  .  .  1  .  .  .  1  1  1
B2  .  1  .  .  1  .  1  .  1  .  .  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .  .  .
B4  .  .  .  .  .  .  .  .  1  .  1  .  1  1
B5  .  1  .  .  1  .  .  .  .  1  .  1  .  .
B6  .  .  1  .  .  1  1  .  .  .  1  .  .  .
C   1  .  .  1  .  .  1  .  .  1  .  .  .  .
D   1  .  .  1  .  .  1  .  .  1  .  .  .  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C  D
A1  0  1  2  2  2  1  2  2  2  2  2  2  1  1
A2  1  0  1  2  2  2  2  1  2  2  1  2  2  2
A3  2  1  0  1  2  2  2  2  1  2  2  1  2  2
A4  2  2  1  0  1  2  2  2  2  2  2  2  1  1
A5  2  2  2  1  0  1  2  1  2  2  1  2  2  2
A6  1  2  2  2  1  0  2  2  1  2  2  1  2  2
B1  2  2  2  2  2  2  0  1  2  2  2  1  1  1
B2  2  1  2  2  1  2  1  0  1  2  2  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2  2  2
B4  2  2  2  2  2  2  2  2  1  0  1  2  1  1
B5  2  1  2  2  1  2  2  2  2  1  0  1  2  2
B6  2  2  1  2  2  1  1  2  2  2  1  0  2  2
C   1  2  2  1  2  2  1  2  2  1  2  2  0  2
D   1  2  2  1  2  2  1  2  2  1  2  2  2  0


The scenario for 15 GSCs is much more complicated, I will show it next time.

[dyitto]

I've speeded up the program with factor 5.

Now it finds the first solution for 10 nodes/3 links in about 20 seconds.
In 5 - 6 minutes it confirms that for 9 nodes/3 links there is no solution.

I've tried 19 nodes / 5 links for over 6 hours but no result yet.
This scenario should be attacked with a combination of brute force and some smart pre-constructing I guess.

[RW]

The scenario for 15 GSCs is much more complicated, I will show it next time.

Here's a shot for 15 GSCs, hopefully I understood all the rules correctly...

Divide into 3 groups of 5, let's call the groups A, B and C.

Each group is arranged in a circle, with links between neighbours.

Outgoing connections from group A:
A1-B3&C3
A2-B1&C1
A3-B4&C4
A4-B2&C2
A5-B5&C5

Connections between group B and C:
B1-C3
B2-C1
B3-C4
B4-C2
B5-C5

And the SCM:

Code: Select all

   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  0  1  .  .  1  .  .  1  .  .  .  .  1  .  .
A2  1  0  1  .  .  1  .  .  .  .  1  .  .  .  .
A3  .  1  0  1  .  .  .  .  1  .  .  .  .  1  .
A4  .  .  1  0  1  .  1  .  .  .  .  1  .  .  .
A5  1  .  .  1  0  .  .  .  .  1  .  .  .  .  1
B1  .  1  .  .  .  0  1  .  .  1  .  .  1  .  .
B2  .  .  .  1  .  1  0  1  .  .  1  .  .  .  .
B3  1  .  .  .  .  .  1  0  1  .  .  .  .  1  .
B4  .  .  1  .  .  .  .  1  0  1  .  1  .  .  .
B5  .  .  .  .  1  1  .  .  1  0  .  .  .  .  1
C1  .  1  .  .  .  .  1  .  .  .  0  1  .  .  1
C2  .  .  .  1  .  .  .  .  1  .  1  0  1  .  .
C3  1  .  .  .  .  1  .  .  .  .  .  1  0  1  .
C4  .  .  1  .  .  .  .  1  .  .  .  .  1  0  1
C5  .  .  .  .  1  .  .  .  .  1  1  .  .  1  0


   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  0  1  2  2  1  2  2  1  2  2  2  2  1  2  2
A2  1  0  1  2  2  1  2  2  2  2  1  2  2  2  2
A3  2  1  0  1  2  2  2  2  1  2  2  2  2  1  2
A4  2  2  1  0  1  2  1  2  2  2  2  1  2  2  2
A5  1  2  2  1  0  2  2  2  2  1  2  2  2  2  1
B1  2  1  2  2  2  0  1  2  2  1  2  2  1  2  2
B2  2  2  2  1  2  1  0  1  2  2  1  2  2  2  2
B3  1  2  2  2  2  2  1  0  1  2  2  2  2  1  2
B4  2  2  1  2  2  2  2  1  0  1  2  1  2  2  2
B5  2  2  2  2  1  1  2  2  1  0  2  2  2  2  1
C1  2  1  2  2  2  2  1  2  2  2  0  1  2  2  1
C2  2  2  2  1  2  2  2  2  1  2  1  0  1  2  2
C3  1  2  2  2  2  1  2  2  2  2  2  1  0  1  2
C4  2  2  1  2  2  2  2  1  2  2  2  2  1  0  1
C5  2  2  2  2  1  2  2  2  2  1  1  2  2  1  0

[Edit: I think this same system could be used to connect 20 RSCs (5 links), but I don't have time to write the SCM now.]

RW

[simon_blow_snow]

I've speeded up the program with factor 5.

Now it finds the first solution for 10 nodes/3 links in about 20 seconds.
In 5 - 6 minutes it confirms that for 9 nodes/3 links there is no solution.

I've tried 19 nodes / 5 links for over 6 hours but no result yet.
This scenario should be attacked with a combination of brute force and some smart pre-constructing I guess.

Wow thanks so much dyitto!

Hopefully your program will yield solid results. Once I actually tried really hard to mathematically verify the impossibility of (N,M)=(19,5) but no luck at all. And the fact that (N,M)=(21,5) is possible does not help.

Hopefully your program will return positive results on (16,5),(17,5),(18,5),(20,5),(21,5),(22,5) and more importantly, (24,5)!

[dyitto]

You're welcome, simon!

I've quite finished another version that allows to enter an initial situation, and specify which links should remain present or absent.
That means you could enter an initial tree which you think may be promising, and have the program search only where you think it's useful.
I've been running such an attack for 19/5 already tonight, but no result after 6 hrs.

I suggest, when I've cleaned up the UI I'll put it on my site and anyone can run it.
Especially since I've no accomodation myself to run a program for a real substantial amount of time - like 24hrs or longer.

Also I am quite certain that GSCs for 16/17 agents and RSCs for 26 agents are mathematically impossible, and it have been proven by graph theorists over the years.
However it would be much better if the programming experts can prove it via brute force!

Could you elaborate on this a bit more?
Why the 'quite' in 'quite certain' if 'graph theorists have proven it over the years'?

[simon_blow_snow]

Here's a shot for 15 GSCs, hopefully I understood all the rules correctly...

Great work RW, it is absolutely correct! My construction is a little bit different, but they all lead to the same isomorphic arrangement. I believe it has been mathematically proven that the solution is essentially unique (barring isomorphs), much like the case for 10 BSCs.

[Edit: I think this same system could be used to connect 20 RSCs (5 links), but I don't have time to write the SCM now.]

Yes for all multiples of 5, this approach seems to work fine. But it does not always give you the most "economical" arrangements. For example, (25,6) is still marginally necessary, but (30,7) & (35,8) are much worse than the optimal results. In fact, with a maximum of 7 links each, it is possible to connect 50 nodes, which is the theoretical upper bound. But I won't go there yet as my main focus here is to work on the (19,5) case.

If you want to flex your mental muscles, I recommend you to work on (24,5). It would be very satisfying if you work out this arrangement on your own (which is also essentially unique I think).

[simon_blow_snow]

Also I am quite certain that GSCs for 16/17 agents and RSCs for 26 agents are mathematically impossible, and it have been proven by graph theorists over the years.
However it would be much better if the programming experts can prove it via brute force!

Could you elaborate on this a bit more?
Why the 'quite' in 'quite certain' if 'graph theorists have proven it over the years'?

Okay, I am absolutely certain.

The M^2+1 upper bound is properly called "Moore bound" in mathematics. It has been proven that the only possible scenarios for this bound to be reached are (5,2),(10,3),(50,7) and perhaps (3250,57). And also it has been proven that the Moore bound minus one, i.e. M^2, is only possible for one case, (4,2). I have done some light research on this but I think the mathematics involved is quite intimidating and might throw off the general audience, turning the topic into a dry boring lecture of combinatorial mathematics. That's why I wrote the KGB story and hope it would be more appealing to the programming experts here.

But again, although the mathematicians have work so hard on the cases close to the limit, e.g. (15,4) & (24,5), little research has been done for other cases, such as the dreaded (19,5) which has been bothering me for a very long time. That's why I created this thread to sought help from you guys, and hopefully fruitful results would come out this time!

I will show the results for other cases soon. One good thing about this problem is it can pose as both a tough programming exercise as well as a challenging mental puzzle for specific cases!

[simon_blow_snow]

I have drawn up some "text graphics" for a few of the scenarios:

Code: Select all

10 BSCs (10 nodes, max 3 links each):

+---+     +---+     +---+
| B1|-----| B |-----| B2|
+---+     +---+     +---+
  |  \      |      /  |
  |   \   +---+   /   |
  |    \  | Z |  /    |
  |     \ +---+ /     |
  |      X     X      |
+---+   / \   / \   +---+
| A1|--/---\-/---\--| C2|
+---+ /     X     \ +---+
  |  /     / \     \  |
+---+ +---+   +---+ +---+
| A |-| A2|---| C1|-| C |
+---+ +---+   +---+ +---+


Code: Select all

12 GSCs (12 nodes, max 4 links each):

       +---+       +---+
       | B6|-------| B5|
       +---+\_   _/+---+
      /  |    \ /    |  \
     /   |     X     |   \
    /    |   _/ \_   |    \
   /     | _/     \_ |     \
+---+    |/  +---+  \|    +---+
| A6|----/---| A1|---\----| A2|
+---+   /|   +---+   |\   +---+
  |\   / |  /     \  | \   /|
  | \ /+---+       +---+\ / |
  |  X | B1|       | B4| X  |
  | / \+---+       +---+/ \ |
  |/   \ |  \     /  | /   \|
+---+   \|   +---+   |/   +---+
| A5|----\---| A4|---/----| A3|
+---+    |\_ +---+ _/|    +---+
   \     |  \_   _/  |     /
    \    |    \ /    |    /
     \   |     X     |   /
      \  |   _/ \_   |  /
       +---+/     \+---+
       | B2|-------| B3|
       +---+       +---+


Code: Select all

13 GSCs (13 nodes, max 4 links each):

       +---+       +---+
       | B6|-------| B5|
       +---+\_   _/+---+
      /  |    \ /    |  \
     /   |     X     |   \
    /    |   _/ \_   |    \
   /     | _/     \_ |     \
+---+    |/  +---+  \|    +---+
| A6|----/---| A1|---\----| A2|
+---+   /|   +---+   |\   +---+
  |\   / |     |     | \   /|
  | \ /+---+ +---+ +---+\ / |
  |  X | B1|-| C |-| B4| X  |
  | / \+---+ +---+ +---+/ \ |
  |/   \ |     |     | /   \|
+---+   \|   +---+   |/   +---+
| A5|----\---| A4|---/----| A3|
+---+    |\_ +---+ _/|    +---+
   \     |  \_   _/  |     /
    \    |    \ /    |    /
     \   |     X     |   /
      \  |   _/ \_   |  /
       +---+/     \+---+
       | B2|-------| B3|
       +---+       +---+


Code: Select all

14 GSCs (14 nodes, max 4 links each):

       +---+         +---+
       | B5|---------| A2|
       +---+\       /+---+
      /  |   \     /   |  \
     /   |    \   /    |   \
+---+    |     \ /     |    +---+
| B6|----+------X------+----| A3|
+---+    | +---+ +---+ |    +---+
  |  \   | | A1| | B4| |   /  |
  |   \  | +---+ +---+ |  /   |
  |    \ | / |  X  | \ | /    |
  |     \|/+---+ +---+\|/     |
  |      X | C | | D | X      |
  |     /|\+---+ +---+/|\     |
  |    / | \ |  X  | / | \    |
  |   /  | +---+ +---+ |  \   |
  |  /   | | B1| | A4| |   \  |
+---+    | +---+ +---+ |    +---+
| A6|----+------X------+----| B3|
+---+    |     / \     |    +---+
     \   |    /   \    |   /
      \  |   /     \   |  /
       +---+/       \+---+
       | A5|---------| B2|
       +---+         +---+


The 15 GSCs scenario is quite difficult to draw out. I will see what I can do later.

[simon_blow_snow]

I will give up on drawing the text graphics for now. Back to describing the connection arrangements:


15 GSCs (15 nodes, max 4 links each):

Divide them into 3 different groups of 5: A1,A2,A3,A4,A5, B1,B2,B3,B4,B5, C1,C2,C3,C4,C5. Arrange each group into a circle, linking the neighbours.

Next, order the groups in the following cyclic manner A->B->C->A->B, so each group has a previous and a next (e.g. C's previous is B, its next is A).

Then we link each GSC to the next group's GSC with double the index (mod 5). Say B4, double the index (mod 5) is 8 (mod 5), which is 3. So we link B4 to C3. Starting from A1, we have the following 12 elements cycle:

A1-B2-C4-A3-B1-C2-A4-B3-C1-A2-B4-C3-A1

Also, A5,B5,C5 are linked together as a triangle, which also follows the previous rule as 5 (mod 5) & 5*2 (mod 5) are both equal to 0 (mod 5).

Now to verify this works. We use group B as an example because all groups are rotationally symmetric now. All groups are already interconnected via the circles, so we just need to demonstrate the cross-group connections.

For B1, it is directly linked to A3,C2,B2,B5. A3 bridges to A2,A4, C2 bridges to C1,C3, B2 bridges to A1,C4, B5 bridges to A5,C5.
For B2, it is directly linked to A1,C4,B1,B3. A1 bridges to A2,A5, C4 bridges to C3,C5, B1 bridges to A3,C2, B3 bridges to A4,C1.
For B3, it is directly linked to A4,C1,B2,B4. A4 bridges to A3,A5, C1 bridges to C2,C5, B2 bridges to A1,C4, B4 bridges to A2,C3.
For B4, it is directly linked to A2,C3,B3,B5. A2 bridges to A1,A3, C3 bridges to C2,C4, B3 bridges to A4,C1, B5 bridges to A5,C5.
For B5, it is directly linked to A5,C5,B1,B4. A5 bridges to A1,A4, C5 bridges to C1,C4, B1 bridges to A3,C2, B4 bridges to A2,C3.


As shown all GSCs are connected to all others. This is the SCM:

Code: Select all

   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  .  1  .  .  1  .  1  .  .  .  .  .  1  .  .
A2  1  .  1  .  .  .  .  .  1  .  1  .  .  .  .
A3  .  1  .  1  .  1  .  .  .  .  .  .  .  1  .
A4  .  .  1  .  1  .  .  1  .  .  .  1  .  .  .
A5  1  .  .  1  .  .  .  .  .  1  .  .  .  .  1
B1  .  .  1  .  .  .  1  .  .  1  .  1  .  .  .
B2  1  .  .  .  .  1  .  1  .  .  .  .  .  1  .
B3  .  .  .  1  .  .  1  .  1  .  1  .  .  .  .
B4  .  1  .  .  .  .  .  1  .  1  .  .  1  .  .
B5  .  .  .  .  1  1  .  .  1  .  .  .  .  .  1
C1  .  1  .  .  .  .  .  1  .  .  .  1  .  .  1
C2  .  .  .  1  .  1  .  .  .  .  1  .  1  .  .
C3  1  .  .  .  .  .  .  .  1  .  .  1  .  1  .
C4  .  .  1  .  .  .  1  .  .  .  .  .  1  .  1
C5  .  .  .  .  1  .  .  .  .  1  1  .  .  1  .

   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  0  1  2  2  1  2  1  2  2  2  2  2  1  2  2
A2  1  0  1  2  2  2  2  2  1  2  1  2  2  2  2
A3  2  1  0  1  2  1  2  2  2  2  2  2  2  1  2
A4  2  2  1  0  1  2  2  1  2  2  2  1  2  2  2
A5  1  2  2  1  0  2  2  2  2  1  2  2  2  2  1
B1  2  2  1  2  2  0  1  2  2  1  2  1  2  2  2
B2  1  2  2  2  2  1  0  1  2  2  2  2  2  1  2
B3  2  2  2  1  2  2  1  0  1  2  1  2  2  2  2
B4  2  1  2  2  2  2  2  1  0  1  2  2  1  2  2
B5  2  2  2  2  1  1  2  2  1  0  2  2  2  2  1
C1  2  1  2  2  2  2  2  1  2  2  0  1  2  2  1
C2  2  2  2  1  2  1  2  2  2  2  1  0  1  2  2
C3  1  2  2  2  2  2  2  2  1  2  2  1  0  1  2
C4  2  2  1  2  2  2  1  2  2  2  2  2  1  0  1
C5  2  2  2  2  1  2  2  2  2  1  1  2  2  1  0


This cyclic approach can also be used for larger scenarios to ensure easy verification.

[simon_blow_snow]

Now immediately on to the RSCs (max 5 links each):


16 RSCs (16 nodes, max 5 links each):

Divide them into 4 groups of 4 (ABCD x 1234). Each group (ABCD) is linked as a circle. Also RSCs with the same index (e.g. A1,B1,C1,D1) are also linked as circles. Finally, RSCs two groups and two indices apart are linked together, e.g. A1-C3, B4-D2. Since all nodes are symmetrically linked, just verify using B2 as an example:

B2 is directly linked to B1,B3,A2,C2,D4.
B4 is bridged from B1 or B3.
D2 is bridged from A2 or C2.
A1,A3 are bridged from A2.
C1,C3 are bridged from C2.
D1,D3,A4,C4 are bridged from D4.

Hence all other 15 RSCs are connected to B2. Ditto for the rest. This is the SCM:

Code: Select all

   A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4
A1  .  1  .  1  1  .  .  .  .  .  1  .  1  .  .  .
A2  1  .  1  .  .  1  .  .  .  .  .  1  .  1  .  .
A3  .  1  .  1  .  .  1  .  1  .  .  .  .  .  1  .
A4  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  .  .
C1  .  .  1  .  1  .  .  .  .  1  .  1  1  .  .  .
C2  .  .  .  1  .  1  .  .  1  .  1  .  .  1  .  .
C3  1  .  .  .  .  .  1  .  .  1  .  1  .  .  1  .
C4  .  1  .  .  .  .  .  1  1  .  1  .  .  .  .  1
D1  1  .  .  .  .  .  1  .  1  .  .  .  .  1  .  1
D2  .  1  .  .  .  .  .  1  .  1  .  .  1  .  1  .
D3  .  .  1  .  1  .  .  .  .  .  1  .  .  1  .  1
D4  .  .  .  1  .  1  .  .  .  .  .  1  1  .  1  .

   A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4
A1  0  1  2  1  1  2  2  2  2  2  1  2  1  2  2  2
A2  1  0  1  2  2  1  2  2  2  2  2  1  2  1  2  2
A3  2  1  0  1  2  2  1  2  1  2  2  2  2  2  1  2
A4  1  2  1  0  2  2  2  1  2  1  2  2  2  2  2  1
B1  1  2  2  2  0  1  2  1  1  2  2  2  2  2  1  2
B2  2  1  2  2  1  0  1  2  2  1  2  2  2  2  2  1
B3  2  2  1  2  2  1  0  1  2  2  1  2  1  2  2  2
B4  2  2  2  1  1  2  1  0  2  2  2  1  2  1  2  2
C1  2  2  1  2  1  2  2  2  0  1  2  1  1  2  2  2
C2  2  2  2  1  2  1  2  2  1  0  1  2  2  1  2  2
C3  1  2  2  2  2  2  1  2  2  1  0  1  2  2  1  2
C4  2  1  2  2  2  2  2  1  1  2  1  0  2  2  2  1
D1  1  2  2  2  2  2  1  2  1  2  2  2  0  1  2  1
D2  2  1  2  2  2  2  2  1  2  1  2  2  1  0  1  2
D3  2  2  1  2  1  2  2  2  2  2  1  2  2  1  0  1
D4  2  2  2  1  2  1  2  2  2  2  2  1  1  2  1  0


[dyitto]

I've quite finished another version that allows to enter an initial situation, and specify which links should remain present or absent.
That means you could enter an initial tree which you think may be promising, and have the program search only where you think it's useful.
I've been running such an attack for 19/5 already tonight, but no result after 6 hrs.

Currently I'm searching for a 19/5 within the following construction:

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

The project can be downloaded here so anyone can use it for similar searches.