superprismatic 11 Report post Posted November 13, 2012 A Boggle-like Challenge In the game, Boggle, a letter may have at most 8 adjacent letters. That fact inspired this challenge. This first part of this challenge is to place letters in such a way that each letter of the alphabet has precisely eight other different letters adjacent to it. You must use all 26 letters and, of course, "adjacent" is a commutative relation. To specify your placement, all you need to do is list the eight letters adjacent to A, the eight letters adjacent to B, the eight letters adjacent to C,...,etc. But remember that, if Q is on A's adjacency list, then A must be on Q's adjacency list, and this is true for every pair of letters -- not just A and Q. The second part of the challenge is to create a cycle of all 26 letters, such that each adjacent pair of letters in the cycle are adjacent in the sense of the first part of the challenge. Note that there is no requirement that the graph of adjacent letters is realizable in a small number of dimensions. So, trying to visualize such a graph may be hazardous to your mental health! Quote Share this post Link to post Share on other sites
0 BobbyGo 7 Report post Posted November 13, 2012 Can the letters be used more than once? If so, are the number of adjacent letters accumulative? (Would the conditions be meet if the first 'A' has 6 adjacent letters and the second 'A' has 2?) Does the arrangement need to be on a straight plane or can it be on a sperical one? (Could A be next to B and C in the same way that Indiana is next to Kentucky and Illinois?) Quote Share this post Link to post Share on other sites
0 superprismatic 11 Report post Posted November 13, 2012 Can the letters be used more than once? If so, are the number of adjacent letters accumulative? (Would the conditions be meet if the first 'A' has 6 adjacent letters and the second 'A' has 2?) Does the arrangement need to be on a straight plane or can it be on a sperical one? (Could A be next to B and C in the same way that Indiana is next to Kentucky and Illinois?) There is only one A which has eight neighbours. There is only one of each of the 26 letters from A to Z, and each letter has to be connected (adjacent) to exactly 8 others. The arrangement can be on any manifold with any number of dimensions -- Whence my last paragraph. All that is required is that each of the 26 letters is adjacent to 8 others and "adjacency" is commutative. How this plays out in your head is of no concern. I hope this clarifies things. Quote Share this post Link to post Share on other sites
0 CaptainEd 26 Report post Posted November 13, 2012 I think I just learned something from this clarification. In Boggle, the tableau ABC DEF GHI has E adjacent to each of the others, and each of the others adjacent to two others, arranged in a ring. But I believe you are willing to relax the ring requirement on the neighbors of E; your only requirement is that AE <-> EA. All that is required is the graph. Thanks! (Another interesting puzzle from superprismatic!) Quote Share this post Link to post Share on other sites
0 TheChad08 14 Report post Posted November 14, 2012 (edited) Seems as though there is a near infinite amount of answers. EDIT: Nevermind, did it in a less graphical way Edited November 14, 2012 by TheChad08 Quote Share this post Link to post Share on other sites
0 curr3nt 23 Report post Posted November 14, 2012 A : BDFHZXVT B : CEGIAYWU C : DFHJBZXV D : EGIKCAYW E : FHJLDBZX F : GIKMECAY G : HJLNFDBZ H : IKMOGECA I : JLNPHFDB J : KMOQIGEC K : LNPRJHFD L : MOQSKIGE M : NPRTLJHF N : OQSUMKIG O : PRTVNLJH P : QSUWOMKI Q : RTVXPNLJ R : SUWYQOMK S : TVXZRPNL T : UWYASQOM U : VXZBTRPN V : WYACUSQO W : XZBDVTRP X : YACEWUSQ Y : ZBDFXVTR Z : ACEGYWUS Quote Share this post Link to post Share on other sites
0 curr3nt 23 Report post Posted November 14, 2012 How would this be difficult to make with rings too? Make a 3x3x3 cube and exclude the center piece. There are your 26 pieces for each letter. The center and edge pieces will have 8 neighbors while the corners will have 6. So pretend that the corners are connected to two other corners. I can't upload the picture I have showing this... Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted November 14, 2012 (edited) W X Y Z Q A B C D V E F G H I J E K L M N O P K Q R S T U V Q E W X Y Z J A B C D where there are duplicate letters, they are actually the same letter, just there to help you understand connections. and here is the original pic. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Edited November 14, 2012 by phil1882 Quote Share this post Link to post Share on other sites
0 curr3nt 23 Report post Posted November 14, 2012 (edited) A cube example... .......MLK .......VWX .......SRQ .......SRQ .......TUP .......IBC ..STI IBC CPQ ..VYH HAD DZX ..MNG GFE EJK .......GFE .......NOJ .......MLK Where the corners connect at... C -> MS E -> MS G -> KQ I -> KQ K -> GI M -> CE Q -> GI S -> CE Edited November 14, 2012 by curr3nt Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted November 14, 2012 edit of above: still not quite right. Z Y X W V A B C D Q E F G H I J K L M N O P K Q R S T U V J W X Y Z E D C B A Quote Share this post Link to post Share on other sites
0 brifri238 0 Report post Posted November 16, 2012 (edited) Letter1 Adjacent Letters ===== ============= A B,C,D,E,F,G,O,V B A,C,D,E,F,G,P,V C A,B,D,E,F,G,Q,W D A,B,C,E,F,G,R,W E A,B,C,D,F,G,S,X F A,B,C,D,E,G,T,X G A,B,C,D,E,F,N,U H I,J,K,L,M,N,V,Y I H,J,K,L,M,N,V,Y J H,I,K,L,M,N,W,Z K H,I,J,L,M,N,W,Z L H,I,J,K,M,N,S,X M H,I,J,K,L,N,T,X N G,H,I,J,K,L,M,U O A,P,Q,R,S,T,U,Y P B,O,Q,R,S,T,U,Y Q C,O,P,R,S,T,U,Z R D,O,P,Q,S,T,U,Z S E,L,O,P,Q,R,T,U T F,M,O,P,Q,R,S,U U G,N,O,P,Q,R,S,T V A,B,H,I,W,X,Y,Z W C,D,J,K,V,X,Y,Z X E,F,L,M,V,W,Y,Z Y H,I,O,P,V,W,X,Z Z J,K,Q,R,V,W,X,Y Edited November 16, 2012 by brifri238 Quote Share this post Link to post Share on other sites
0 superprismatic 11 Report post Posted November 16, 2012 Curr3nt and brifri238 both found good adjacency hookups. I think phil1882 got into a bit of trouble trying to keep the dimension down to two or three. Also, curr3nt's solution makes for an easy second part solution. I had hoped that someone would go a bit further and hint at some algorithm for generating these things. I know of no way to generate a random one -- i.e. an algorithm which can choose one with probability 1/N where N is the total number of possible adjacencies. I don't even know how to find N. Thanks for working on it. Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted November 17, 2012 26!/(6*8) = N, i would think. as to how to generate all of them evenly, no idea. Quote Share this post Link to post Share on other sites
0 EventHorizon 13 Report post Posted November 18, 2012 26!/(6*8) = N, i would think. as to how to generate all of them evenly, no idea. N is not going to be that simple to calculate. Any given adjacency you find could have multiple possible cycles that could be found within it (So it may incorrectly be counted multiple times). Adjacencies don't need to be as neatly organized as curr3nt's answer was. Choose a random ordering with a as the first letter (since there's going to be a cycle anyway). There are 25! of them. Since the graph is commutative the cycle can go in either direction. 25!/2. For the rest of the adjacencies, pick 3 numbers between 2 and 12 inclusive for the amount to jump with respect to the cycle (one forward that many steps and one back that many steps for each number picked (to preserve commutativity)). (25!/2) * (12 choose 3) = (25! * 110) Since each of these has a cycle right in the middle of the others and very neatly ordered, these are not repeated in the count (I think...). So N > 25! * 110. Each adjacency list can be treated as 26*8/2 = 104 1's in a lower triangular 26x26 matrix. This means N must be less than (26*(26-1))/2 choose 104 = 1.43e87. We can easily limit this a little by enforcing exactly 8 x's in the first column. (25 choose 8) * (25*(25-1)/2 choose 96) = (25 choose 8) * (300 choose 96) = 1081575 * 2.33e80 = 2.52e86 So a crude range for N is... 25! * 110 = 1.706e27 < N < 2.52e86 = (25 choose 8) * (300 choose 96). A slightly smaller upper bound would be found noticing that after the first 8 are chosen from the first column, there is still an xth letter without any adjacencies set so far. If you then choose 8 for it's adjacencies, it leaves another in the same situation. And once more for the last time you can be sure (since 25-8-8-8=1). (Edit: Forgot to include the letter itself, so only 3 times...) N < (25 choose 8) * (24 choose 8) * (23 choose 8) * (22 choose 8) * ((22*(22-1)/2) choose (104-32)) N < 1081575 * 753471 * 490314 * 319770 * (231 choose 72) N < 1081575 * 753471 * 490314 * 319770 * 9.933e60 N < 1.27e84 If you assume you'll always have 8 more to choose for each letter (an overestimation) you can get the following... N < Product of i=8 to 25 of (i choose 8) = 25! * 24! * 23! * 22! * 21! * 20! * 19! * 18! / (8!^{18} * 7! * 6! * 5! * 4! * 3! * 2!) = 2.72e69 1.706e27 < N < 2.72e69 Yeah, still a huge range... 1. Randomly pick 8 letters to be adjacent to each letter. 2. Check for commutativity. If not, redo step 1. 3. Check that a cycle of all 26 letters exists. If not, redo step 1. Now, someone find a way without a large amount of resampling... :-/ Quote Share this post Link to post Share on other sites
0 curr3nt 23 Report post Posted November 19, 2012 Other than the organized adjacencies? Is there an arrangement the "cube" can't cover? Took me a bit to figure out what phil did. He took all the possibilities and divided by all the orientations of the "cube". 6 faces * 4 rotations * 2 for mirroring. I think this leaves out a shifting position divisor. Can you take a cube arrangement and shift a letter from a center position to an adjacent square and retain adjacencies for all the letters? If so then how many shifts? Off the hip guess would be 3 unless which diagonal set is being shifted into matters. (Center, center edge and diagonal) So N ?= 26!/(6*4*2*3) for unique possibilities? I can't think of another way to alter the cube that would retain adjacencies but wouldn't be part of the (6*4*2*3). Quote Share this post Link to post Share on other sites
0 EventHorizon 13 Report post Posted November 19, 2012 Other than the organized adjacencies? Is there an arrangement the "cube" can't cover? Took me a bit to figure out what phil did. He took all the possibilities and divided by all the orientations of the "cube". 6 faces * 4 rotations * 2 for mirroring. I think this leaves out a shifting position divisor. Can you take a cube arrangement and shift a letter from a center position to an adjacent square and retain adjacencies for all the letters? If so then how many shifts? Off the hip guess would be 3 unless which diagonal set is being shifted into matters. (Center, center edge and diagonal) So N ?= 26!/(6*4*2*3) for unique possibilities? I can't think of another way to alter the cube that would retain adjacencies but wouldn't be part of the (6*4*2*3). a - cdefghij b - cdefghik c - abdefghi d - abcefghi e - abcdfghi f - abcdeghi g - abcdefhi h - abcdefgi i - abcdefgh j - almnzyxw k - lmnobzyx l - mnopkjzy m - nopqlkjz n - opqrmlkj o - pqrsnmlk p - qrstonml q - rstuponm r - stuvqpon s - tuvwrqpo t - uvwxsrqp u - vwxytsrq v - wxyzutsr w - xyzjvuts x - yzjkwvut y - zjklxwvu z - jklmyxwv Example cycle: acdefghibklmnopqrstuvwxyzj Description of above: a through i are all connected to each other, except a is not adjacent to b. Instead of a adjacent to b, a is connected to j and b is connected to k. j through z are in a loop and are adjacent to the ones 4 in front and 4 behind themselves, except j is not adjacent to k to allow the connections to a and b. This means that any cycle found must include "ja" followed by any combination of c through i followed by "bk", or that but reversed. The cube model has no way to represent that the cycle is required to use the connections "aj" and "bk". The cube also cannot have 9 letters all adjacent to each other (except for the 1 missing connection "ab" to allow for a cycle). Quote Share this post Link to post Share on other sites
0 superprismatic 11 Report post Posted November 19, 2012 Perhaps going down to a smaller alphabet will help shed light on this problem. I wrote a little program to generate all possible ways of making adjacencies on an alphabet of size 8 with each letter having 3 adjacencies. The number of these I got was 19,355. Quote Share this post Link to post Share on other sites
0 EventHorizon 13 Report post Posted November 20, 2012 Yay for integer sequences (found using your 19355 )... A002829 - Number of trivalent (or cubic) labeled graphs with 2n nodes. 1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750, 62870315446244013091262178375075 A004109 - Number of connected trivalent (or cubic) labeled graphs with 2n nodes. 0, 1, 70, 19320, 11166120, 11543439600, 19491385914000, 50233275604512000, 187663723374359232000, 975937986889287117696000, 6838461558851342749449120000, 62856853767402275979616458240000 A014378 - Number of connected regular graphs of degree 8 with n nodes. 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 6, 94, 10786, 3459386, 1470293676, 733351105935 If someone can prove that being connected is sufficient to be able to create the cycle with 8-regular graphs, the last integer sequence would contain N... if it went further than 16 nodes/letters... The factor from one number to the next is: 6 15.6666666 114.7446 320.729 425.015790663 498.778657561 Assuming 500 for each additional letter added beyond 16 gives the estimate of 733351105935 * 500^{10} = 7.161631894e38 And this should be underestimating it. For overestimating, we can assume the factor will increase by at least 75 for each letter added (it's clearly increasing at a decreasing rate): 733351105935*575*650*725*800*875*950*1025*1100*1175*1250 = 2.188352274e41 That's a much smaller range than before, but it does require the connected=cycle assumption. The upper bound is still an upper bound without the assumption since you definitely need the graph connected for a cycle to exist. Ooops. Just noticed that the list is unlabeled nodes, so the number is actually larger. Set one random edge. There needs to be one, so start anywhere. Choose one of the nodes attached to this edge. It cannot connect back to the first again with its other edge, so it connects to a third node. This third node cannot be connected to the previous node with both its edges. If there are more nodes, it cannot attach to the other node from the first edge, as it would mean the graph is not connected. Proceed this way until all nodes have been added, and the last node connects to the other node from the first edge to finish one big loop. Since the graph is simply one big loop, there is a cycle. Time to look at 3-regular graphs... which aren't as simple and quite possibly don't have this property. Almost all regular graphs are hamiltonian. Abstract: In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ⩾ 3. So it looks like we basically just need to find how many 8-regular graphs there are with 26 labeled vertices. It'll be off by a little, but will be a good estimate for N. Quote Share this post Link to post Share on other sites
0 curr3nt 23 Report post Posted November 20, 2012 a - cdefghij b - cdefghik c - abdefghi d - abcefghi e - abcdfghi f - abcdeghi g - abcdefhi h - abcdefgi i - abcdefgh j - almnzyxw k - lmnobzyx l - mnopkjzy m - nopqlkjz n - opqrmlkj o - pqrsnmlk p - qrstonml q - rstuponm r - stuvqpon s - tuvwrqpo t - uvwxsrqp u - vwxytsrq v - wxyzutsr w - xyzjvuts x - yzjkwvut y - zjklxwvu z - jklmyxwv Example cycle: acdefghibklmnopqrstuvwxyzj Description of above: a through i are all connected to each other, except a is not adjacent to b. Instead of a adjacent to b, a is connected to j and b is connected to k. j through z are in a loop and are adjacent to the ones 4 in front and 4 behind themselves, except j is not adjacent to k to allow the connections to a and b. This means that any cycle found must include "ja" followed by any combination of c through i followed by "bk", or that but reversed. The cube model has no way to represent that the cycle is required to use the connections "aj" and "bk". The cube also cannot have 9 letters all adjacent to each other (except for the 1 missing connection "ab" to allow for a cycle). c - abdefghi d - abcefghi bummer... Quote Share this post Link to post Share on other sites
A Boggle-like Challenge
In the game, Boggle, a letter may have at most 8 adjacent letters.
That fact inspired this challenge.
This first part of this challenge is to place letters in such a way
that each letter of the alphabet has precisely eight other different
letters adjacent to it. You must use all 26 letters and, of course,
"adjacent" is a commutative relation. To specify your placement,
all you need to do is list the eight letters adjacent to A, the
eight letters adjacent to B, the eight letters adjacent to C,...,etc.
But remember that, if Q is on A's adjacency list, then A must be
on Q's adjacency list, and this is true for every pair of letters
-- not just A and Q.
The second part of the challenge is to create a cycle of all 26
letters, such that each adjacent pair of letters in the cycle are
adjacent in the sense of the first part of the challenge.
Note that there is no requirement that the graph of adjacent letters
is realizable in a small number of dimensions. So, trying to visualize
such a graph may be hazardous to your mental health!
Share this post
Link to post
Share on other sites