I have been thinking about writing a program that fills a 4x4x4 cubical
box of cells, each cell with a single digit (0 to 9), such that all of
the integers can be found by stepping from one cell to a neighboring
cell. Neighboring cells share a face, edge, or vertex. One way to do
this would be by ensuring that each occupied cell has neighboring cells
with every digit 0 to 9. Since at least 10 neighboring cells would be
required to handle all digit sequences, the eight corner-cells would be
of little use, since they only have seven neighbors. My plan was to
leave corner-cells unoccupied. Edge-cells are part of a 2x2x3 sub-box,
so there would be just enough neighbors (11, or only 10 if the sub-box
has an unoccupied corner-cell within it). Mid-face and interior cells
have even more neighbors.

Putting every integer into a such a small "Universal Integer Box" would
be gratifying.

Is this "Universal Integer Box" even possible?

What's an efficient algorithm for filling the box, or for proving that
it's impossible? A brute-force algorithm that checks all 10^56
possibilities in beyond the capability of my current computer ;).

If a 4x4x4 box wouldn't work, what about a larger box?

Can a smaller box work (e.g., 3x4x4)?

--
Carl G.

--
This email has been checked for viruses by AVG antivirus software.
www.avg.com

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

For your reference, records indicate that
"Carl G." <carlgnews@microprizes.com> wrote:

I have been thinking about writing a program that fills a 4x4x4 cubical
box of cells, each cell with a single digit (0 to 9), such that all of
the integers can be found by stepping from one cell to a neighboring
cell. Neighboring cells share a face, edge, or vertex. One way to do
this would be by ensuring that each occupied cell has neighboring cells
with every digit 0 to 9. Since at least 10 neighboring cells would be required to handle all digit sequences, the eight corner-cells would be
of little use, since they only have seven neighbors. My plan was to
leave corner-cells unoccupied. Edge-cells are part of a 2x2x3 sub-box,
so there would be just enough neighbors (11, or only 10 if the sub-box
has an unoccupied corner-cell within it). Mid-face and interior cells
have even more neighbors.

Putting every integer into a such a small "Universal Integer Box" would
be gratifying.

Is this "Universal Integer Box" even possible?

I’m not sure there’s even much *puzzle* to it that you haven’t already worked out yourself. So long as you have a graph with at least 11 nodes
that each have connections to 10 other nodes, it doesn’t matter where the digits go. Having more connections than that doesn’t matter, either,
because you always need to connect to a node with at least 10 connections itself.

By your own observations, 4x4x4 = 64 - 8 corners = 56. Far in excess of
the required 11. Heck, it seems like it should be able to contain 5 independent UIBs! Not sure how the layout(s) for that would look . . .

What's an efficient algorithm for filling the box,

It’s essentially fill-as-you-go. For any requested digit, check your connections to see if it is already filled in the graph. If so, move to
that node. If not, move to an empty node and fill it with the requested
digit.

Can a smaller box work (e.g., 3x4x4)?

It is interesting to note that 3x3x3 = 27 - 8 = 19 > 11. BUT! For any
side with a length of 3, your edge cells actually lose *2* corner neighbors,
so they are rendered unusable. It seems to go from trivial to impossible at that boundary.

--
"Also . . . I can kill you with my brain."
River Tam, Trash, Firefly

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)