A Boggle-like Challenge

[superprismatic]

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!

[BobbyGo]

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?)

[superprismatic]

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.

[CaptainEd]

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!)

[TheChad08]

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

[curr3nt]

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

[curr3nt]

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

[phil1882]

  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

[curr3nt]

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

[phil1882]

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

[brifri238]

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

[superprismatic]

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.

[phil1882]

26!/(6*8) = N, i would think.

as to how to generate all of them evenly, no idea.

[EventHorizon]

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!¹⁸ * 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... :-/

[curr3nt]

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).

[EventHorizon]

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).

[superprismatic]

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.

[EventHorizon]

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¹⁰ = 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.

[curr3nt]

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