Secret Communicator Matrix

Notes on possible new logic puzzles

Re: Secret Communicator Matrix

Postby simon_blow_snow » Sun Feb 06, 2011 7:12 pm

BryanL wrote:Maybe it could be shown by the exact cover algorithm whether there is or isn't an arangement for a given n with x agents.

I haven't the time or energy to try and work out the possible rows and constraints. I do however already have the code as it applies to sudoku and it wouldn't be hard to apply it to this problem if someone worked out the constraints. Tarek seemed to do ok with setdoku but never gave enough info for me to follow and I wasn't interested enough to try and nut it out or reinvent the wheel...

One point about exact cover. If it is applicable, then for any solutions it finds, the arrangements will be part of the solution.

Yes, programming for the exact cover algorithm could be very helpful there. I cannot do it myself so would really appreciate if someone like you, tarek, dyitto can help me out.

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!
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby BryanL » Sun Feb 06, 2011 10:02 pm

simon_blow_snow wrote:Okay I will try to type up the lengthy answers for 9/10 BSCs and reveal it soon.

For the 9 case, my guess is that removing a node removes too many direct links which removes too many bridged links. - just a guess... :)

The Petersen Graph is the unique arrangement for 10 BSCs to connect altogether. Any solution one can come up with must be isomorphic (in Sudoku sense) to it.

Yes. In my reading I think I even read the isomorphic term used in reference to graphs.

BryanL wrote:It leads to a much nicer symmetric diagram with a central node which is what I think you were after.

The one with central node is one possible graphical representation to the Petersen Graph. A more popular representation is to lay them out in two layers of 5 nodes, and connect the outer layer as a pentagon, the inside layer as a pentagram (star pentagon), and then connect the 5 links between corresponding nodes in each layer.

There is also a third graphical representation which resemble a tree structure. That was the one I said I would elaborate later.

Yes I saw the pentagram inside pentagram. Drawing a graphical representation got a bit messy as the links get a bit close to each other. i guess one could use arcs.

BryanL wrote:I can also see that 3d and more is the way to get maximum nodes.

I don't quite understand this statement. Do you mean "3d" as "3-dimentional"? I only think of them in 2-dimensional sense. Of course, many graphs of the connection arrangements are non-planar, but I still try to present them in 2D only.

Wasn't my original mistake because I only considered the planar case?

This is good because I have already started to formulate 3d pictures in my mind - haven't got anywhere with them yet... :)

My feeling is that even though we can only show them in 2d, the structure for higher orderings will exist in more than 2d.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sun Feb 06, 2011 10:28 pm

simon_blow_snow wrote:
BryanL wrote:Maybe it could be shown by the exact cover algorithm whether there is or isn't an arangement for a given n with x agents.

Yes, programming for the exact cover algorithm could be very helpful there. I cannot do it myself so would really appreciate if someone like you, tarek, dyitto can help me out.

I have 6 days before I go away for a two week intensive course. I also need to use those days to focus so can't give too much to this.
I will watch and contribute as much as I feel I can because I think it will be a great application of exact cover and I would love to program it - if it is applicable...

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!

Reading about graphs, there have been so many great minds at work for many years on these types of problems...
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Mon Feb 07, 2011 7:45 am

Simon, because I don't know how much you know of exact cover I will give a brief summary for the vanilla sudoku case.

There are 81 cells each with a possible 9 candidates and that is represented by 81 * 9 rows in the matrix.

There are 4 constraints - only 1 number per cell, only one of each number per row, one of each per column and one of each per 3 * 3 box - giving 4 * 81 columns.

Exact cover works by trying every combination - until 0, 1 or more solutions are found.

I have progressed an exact cover solution as DLX to a point. Crazy how much time I spent trying to implement the harder stuff while this simple start was staring me in the face... :roll:

I will use the WSC, n = 2 and maximun agents x = 5 as my example.

First, the constraints as I see them:

Constraint 1: 10 links - 5 direct, 5 bridged, from DL = trunc(nx/2) and is it BL = Sx-1 - trunc(nx/2)???

Constraint 2: Only one link between any two nodes.

Constraint 3: Each node can have at most n direct links.

Constraint 4: A bridged link can only exist between 2 nodes with a common directly linked node.

Constraint 5: Perhaps not a constraint but an implementation requirement. Satisfy all possible direct links before trying bridged links.

Constraint 1 and 2 seem easy to implement in an exact cover matrix as shown below. 10 * 10 rows, 10 columns for each constraint.

Constraints 3 and 4 I can't yet see how they could be introduced to the matrix however they would be easy to program into the DLX column selection process with a simple test for each constraint.
It would be really great if someone could get them into the matrix.

Constraint 5 would be another test in the column selection process.

It is not necessary to include every type of bridged link (ACB, ADB, etc) in the lower rows. AB, AC.. DE are enough. They were there from when i was trying to introduce constraint 4 and they may serve to spark an idea.

Hidden Text: Show
Code: Select all
             Constraint 1         Constraint 2        Constraint 3        Constraint 4
                                                                                             
        |    10 links         | Only 1 link between | Max n direct      | A bridged link can only
        |    5 direct         | between any 2 nodes | links to any node | exist if there are direct
        |    5 bridged        |                     |                   | links to a common node
        |                   1 |                     |
        | 1 2 3 4 5 6 7 8 9 0 | A A A A B B B C C D |
        |                     | B C D E C D E D E E |
        |                     |                     |
DL1 AB  | x                   | x                   |
DL1 AC  | x                   |   x                 |
DL1 AD  | x                   |     x               |
DL1 AE  | x                   |       x             |
DL1 BC  | x                   |         x           |
DL1 BD  | x                   |           x         |
DL1 BE  | x                   |             x       |
DL1 CD  | x                   |               x     |
DL1 CE  | x                   |                 x   |
DL1 DE  | x                   |                   x |
--------+---------------------+---------------------+
DL2 AB  |   x                 | x                   |
DL2 AC  |   x                 |   x                 |
DL2 AD  |   x                 |     x               |
DL2 AE  |   x                 |       x             |
DL2 BC  |   x                 |         x           |
DL2 BD  |   x                 |           x         |
DL2 BE  |   x                 |             x       |
DL2 CD  |   x                 |               x     |
DL2 CE  |   x                 |                 x   |
DL2 DE  |   x                 |                   x |
--------+---------------------+---------------------+
DL3 AB  |     x               | x                   |
DL3 AC  |     x               |   x                 |
DL3 AD  |     x               |     x               |
DL3 AE  |     x               |       x             |
DL3 BC  |     x               |         x           |
DL3 BD  |     x               |           x         |
DL3 BE  |     x               |             x       |
DL3 CD  |     x               |               x     |
DL3 CE  |     x               |                 x   |
DL3 DE  |     x               |                   x |
--------+---------------------+---------------------+
DL4 AB  |       x             | x                   |
DL4 AC  |       x             |   x                 |
DL4 AD  |       x             |     x               |
DL4 AE  |       x             |       x             |
DL4 BC  |       x             |         x           |
DL4 BD  |       x             |           x         |
DL4 BE  |       x             |             x       |
DL4 CD  |       x             |               x     |
DL4 CE  |       x             |                 x   |
DL4 DE  |       x             |                   x |
--------+---------------------+---------------------+
DL5 AB  |         x           | x                   |
DL5 AC  |         x           |   x                 |
DL5 AD  |         x           |     x               |
DL5 AE  |         x           |       x             |
DL5 BC  |         x           |         x           |
DL5 BD  |         x           |           x         |
DL5 BE  |         x           |             x       |
DL5 CD  |         x           |               x     |
DL5 CE  |         x           |                 x   |
DL5 DE  |         x           |                   x |
--------+---------------------+---------------------+
BL1 ACB |           x         | x                   |
BL1 ADB |           x         | x                   |
BL1 AEB |           x         | x                   |
BL1 ABC |           x         |   x                 |
BL1 ADC |           x         |   x                 |
BL1 AEC |           x         |   x                 |
BL1 ABD |           x         |     x               |
BL1 ACD |           x         |     x               |
BL1 AED |           x         |     x               |
BL1 ABE |           x         |       x             |
BL1 ACE |           x         |       x             |
BL1 ADE |           x         |       x             |
BL1 BAC |           x         |         x           |
BL1 BDC |           x         |         x           |
BL1 BEC |           x         |         x           |
BL1 BAD |           x         |           x         |
BL1 BCD |           x         |           x         |
BL1 BED |           x         |           x         |
BL1 BAE |           x         |             x       |
BL1 BCE |           x         |             x       |
BL1 BDE |           x         |             x       |
BL1 CAD |           x         |               x     |
BL1 CBD |           x         |               x     |
BL1 CED |           x         |               x     |
BL1 CAE |           x         |                 x   |
BL1 CBE |           x         |                 x   |
BL1 CDE |           x         |                 x   |
BL1 DAE |           x         |                   x |
BL1 DBE |           x         |                   x |
BL1 DCE |           x         |                   x |
--------+---------------------+---------------------+
BL2 ACB |             x       | x                   |
BL2 ADB |             x       | x                   |
BL2 AEB |             x       | x                   |
BL2 ABC |             x       |   x                 |
BL2 ADC |             x       |   x                 |
BL2 AEC |             x       |   x                 |
BL2 ABD |             x       |     x               |
BL2 ACD |             x       |     x               |
BL2 AED |             x       |     x               |
BL2 ABE |             x       |       x             |
BL2 ACE |             x       |       x             |
BL2 ADE |             x       |       x             |
BL2 BAC |             x       |         x           |
BL2 BDC |             x       |         x           |
BL2 BEC |             x       |         x           |
BL2 BAD |             x       |           x         |
BL2 BCD |             x       |           x         |
BL2 BED |             x       |           x         |
BL2 BAE |             x       |             x       |
BL2 BCE |             x       |             x       |
BL2 BDE |             x       |             x       |
BL2 CAD |             x       |               x     |
BL2 CBD |             x       |               x     |
BL2 CED |             x       |               x     |
BL2 CAE |             x       |                 x   |
BL2 CBE |             x       |                 x   |
BL2 CDE |             x       |                 x   |
BL2 DAE |             x       |                   x |
BL2 DBE |             x       |                   x |
BL2 DCE |             x       |                   x |
--------+---------------------+---------------------+
BL3 ACB |               x     | x                   |
BL3 ADB |               x     | x                   |
BL3 AEB |               x     | x                   |
BL3 ABC |               x     |   x                 |
BL3 ADC |               x     |   x                 |
BL3 AEC |               x     |   x                 |
BL3 ABD |               x     |     x               |
BL3 ACD |               x     |     x               |
BL3 AED |               x     |     x               |
BL3 ABE |               x     |       x             |
BL3 ACE |               x     |       x             |
BL3 ADE |               x     |       x             |
BL3 BAC |               x     |         x           |
BL3 BDC |               x     |         x           |
BL3 BEC |               x     |         x           |
BL3 BAD |               x     |           x         |
BL3 BCD |               x     |           x         |
BL3 BED |               x     |           x         |
BL3 BAE |               x     |             x       |
BL3 BCE |               x     |             x       |
BL3 BDE |               x     |             x       |
BL3 CAD |               x     |               x     |
BL3 CBD |               x     |               x     |
BL3 CED |               x     |               x     |
BL3 CAE |               x     |                 x   |
BL3 CBE |               x     |                 x   |
BL3 CDE |               x     |                 x   |
BL3 DAE |               x     |                   x |
BL3 DBE |               x     |                   x |
BL3 DCE |               x     |                   x |
--------+---------------------+---------------------+
BL4 ACB |                 x   | x                   |
BL4 ADB |                 x   | x                   |
BL4 AEB |                 x   | x                   |
BL4 ABC |                 x   |   x                 |
BL4 ADC |                 x   |   x                 |
BL4 AEC |                 x   |   x                 |
BL4 ABD |                 x   |     x               |
BL4 ACD |                 x   |     x               |
BL4 AED |                 x   |     x               |
BL4 ABE |                 x   |       x             |
BL4 ACE |                 x   |       x             |
BL4 ADE |                 x   |       x             |
BL4 BAC |                 x   |         x           |
BL4 BDC |                 x   |         x           |
BL4 BEC |                 x   |         x           |
BL4 BAD |                 x   |           x         |
BL4 BCD |                 x   |           x         |
BL4 BED |                 x   |           x         |
BL4 BAE |                 x   |             x       |
BL4 BCE |                 x   |             x       |
BL4 BDE |                 x   |             x       |
BL4 CAD |                 x   |               x     |
BL4 CBD |                 x   |               x     |
BL4 CED |                 x   |               x     |
BL4 CAE |                 x   |                 x   |
BL4 CBE |                 x   |                 x   |
BL4 CDE |                 x   |                 x   |
BL4 DAE |                 x   |                   x |
BL4 DBE |                 x   |                   x |
BL4 DCE |                 x   |                   x |
--------+---------------------+---------------------+
BL5 ACB |                   x | x                   |
BL5 ADB |                   x | x                   |
BL5 AEB |                   x | x                   |
BL5 ABC |                   x |   x                 |
BL5 ADC |                   x |   x                 |
BL5 AEC |                   x |   x                 |
BL5 ABD |                   x |     x               |
BL5 ACD |                   x |     x               |
BL5 AED |                   x |     x               |
BL5 ABE |                   x |       x             |
BL5 ACE |                   x |       x             |
BL5 ADE |                   x |       x             |
BL5 BAC |                   x |         x           |
BL5 BDC |                   x |         x           |
BL5 BEC |                   x |         x           |
BL5 BAD |                   x |           x         |
BL5 BCD |                   x |           x         |
BL5 BED |                   x |           x         |
BL5 BAE |                   x |             x       |
BL5 BCE |                   x |             x       |
BL5 BDE |                   x |             x       |
BL5 CAD |                   x |               x     |
BL5 CBD |                   x |               x     |
BL5 CED |                   x |               x     |
BL5 CAE |                   x |                 x   |
BL5 CBE |                   x |                 x   |
BL5 CDE |                   x |                 x   |
BL5 DAE |                   x |                   x |
BL5 DBE |                   x |                   x |
BL5 DCE |                   x |                   x |
--------+---------------------+---------------------+

Last edited by BryanL on Wed Feb 09, 2011 3:26 am, edited 3 times in total.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby tarek » Mon Feb 07, 2011 5:44 pm

I will hopefully attempt to help but I need to understand the concept 1st. This means reading through the posts ... Hopefully I can manage that this week.

tarek
User avatar
tarek
 
Posts: 2574
Joined: 05 January 2006

Re: Secret Communicator Matrix

Postby dyitto » Tue Feb 08, 2011 10:37 pm

I'm as far as having a basic project setup.

It reads and writes text formats. It has a very poor visualisation.
It computes the shortest-path-distances and using this it could correctly reproduce your adjacency matrices so far.

Of course this is still the most trivial part.
How could I share this?

By the way, fo the visualization part this might be helpful:

http://www.graphviz.org/
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Secret Communicator Matrix

Postby BryanL » Thu Feb 10, 2011 11:13 pm

Status update.

I have been giving this more time than i should have. I think i am the original obsessive compulsive...

I have been hacking my DLX code (bastardising it might be more appropriate) . First step was to make a generic case for any given n, x (n + 1 <= x <= n^2 + 1) - I had hard coded everything for 9 * 9 suduko for optimum speed but it wasn't too hard to recreate the code for a generic matrix build for this case with only the two constraints. A few calculations give the number of combinations of agent pairings (agent pairings equates to the number of cells in sudoku), columns and rows. After that it would basically run but there was nothing stopping it giving more than n links per node.

This is where i can regret things i say:

BryanL wrote:Constraints 3 and 4 I can't yet see how they could be introduced to the matrix however they would be easy to program into the DLX column selection process with a simple test for each constraint.

Working on Constraint 3: Each agent can have at most n direct links.

Not so simple. To quote Simon: I could never be more wrong. Not even easy to create an array which stores the number of links created per agent and update at the appropriate times. I had to introduce two new fields to the node structure which contain identifiers for the two connected agents that are represented by the selected node (nodes in the matrix represent comms links in the problem - edges on the graph - AB, AC, etc).

A bit of refresher on DLX workings for those who know it. Typically DLX chooses the col with smallest "size" (number of nodes left) or just the first available. After that, to quote Wikipedia somewhere, it "non-deterministically" chooses a row in that column. In all the code I have seen it is not quite non-deterministic, it always selects the first available node in that column - why not? Especially because that fits in with the simplicity and elegance of Knuth's 2 dimensional doubly linked list. The relevant while loops start at the first node and stop when the next node is the column header node.

I started to put a test in the column selection but found that in reality the test relates to node selection. This is where I am up to and where the fun will start. I need to first select a column (by size) but with an available node per the constraint. Not too hard. But then, the first loop which operates on that column (to cover the other columns) will need to begin at the selected node and progress past the col header and stop when it gets back to the selected node. That wouldn't be too hard in the solve routine, but i have a suspicion that the column cover and uncover routines would need to do the same. This ties in with the exact sequence in reverse for uncover stipulation. All doable but easy to get wrong and i don't even know if it will work... I will have a play with a simple matrix on paper and see what happens. One little bit of joy is that the solution stack contains nodes not col header nodes so no changes required there.

So that is where i am up to. I have to put it on hold for a couple of weeks - what bothers me is that when i get back my focus may be elsewhere.
.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Fri Feb 11, 2011 5:38 am

Sorry all, I have been pre-occupied these few days. Truly thanks for all the help with programming and all. Haven't got much time so I will just list out the results I found manually.


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. If we need to connect 9 SCs together, at least the GSCs (4 RPDs @) must be used.


2. Is it possible to connect 10 BSCs altogether? If yes how? If not why?

Even though 9 BSCs cannot be connected together, if we add 1 extra BSC, then the situation is totally different. Now the maximum total number of RPDs is 10*3=30 which is even, a possible scenario. The remaining problem is to work out the actual arrangement.

I will introduce a method called the "3 levels assignment" which would be very useful in constructing any connection arrangement.

Firstly we assign one BSC as in level 0, and label it Z, which is like the root in a tree structure.

Z would connect to 3 other BSCs, which we assign in level 1, and label them A,B,C. We can refer to them as "moms".

Each of A,B,C would connect to 2 other BSCs (other than Z), which we assign in level 2, and label them A1,A2,B1,B2,C1,C2. We can refer to them as "kids".

This is a graphical view of the structure:

Code: Select all
        Z
     /  |  \
   A    B    C
  /|   / \   |\
A1 A2 B1 B2 C1 C2


It is obvious Z has already establish communication with all other BSCs. All it requires for altogether connection is to do the same of the 9 remaining BSCs.

To do this we need to systematically add direct links among the 6 "kids". Say we adopt the following system:

Code: Select all
B1 links to A1,C1. B2 links to A2,C2. A1 links to C2. A2 links to C1.


In a nutshell the group B (middle group) kids links to other kids with the same index, while the 2 other groups have links between kids with different indices.

Now we can check the actual situation for each BSC:

For moms (A,B,C), they have direct links to Z and their own kids, and have bridged communication to other moms (via Z) and other kids (via their own kids).

For kids (A1,A2,B1,B2,C1,C2), they have direct links to the their own moms, and 2 kids from other groups, and have bridged communication to Z and the other kids of the same group (via their own moms), as well as other moms and kids (via the 2 other kids they link to).

This is the SCM for this arrangement:

Code: Select all
    Z  A  B  C A1 A2 B1 B2 C1 C2
 Z  .  1  1  1  .  .  .  .  .  .
 A  1  .  .  .  1  1  .  .  .  .
 B  1  .  .  .  .  .  1  1  .  .
 C  1  .  .  .  .  .  .  .  1  1
A1  .  1  .  .  .  .  1  .  .  1
A2  .  1  .  .  .  .  .  1  1  .
B1  .  .  1  .  1  .  .  .  1  .
B2  .  .  1  .  .  1  .  .  .  1
C1  .  .  .  1  .  1  1  .  .  .
C2  .  .  .  1  1  .  .  1  .  .

    Z  A  B  C A1 A2 B1 B2 C1 C2
 Z  0  1  1  1  2  2  2  2  2  2
 A  1  0  2  2  1  1  2  2  2  2
 B  1  2  0  2  2  2  1  1  2  2
 C  1  2  2  0  2  2  2  2  1  1
A1  2  1  2  2  0  2  1  2  2  1
A2  2  1  2  2  2  0  2  1  1  2
B1  2  2  1  2  1  2  0  2  1  2
B2  2  2  1  2  2  1  2  0  2  1
C1  2  2  2  1  2  1  1  2  0  2
C2  2  2  2  1  1  2  2  1  2  0


With some permutations, this SCM can be shown isomorphic to the one I provided earlier, which was attributed to the well known "Petersen Graph".
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Fri Feb 11, 2011 5:59 am

Bryan

Lots of thanks for the effort to implement it using the DLX algorithm. You are right that I don't have much knowledge/experience in this subject, and it will take me a while before I can catch up to your terminology, descriptions etc. But hopefully I will get there at the end.

For me the ultimate goal of this programming exercise is to work out the possibility of 19 RSCs (5 direct links each), and the actual arrangement if any.


I will go out on a limb and list out all the possible scenarios that I know of. And then given time I will list out their arrangements in detail in the future. Hopefully the programming experts can get there before me (I really hope so). Then perhaps we can explore the problem for larger sizes (e.g. SCs with 6, 7 or even more direct links each).

WSCs (2 direct links each) can support communications for 2,3,4,5 agents.

BSCs (3 direct links each) can support communications for 6,7,8,10 agents (as well as 2-5).

GSCs (4 direct links each) can support communications for 9,11,12,13,14,15 agents (as well as 2-8,10).

RSCs (5 direct links each) can support communications for 16,17,18,20,21,22,24 agents (as well as 2-15).

The possibility of RSCs supporting 19 agents has not been determined yet.
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 12, 2011 7:45 am

.
Last update for two weeks...

Selecting a node other than the first doesn't work.

I played around a bit more using extra columns to limit edges to a given agent to n (I would say node but save the term node for the dlx matrix).

I thought I might have had it but it needs refinement.

The idea was to have n extra columns per agent, not linked to every row in the matrix but evenly distributed (two per 10 rows). I tested on just one agent and needed two links per 10 rows (n = 2, x = 5) and that was ok. But when I fleshed it out with all 5 agents, the extra nodes covered too many other nodes before completion - note cols with 0 nodes left. I will try when i get back with just one link per extra column evenly distributed - no guarantees...

Diagram follows for what i tried.

As I said it is wrong and will try just one extra node per 10 rows.

Hidden Text: Show
Code: Select all
                                                                                                                 
                                                                                                                 
  n = 2, x = 5   1st choice is col 1 row AB, 2nd choice is col 2 row AE, 3rd choice is col 5 row BD,             
                 4th choice is col 3 row CE                                                                     
                                                                            Legend    x : uncovered node         
             Constraint 1         Constraint 2        Constraint 3                 c1-5 : covered node           
                                                                                   C1-5 : covered column         
        |    10 links         | Only 1 link between | Only n links to any node     xab  : uncovered extra node   
        |    5 direct         | between any 2 nodes |                             1-5ab : covered extra node     
        |    5 bridged        |                     |                                                           
        |                   1 |                     |                                                           
        | 1 2 3 4 5 6 7 8 9 0 | A A A A B B B C C D |  A1 |  A2 |  B1 |  B2 |  C1 |  C2 |  D1 |  D2 |  E1 |  E2 |
        |                     | B C D E C D E D E E |     |     |     |     |     |     |     |     |     |     |
        |                     |                     |     |     |     |     |     |     |     |     |     |     |
        | C1C2C4  C3          | C1    C2  C3    C4  |  C1 |  C2 |  C1 |  C3 |  C4 |     |  C3 |     |  C4 |  C2 |
        | 10 5 1 1 3 0 1 1 0 1|                     |     |     |     |     |     |     |     |     |     |     |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
DL1 AB  | x                   | c1                  | 1ab |     | 1ba |     |     |     |     |     |     |     |
DL1 AC  | x                   |   c1                | 1ac |     |     |     | 1ca |     |     |     |     |     |
DL1 AD  | x                   |     c1              |     | 1ad |     |     |     |     | 1da |     |     |     |
DL1 AE  | x                   |       c1            |     | 1ae |     |     |     |     |     |     | 1ea |     |
DL1 BC  | x                   |         c1          |     |     | 1bc |     | 1cb |     |     |     |     |     |
DL1 BD  | x                   |           c1        |     |     |     | 1bd |     |     | 1db |     |     |     |
DL1 BE  | x                   |             c1      |     |     |     | 1be |     |     |     |     | 1eb |     |
DL1 CD  | x                   |               c1    |     |     |     |     |     | 1cd |     | 1dc |     |     |
DL1 CE  | x                   |                 c1  |     |     |     |     |     | 1ce |     |     |     | 1ec |
DL1 DE  | x                   |                   c1|     |     |     |     |     |     |     | 1de |     | 1ed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
DL2 AB  |   c1                | x                   |     | 1ab |     | 1ba |     |     |     |     |     |     |
DL2 AC  |   c1                |   c1                | xac |     |     |     |     | 1ca |     |     |     |     |
DL2 AD  |   c1                |     c1              | xad |     |     |     |     |     |     | 1da |     |     |
DL2 AE  |   x                 |       c2            |     | 2ae |     |     |     |     |     |     |     | 2ea |
DL2 BC  |   c1                |         c1          |     |     | 2bc |     | 1cb |     |     |     |     |     |
DL2 BD  |   c1                |           c1        |     |     | 2bd |     |     |     | 1db |     |     |     |
DL2 BE  |   x                 |             c2      |     |     |     | 2be |     |     |     |     | 2eb |     |
DL2 CD  |   x                 |               c2    |     |     |     |     | 2cd |     | 2dc |     |     |     |
DL2 CE  |   x                 |                 c2  |     |     |     |     |     | 2ce |     |     | 2ec |     |
DL2 DE  |   x                 |                   c2|     |     |     |     |     |     |     | 2de |     | 2ed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
DL3 AB  |     c1              | x                   |     | 1ab |     | 1ba |     |     |     |     |     |     |
DL3 AC  |     c2              |   c2                |     | xac |     |     |     | 2ca |     |     |     |     |
DL3 AD  |     c1              |     c1              | xad |     |     |     |     |     |     | 1da |     |     |
DL3 AE  |     c1              |       c1            | xae |     |     |     |     |     |     |     |     | 1ea |
DL3 BC  |     c3              |         c3          |     |     |     | xbc |     | 3cb |     |     |     |     |
DL3 BD  |     c1              |           c1        |     |     | xbd |     |     |     |     | 1db |     |     |
DL3 BE  |     c1              |             c1      |     |     | xbe |     |     |     |     |     |     | 1eb |
DL3 CD  |     c3              |               c3    |     |     |     |     | 3cd |     | xdc |     |     |     |
DL3 CE  |     x               |                 c4  |     |     |     |     | 4ce |     |     |     | 4ec |     |
DL3 DE  |     c3              |                   c3|     |     |     |     |     |     | 4de |     | 3ed |     |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
DL4 AB  |       c1            | x                   | 1ab |     | 1ba |     |     |     |     |     |     |     |
DL4 AC  |       c2            |   c2                |     | xac |     |     | 2ca |     |     |     |     |     |
DL4 AD  |       c2            |     c2              |     | xad |     |     |     |     | 2da |     |     |     |
DL4 AE  |       c1            |       c1            | xae |     |     |     |     |     |     |     | 1ea |     |
DL4 BC  |       c3            |         c3          |     |     |     | xbc |     | 3cb |     |     |     |     |
DL4 BD  |       c3            |           x         |     |     |     | 3bd |     |     |     | 3db |     |     |
DL4 BE  |       c1            |             c1      |     |     | xbe |     |     |     |     |     |     | 1eb |
DL4 CD  |       x             |               x     |     |     |     |     |     | xcd |     | xdc |     |     |
DL4 CE  |       c2            |                 c2  |     |     |     |     | 2ce |     |     |     |     | xec |
DL4 DE  |       c3            |                   c3|     |     |     |     |     |     | xde |     | 3ed |     |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
DL5 AB  |         c1          | x                   | 1ab |     | 1ba |     |     |     |     |     |     |     |
DL5 AC  |         c1          |   c1                | xac |     |     |     | 1ca |     |     |     |     |     |
DL5 AD  |         c2          |     c2              |     | xad |     |     |     |     | 2da |     |     |     |
DL5 AE  |         c2          |       x             |     | 2ae |     |     |     |     |     |     | 2ea |     |
DL5 BC  |         c1          |         c1          |     |     | xbc |     | 1cb |     |     |     |     |     |
DL5 BD  |         x           |           c3        |     |     |     | 3bd |     |     | 3db |     |     |     |
DL5 BE  |         x           |             c3      |     |     |     | 3be |     |     |     |     | 3eb |     |
DL5 CD  |         x           |               c3    |     |     |     |     |     | 3cd |     | 3dc |     |     |
DL5 CE  |         c2          |                 c2  |     |     |     |     |     | 2ce |     |     |     | 3ec |
DL5 DE  |         c2          |                   c2|     |     |     |     |     |     |     | 2de |     | 3ed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BL1 AB  |           c1        | x                   |     | 1ab |     | 1ba |     |     |     |     |     |     |
BL1 AC  |           c1        |   c1                | xac |     |     |     |     | 1ca |     |     |     |     |
BL1 AD  |           c1        |     c1              | xad |     |     |     |     |     |     | 1da |     |     |
BL1 AE  |           c2        |       x             |     | 2ae |     |     |     |     |     |     |     | 2ea |
BL1 BC  |           c1        |         c1          |     |     | xbc |     | 1cb |     |     |     |     |     |
BL1 BD  |           c1        |           c1        |     |     | xbd |     |     |     | 1db |     |     |     |
BL1 BE  |           c3        |             c3      |     |     |     | xbe |     |     |     |     | 3eb |     |
BL1 CD  |           c3        |               c3    |     |     |     |     | 3cd |     | xdc |     |     |     |
BL1 CE  |           c4        |                 x   |     |     |     |     |     | 4ce |     |     | 4ec |     |
BL1 DE  |           c2        |                   c2|     |     |     |     |     |     |     | 2de |     | xed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BL2 AB  |             c1      | x                   |     | 1ab |     | 1ba |     |     |     |     |     |     |
BL2 AC  |             c2      |   c2                |     | xac |     |     |     | 2ca |     |     |     |     |
BL2 AD  |             c1      |     c1              | xad |     |     |     |     |     |     | 1da |     |     |
BL2 AE  |             c1      |       c1            | xae |     |     |     |     |     |     |     |     | 1ea |
BL2 BC  |             c3      |         c3          |     |     |     | xbc |     | 3cb |     |     |     |     |
BL2 BD  |             c1      |           c1        |     |     | xbd |     |     |     |     | 1db |     |     |
BL2 BE  |             c1      |             c1      |     |     | xbe |     |     |     |     |     |     | 1eb |
BL2 CD  |             c3      |               c3    |     |     |     |     | 3cd |     | xdc |     |     |     |
BL2 CE  |             c4      |                 x   |     |     |     |     | 4ce |     |     |     | 4ec |     |
BL2 DE  |             c3      |                   c3|     |     |     |     |     |     | 4de |     | 3ed |     |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BL3 AB  |               c1    | x                   | 1ab |     | 1ba |     |     |     |     |     |     |     |
BL3 AC  |               c2    |   c2                |     | xac |     |     | 2ca |     |     |     |     |     |
BL3 AD  |               c2    |     c2              |     | xad |     |     |     |     | 2da |     |     |     |
BL3 AE  |               c1    |       c1            | xae |     |     |     |     |     |     |     | 1ea |     |
BL3 BC  |               c3    |         c3          |     |     |     | xbc |     | 3cb |     |     |     |     |
BL3 BD  |               c3    |           x         |     |     |     | 3bd |     |     |     | 3db |     |     |
BL3 BE  |               c1    |             c1      |     |     | xbe |     |     |     |     |     |     | 1eb |
BL3 CD  |               x     |               x     |     |     |     |     |     | xcd |     | xdc |     |     |
BL3 CE  |               c2    |                 c2  |     |     |     |     | 2ce |     |     |     |     | xec |
BL3 DE  |               c3    |                   c3|     |     |     |     |     |     | xde |     | 3ed |     |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BL4 AB  |                 c1  | x                   | 1ab |     | 1ba |     |     |     |     |     |     |     |
BL4 AC  |                 c1  |   c1                | xac |     |     |     | 1ca |     |     |     |     |     |
BL4 AD  |                 c2  |     c2              |     | xad |     |     |     |     | 2da |     |     |     |
BL4 AE  |                 c2  |       x             |     | 2ae |     |     |     |     |     |     | 2ea |     |
BL4 BC  |                 c1  |         c1          |     |     | xbc |     | 1cb |     |     |     |     |     |
BL4 BD  |                 c3  |           x         |     |     |     | 3bd |     |     | 3db |     |     |     |
BL4 BE  |                 c3  |             c3      |     |     |     | xbe |     |     |     |     | 3eb |     |
BL4 CD  |                 x   |               x     |     |     |     |     |     | xcd |     | xdc |     |     |
BL4 CE  |                 c2  |                 c2  |     |     |     |     |     | 2ce |     |     |     | xec |
BL4 DE  |                 c2  |                   c2|     |     |     |     |     |     |     | 2de |     | xed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BL5 AB  |                   c1| x                   |     | 1ab |     | 1ba |     |     |     |     |     |     |
BL5 AC  |                   c1|   c1                | xac |     |     |     |     | 1ca |     |     |     |     |
BL5 AD  |                   c1|     c1              | xad |     |     |     |     |     |     | 1da |     |     |
BL5 AE  |                   c2|       x             |     | 2ae |     |     |     |     |     |     |     | 2ea |
BL5 BC  |                   c1|         c1          |     |     | xbc |     | 1cb |     |     |     |     |     |
BL5 BD  |                   c1|           c1        |     |     | xbd |     |     |     | 1db |     |     |     |
BL5 BE  |                   c3|             c3      |     |     |     | xbe |     |     |     |     | 3eb |     |
BL5 CD  |                   c3|               c3    |     |     |     |     | 3cd |     | xdc |     |     |     |
BL5 CE  |                   c4|                 x   |     |     |     |     |     | 4ce |     |     | 4ec |     |
BL5 DE  |                   c2|                   c2|     |     |     |     |     |     |     | 2de |     | 4ed |
--------+---------------------+---------------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 12, 2011 7:56 am

.
Hi Simon,

will be brief.

9 agents with BSCs was as I expected.

I liked the tree. Very good visual representation although would be hard to draw the extra links.

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?

Later
.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby dyitto » Sat Feb 12, 2011 8:15 am

I've calculated the number of different solutions for BSCs (3 links each) and 8 agents.
That is, with the SCs individually numbered and without normalizing for isomorphy.

The result is 5880.

Unfortunately I can't check this with pen and paper :mrgreen: . Could you confirm this number?
That would ensure that the method gives correct results.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 12, 2011 9:10 am

.
Hi dyitto,

I can't confirm the number because i am no closer to a method for solving.

What is the method you use?
.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby dyitto » Sat Feb 12, 2011 9:29 am

Code: Select all
procedure TGraph.SCConnect(a, b: integer);
begin
  OneWayConnected[a,b] := true;
  OneWayConnected[b,a] := true;
end;

procedure TGraph.SCDisconnect(a, b: integer);
begin
  OneWayConnected[a,b] := false;
  OneWayConnected[b,a] := false;
end;

procedure TGraph.SCGenerate_All(start_n1, start_n2: integer; AllSolutions: boolean);
  var n1, n2, i: integer;
begin
  Application.ProcessMessages;
  ComputeRouteDistances;

  if MaxRouteDistance <= 2 then
  begin
    hlpStringList.Clear;
    PlaceIntoStringList(hlpStringList);
    for i := 0 to hlpStringList.Count - 1 do
           LogStringList.Add(hlpStringList.Strings[i]);

    SCSolutionCount := SCSolutionCount + 1;
    SCSolution := OneWayConnected;
    //LogStringList.Add('maxd2');
    LogStringList.Add('');
    LogStringList.Add('');
  end;

  for n1 := 1 to NodeCount - 1 do
    for n2 := n1 + 1 to NodeCount do
      if (n1 > start_n1) or ((n1 = start_n1) and (n2 > start_n2)) then
        if SCLinkCount[n1] < SCMaxLink then
          if SCLinkCount[n2] < SCMaxLink then
            if n1 <> n2 then
              if OneWayConnected[n1,n2] = false then
              begin
                SCConnect(n1,n2);
                SCLinkCount[n1] := SCLinkCount[n1] + 1;
                SCLinkCount[n2] := SCLinkCount[n2] + 1;
                if (SCSolutionCount < 1) or AllSolutions then
                               SCGenerate_All(n1,n2,AllSolutions);
                SCLinkCount[n2] := SCLinkCount[n2] - 1;
                SCLinkCount[n1] := SCLinkCount[n1] - 1;
                SCDisConnect(n1,n2);
              end;
end;

procedure TGraph.SCProblem_Init;
  var n: integer;
begin
  self.Init_OneWayConnected;
  for n := 1 to NodeCount do SCLinkCount[n] := 0;
  SCSolutionCount := 0;
  self.LogStringList.Clear;
end;

procedure TGraph.SCProblem(RequestedNodeCount, RequestedMaxLink: integer; AllSolutions: boolean);
begin
  ShowMessage('SCProblem started ' +
               IntToStr(RequestedNodeCount) +
               ' nodes ' +
               IntToStr(RequestedMaxLink) +
               ' edges per node'
             );
  self.NodeCount := RequestedNodeCount;
  SCMaxLink := RequestedMaxLink;
  SCProblem_Init;
  SCGenerate_All(1,1, AllSolutions);

  OneWayConnected := SCSolution;
  self.GraphModifiedActions;

  LogStringList.SaveToFile('SCSolution.txt');

  ShowMessage('SCProblem finished ' +
               IntToStr(RequestedNodeCount) +
               ' nodes ' +
               IntToStr(RequestedMaxLink) +
               ' edges per node ' +
               IntToStr(SCSolutionCount) +
               ' solutions.'
             );
end;
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 12, 2011 10:21 am

.
Ah we speak the same language.

Beauty for my eyes to see. :D

You will probably get there before me. I won't go over your code, but have you started with the simplest cases and confirmed the numbers?

I can see we are going to need a method to sort through all the isomorphs. I noticed even with my incorrect results the numbers blew up really quickly. Do you think re-labeling will be enough?

It is probable that for most arrangements there will be only one - so many are symmetric - what term to use - perhaps not most canonical...
.
BryanL
 
Posts: 247
Joined: 28 September 2010

PreviousNext

Return to Inventors' studio