SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 9:05 am

All times are UTC




Post new topic Reply to topic  [ 13 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Tue Feb 22, 2011 7:29 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Here is a quick 17 RSCs scenario using the "3-level tree" 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:
      _____________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:
   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.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 22, 2011 7:31 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Here is 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:
   _________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:
   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 an alternative 18 RSCs scenario, which does not use the tree structure.

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. :-(


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 22, 2011 7:34 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Here is an 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:
   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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ]  Go to page Previous  1, 2

All times are UTC


Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group