Post by Carl G.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.
Carl,
A 4x4x4 box will not work.
Nomenclature
The 56 cube locations have three different designations.
There are 24 locations on 12 edges. These are referred to as ELs. ELs are further classified into 12 pairs by edge. There are 24 locations on the 12 faces. These are referred to as FLs. The FLs are further classified into six groups of four and within those four by whether they are diagonally across for each other on a face or not. There are four core locations referred to as CLs. We refer to four types of touching between two locations – vertex touching (VT), edge touching (ET), face touching (FT) and not touching (NT) – with the designation determined by the largest contact.
An “x” is used to designate a permanently unfilled corner. A ‘u’ is used to designate a currently unfilled or unimportant location for the discussion in progress. Lower case letters are used to define general relationships of unknown values in examples. The cube is presented as four 2-D layers. A sample of two layers is given below. Elements within layers are referred to by EL, FL and CL with further distinction by the Row and Column numbers from 1 to 4 or their value as needed.
Layer 1
x 0 0 x
1 4 5 u
1 u b u
x u u x
Layer 2
2 8 9 u
3 6 7 3
u u c u
u 8 9 u
Observation 1: The ELs cannot touch two of the same number. They only touch ten numbers so all the locations are needed.
Lemma 1: The only place an EL can have its repeated number is in its paired FT EL. That is, the one where the two share a full face. All other locations would create a violation of Ob1 for some other EL. Proof by enumerative checking for one EL and symmetry.
Observation 2: Lemma 1 means that the 24 edge locations are filled with twelve pairs of numbers.
Lemma 2: FLs have to have their repeated digit located either in the diagonal location on the same face (an ET FL) or in the location next to that diagonal toward the center, that is, its VT CL. Proof by enumeration and checking for violations of Ob1, and symmetry.
For example, the only options for placing a second 4 to touch the one in the FL in the Layer 1 shown below are the locations with an ‘a’ or a ‘b’.
Layer
x 0 0 x 0:1
1 4 5 u 2:5
1 u a u 6:9
x u u x 10:11
Layer 2
2 8 9 u 12:15
3 6 7 3 16:19
u u b u 20:23
u 8 9 u 24:27
Lemma 3. If an EL touching a specific FL along a face has its full complement of digits and the FT FL has had a repeat of its digit placed according to Lemma 2, then the FT FL has its full complement of digits. Proof by examination – The FT FL shares all the digits touching the EL. These include all nine except the FL’s own digit.
Lemma 4. If an EL touching a specific CL along an edge has its full complement of digits and the ET CL has had a repeat of its digit placed somewhere, then the FT CL has its full complement of digits. Proof by examination – The FT CL shares all the digits touching the EL. These include all nine except the CL’s own digit. (Note, CLs have seven locations for possible placement of the repeated digit.)
Corollary 1. Paired ELs have two sets of three locations (each consisting of a FL and two ELs) that are not shared. The three values for these must be permutations of each other.
Lemma 5. The values for FLs are paired with FLs on the opposite face. For example, specifying the FLs on Layer 1 also specifies them on Layer 4.
Layer 1
x u u x
u a b u
u c d u
x u u x
Layer 4
x u u x
u a b u
u c d u
u u u u
Proof by contradiction, example and symmetry. If an EL in one set in Corollary 1 equals the FL for the other set, then there is another EL which cannot complete its complement. In this example “a” is the FL value, and b’s and the ‘d’ are 'not a' values as required by Obs1, and ‘c’ is the 'not a’ EV that cannot have an ‘a’ touching it. (Note 1: c equals d. Note 2.
Layer 1
x b b x
b b b b
b b u u
x u u x
Layer 2
b b b a
a b b b
u u u u
u u u u
Layer 3
b b b a
b b b b
u u u u
Layer 4
x c d x
b b b b
u u u u
x u u x
Arrangement 1 (Arr1): We begin by placing a number in an EL and then filling the FT EL with the same number and then placing the other nine numbers in its other nine touching locations. Two of these are ELs so we fill / designate their FT ELs per Lemma 1 and five of them are FLs so we fill / designate their opposite FLs per Lemma 5 for a total of 18 of the 64 spaces as follows. An “x” is for permanently empty corner location and a “u” is for a location with a currently unknown. The cube is specified by four 4x4 layers from top to bottom.
Layer 1
x 0 0 x
1 4 5 u
1 u u u
x u u x
Layer 2
2 8 9 u
3 6 7 3
u u u u
u 8 9 u
Layer 3
2 u u u
u u u u
u u u u
Layer 4
x 4 5 x
u u u u
u u u u
x u u x
Observation 3: All solutions are equivalent to this general class of solutions with some permutation of the ten digits.
Going forward we will concentrate first on trying to fill Layers 1 & 2 so that all the locations in Layer 1 have their full complement of touching values. We will stop showing Layers 3 & 4 even if some more of their values have become specified by Lemma 1 or Lemma 5 or could be limited by using Lemma 2.
Observation 4. The second EL 0 in Arr1 has two undetermined adjacent values. These must take on the values of {1,2} to complete its complement of digits. We create two duplicates of Arr1 with the possible filling sequences in the two locations to create Arrangement 2.
Observation 5: By Lemma 2, the 4 and 5 in Arr1 have to have their repeated digit located in one of two places and those are either in Layer 1 or Layer 2. For example, the options for placing a second 5 to touch the in an Arrangement 2 case are shown below as locations ‘a’ and ‘b’, and for a second 4 are in ‘c’ and ‘d’.
Option 1
Layer 1
x 0 0 x
1 4 5 1
1 a c 1
x u u x
Option 2
Layer 2
2 8 9 u
3 6 7 3
u b d u
u 8 9 u
By going through the different choices for the two locations for each of these two values we create Arrangement 3, we now have eight possible assortments.
Observation 6. We now consider the two ELs on Layer 1 touching the initial two 0s. A sample of one of the members of Arr3 is given below. In this example, they are the 1 and 2 in Row 2 of Layer 1. Notice that each of these touches eight filled locations and two unfilled locations. These have been designated by ‘a’ and ‘b’ for the 1 and by ‘c’ and ‘d’ for the 2. Not that b and d are FL on opposite side, so by Lemma 5, they must be equal.
Layer 1
x 0 0 x
1 4 5 2
1 a 4 2
x u u x
Layer 2
2 8 9 3
3 6 7 1
b 5 c d
u u u u
Observation 7. The two options for location b are {9,7} and for location d are {6,8}. Lemma 5 cannot be satisfied as the sets are mutually exclusive. Below is an example showing one case of this violation.
Layer 1
x 0 0 x
1 4 5 2
1 9 4 2
x c d x
Layer 2
2 8 9 3
3 6 7 1
7 5 8 6
a b e f
Post by Carl G.< No solution exists.