# 4DSUDOKU puzzle ceptimus 2025-09-03
# Finds the solution in about a second on an i3 M330 @ 2.13GHz - but then takes about another hour
# searching (without success) for a second solution.
# You can just press Ctrl-C to exit,  once it's displayed the solution.

# label: is the ID on the little sticky label I fastened to each cubie. '@' to 'M' are 14 orange cubies; 'N' to 'Z' are 13 white cubies.
# faces/orientations order is front right back, left, top, bottom. faces: 0 means blank.  There is no faces: 9 - it's a 6 upside-down.
# orientations: 0 = upright for first four, base of number towards front for last two.
# orientations: 1 means rotated 90 degrees counter clockwise, 2 is upside down, 3 means rotated 270 degrees counter clockwise as viewed.
cubies = []
cubies.append({'label': '@', 'colour': 'orange', 'faces': (0, 2, 4, 6, 5, 1), 'orientations': (0, 0, 0, 2, 2, 0)})
cubies.append({'label': 'A', 'colour': 'orange', 'faces': (0, 4, 6, 6, 1, 5), 'orientations': (0, 0, 2, 0, 2, 0)})
cubies.append({'label': 'B', 'colour': 'orange', 'faces': (0, 7, 1, 2, 6, 6), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'C', 'colour': 'orange', 'faces': (0, 7, 7, 6, 3, 8), 'orientations': (0, 0, 0, 2, 2, 2)})
cubies.append({'label': 'D', 'colour': 'orange', 'faces': (0, 6, 8, 4, 6, 3), 'orientations': (0, 2, 0, 0, 0, 2)})
cubies.append({'label': 'E', 'colour': 'orange', 'faces': (1, 5, 2, 3, 7, 6), 'orientations': (0, 0, 0, 0, 2, 0)})
cubies.append({'label': 'F', 'colour': 'orange', 'faces': (1, 7, 5, 3, 6, 2), 'orientations': (0, 0, 0, 0, 3, 1)})
cubies.append({'label': 'G', 'colour': 'orange', 'faces': (1, 8, 5, 6, 5, 6), 'orientations': (0, 0, 0, 0, 0, 2)})
cubies.append({'label': 'H', 'colour': 'orange', 'faces': (2, 3, 7, 8, 8, 7), 'orientations': (0, 0, 0, 0, 0, 2)})
cubies.append({'label': 'I', 'colour': 'orange', 'faces': (2, 4, 8, 8, 1, 3), 'orientations': (0, 0, 0, 0, 1, 3)})
cubies.append({'label': 'J', 'colour': 'orange', 'faces': (2, 6, 6, 6, 1, 8), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'K', 'colour': 'orange', 'faces': (3, 7, 6, 8, 4, 4), 'orientations': (0, 0, 0, 0, 0, 2)})
cubies.append({'label': 'L', 'colour': 'orange', 'faces': (4, 7, 8, 6, 2, 4), 'orientations': (0, 0, 0, 0, 0, 0)})
cubies.append({'label': 'M', 'colour': 'orange', 'faces': (5, 8, 6, 7, 4, 7), 'orientations': (0, 0, 0, 0, 1, 3)})
cubies.append({'label': 'N', 'colour': 'white', 'faces': (0, 1, 6, 1, 5, 4), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'O', 'colour': 'white', 'faces': (0, 2, 5, 5, 6, 7), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'P', 'colour': 'white', 'faces': (0, 5, 2, 7, 3, 8), 'orientations': (0, 0, 0, 0, 2, 0)})
cubies.append({'label': 'Q', 'colour': 'white', 'faces': (0, 8, 3, 3, 4, 6), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'R', 'colour': 'white', 'faces': (1, 6, 4, 5, 3, 2), 'orientations': (0, 0, 0, 0, 3, 1)})
cubies.append({'label': 'S', 'colour': 'white', 'faces': (1, 8, 4, 4, 2, 6), 'orientations': (0, 0, 0, 0, 1, 3)})
cubies.append({'label': 'T', 'colour': 'white', 'faces': (1, 6, 3, 6, 8, 5), 'orientations': (0, 2, 0, 2, 3, 1)})
cubies.append({'label': 'U', 'colour': 'white', 'faces': (1, 6, 5, 6, 7, 2), 'orientations': (0, 2, 0, 2, 0, 0)})
cubies.append({'label': 'V', 'colour': 'white', 'faces': (1, 7, 3, 2, 6, 6), 'orientations': (0, 0, 0, 0, 2, 0)})
cubies.append({'label': 'W', 'colour': 'white', 'faces': (2, 3, 5, 8, 8, 5), 'orientations': (0, 0, 0, 0, 2, 2)})
cubies.append({'label': 'X', 'colour': 'white', 'faces': (2, 6, 3, 6, 2, 1), 'orientations': (0, 2, 0, 2, 3, 1)})
cubies.append({'label': 'Y', 'colour': 'white', 'faces': (3, 4, 7, 4, 6, 1), 'orientations': (0, 0, 0, 0, 0, 2)})
cubies.append({'label': 'Z', 'colour': 'white', 'faces': (4, 6, 6, 5, 7, 3), 'orientations': (0, 2, 0, 0, 2, 0)})

# A cubie can sit on one of six faces, with four vertical axis rotation positions for each of those - so 24 possible orientations.
# First six items of tuple are the untransformed face locations, last six are face rotation offsets (right angle units).
cubie_orientations = []
cubie_orientations.append((0, 1, 2, 3, 4, 5,  0, 0, 0, 0, 0, 0)) #  0: reference position sat on bottom face
cubie_orientations.append((3, 0, 1, 2, 4, 5,  0, 0, 0, 0, 1, 3)) #  1: still sat on bottom face, rotated 90 degrees 
cubie_orientations.append((2, 3, 0, 1, 4, 5,  0, 0, 0, 0, 2, 2)) #  2: 180 degrees
cubie_orientations.append((1, 2, 3, 0, 4, 5,  0, 0, 0, 0, 3, 1)) #  3: 270 degrees
cubie_orientations.append((4, 1, 5, 3, 2, 0,  0, 1, 0, 3, 2, 2)) #  4: now sitting on what was the front face
cubie_orientations.append((3, 4, 1, 5, 2, 0,  3, 0, 1, 0, 3, 1)) #  5: ... and rotated 90 degrees
cubie_orientations.append((5, 3, 4, 1, 2, 0,  0, 3, 0, 1, 0, 0)) #  6: 180
cubie_orientations.append((1, 5, 3, 4, 2, 0,  3, 0, 3, 0, 1, 3)) #  7: 270
cubie_orientations.append((0, 4, 2, 5, 3, 1,  3, 3, 1, 1, 3, 1)) #  8: now sitting on what was the right face
cubie_orientations.append((5, 0, 4, 2, 3, 1,  1, 3, 3, 1, 0, 0)) #  9:  90
cubie_orientations.append((2, 5, 0, 4, 3, 1,  1, 1, 3, 3, 1, 3)) # 10: 180
cubie_orientations.append((4, 2, 5, 0, 3, 1,  3, 1, 1, 3, 2, 2)) # 11: 270
cubie_orientations.append((5, 1, 4, 3, 0, 2,  2, 3, 2, 1, 0, 0)) # 12: now sitting on what was the back face
cubie_orientations.append((3, 5, 1, 4, 0, 2,  1, 2, 3, 2, 1, 3)) # 13:  90
cubie_orientations.append((4, 3, 5, 1, 0, 2,  2, 1, 2, 3, 2, 2)) # 14: 180
cubie_orientations.append((1, 4, 3, 5, 0, 2,  3, 2, 1, 2, 3, 1)) # 15: 270
cubie_orientations.append((0, 5, 2, 4, 1, 3,  1, 3, 3, 1, 1, 3)) # 16: now sitting on what was the left face
cubie_orientations.append((4, 0, 5, 2, 1, 3,  1, 1, 3, 3, 2, 2)) # 17:  90
cubie_orientations.append((2, 4, 0, 5, 1, 3,  3, 1, 1, 3, 3, 1)) # 18: 180
cubie_orientations.append((5, 2, 4, 0, 1, 3,  3, 3, 1, 1, 0, 0)) # 19: 270
cubie_orientations.append((0, 3, 2, 1, 5, 4,  2, 2, 2, 2, 0, 0)) # 20: now sitting on what was the top face
cubie_orientations.append((1, 0, 3, 2, 5, 4,  2, 2, 2, 2, 1, 3)) # 21:  90
cubie_orientations.append((2, 1, 0, 3, 5, 4,  2, 2, 2, 2, 2, 2)) # 22: 180
cubie_orientations.append((3, 2, 1, 0, 5, 4,  2, 2, 2, 2, 3, 1)) # 23: 270

# There are eighteen 3x3 faces in the assembled cube: 6 on the outside of the cube, and 12 hidden internally.
# In the solved puzzle, each face must contain each of the numbers 1 to 9  (actually 1,2,3,4,5,7,8 and two sixes, given the 6 and 9 are interchangeable)
# or all blank (there is one blank 3x3 face somewhere in/on the solved puzzle).
# I've numbered the faces:
# (0, 1, 2) for the forward-facing faces, starting from the front;
# (3, 4, 5) for the right-facing faces, starting from the left;
# (6, 7, 8) for the backward-facing faces, starting from the front;
# (9, 10, 11) for the leftward-facing faces, starting from the left;
# (12, 13, 14) for the upward-facing faces, starting from the bottom;
# (15, 16, 17) for the downward-facing faces, starting from the bottom.
# So 0, 3, 6, 9, 12, 15 are the faces affected by a cubie at the origin (left, bottom, front corner), taken in the same order as the cubie faces;
# and then the two following faces in each case are the ones facing the same direction, but progressively further away from the origin.

# cubie_posn_to_face_posn[cubie_position][face] gives (face number, face position).
# cubie_position 0 to 8 for the front layer, starting with 0 at the bottom left front, 2 at bottom middle front, etc.
# cubie position 9 to 17 for the middle layer, and 18 to 26 for the back layer.
cubie_posn_to_face_posn = []
cubie_posn_to_face_posn.append((( 0, 0), ( 3, 0), ( 6, 2), ( 9, 2), (12, 0), (15, 2))) # cubie_position 0
cubie_posn_to_face_posn.append((( 0, 1), ( 4, 0), ( 6, 1), (10, 2), (12, 1), (15, 1))) #  1
cubie_posn_to_face_posn.append((( 0, 2), ( 5, 0), ( 6, 0), (11, 2), (12, 2), (15, 0))) #  2
cubie_posn_to_face_posn.append((( 0, 3), ( 3, 3), ( 6, 5), ( 9, 5), (13, 0), (16, 2))) #  3
cubie_posn_to_face_posn.append((( 0, 4), ( 4, 3), ( 6, 4), (10, 5), (13, 1), (16, 1))) #  4
cubie_posn_to_face_posn.append((( 0, 5), ( 5, 3), ( 6, 3), (11, 5), (13, 2), (16, 0))) #  5
cubie_posn_to_face_posn.append((( 0, 6), ( 3, 6), ( 6, 8), ( 9, 8), (14, 0), (17, 2))) #  6
cubie_posn_to_face_posn.append((( 0, 7), ( 4, 6), ( 6, 7), (10, 8), (14, 1), (17, 1))) #  7
cubie_posn_to_face_posn.append((( 0, 8), ( 5, 6), ( 6, 6), (11, 8), (14, 2), (17, 0))) #  8
cubie_posn_to_face_posn.append((( 1, 0), ( 3, 1), ( 7, 2), ( 9, 1), (12, 3), (15, 5))) #  9
cubie_posn_to_face_posn.append((( 1, 1), ( 4, 1), ( 7, 1), (10, 1), (12, 4), (15, 4))) # 10
cubie_posn_to_face_posn.append((( 1, 2), ( 5, 1), ( 7, 0), (11, 1), (12, 5), (15, 3))) # 11
cubie_posn_to_face_posn.append((( 1, 3), ( 3, 4), ( 7, 5), ( 9, 4), (13, 3), (16, 5))) # 12
cubie_posn_to_face_posn.append((( 1, 4), ( 4, 4), ( 7, 4), (10, 4), (13, 4), (16, 4))) # 13 core of assembled cube
cubie_posn_to_face_posn.append((( 1, 5), ( 5, 4), ( 7, 3), (11, 4), (13, 5), (16, 3))) # 14
cubie_posn_to_face_posn.append((( 1, 6), ( 3, 7), ( 7, 8), ( 9, 7), (14, 3), (17, 5))) # 15
cubie_posn_to_face_posn.append((( 1, 7), ( 4, 7), ( 7, 7), (10, 7), (14, 4), (17, 4))) # 16
cubie_posn_to_face_posn.append((( 1, 8), ( 5, 7), ( 7, 6), (11, 7), (14, 5), (17, 3))) # 17
cubie_posn_to_face_posn.append((( 2, 0), ( 3, 2), ( 8, 2), ( 9, 0), (12, 6), (15, 8))) # 18
cubie_posn_to_face_posn.append((( 2, 1), ( 4, 2), ( 8, 1), (10, 0), (12, 7), (15, 7))) # 19
cubie_posn_to_face_posn.append((( 2, 2), ( 5, 2), ( 8, 0), (11, 0), (12, 8), (15, 6))) # 20
cubie_posn_to_face_posn.append((( 2, 3), ( 3, 5), ( 8, 5), ( 9, 3), (13, 6), (16, 8))) # 21
cubie_posn_to_face_posn.append((( 2, 4), ( 4, 5), ( 8, 4), (10, 3), (13, 7), (16, 7))) # 22
cubie_posn_to_face_posn.append((( 2, 5), ( 5, 5), ( 8, 3), (11, 3), (13, 8), (16, 6))) # 23
cubie_posn_to_face_posn.append((( 2, 6), ( 3, 8), ( 8, 8), ( 9, 6), (14, 6), (17, 8))) # 24
cubie_posn_to_face_posn.append((( 2, 7), ( 4, 8), ( 8, 7), (10, 6), (14, 7), (17, 7))) # 25
cubie_posn_to_face_posn.append((( 2, 8), ( 5, 8), ( 8, 6), (11, 6), (14, 8), (17, 6))) # 26

faces = [[-1] * 9 for i in range(18)] # An unfilled position in a face is represented by -1, because 0 is used for the blank faces.
orientations = [[-1] * 9 for i in range(18)]
def faces_ok():
    for face_index in range(18):
        face = faces[face_index]
        blank_present = False # Becomes true if at least one blank cubie face is present.
        number_present = False # Becomes true if at least one non-blank cubie face is present.
        specific_number_present = [False] * 9
        i = next((face.index(x) for x in face if x > 0 and x != 6), None)
        if i == None:
            i = next((face.index(x) for x in face if x == 6), None)
        if i != None:
            orientation = orientations[face_index][i]
        else:
            orientation = None
        for cubie_face_index in range(9):
            cubie_face = face[cubie_face_index]
            if cubie_face >= 0:
                if cubie_face == 0:
                    if number_present:
                        return False; # If one cubie face on a face is blank, then all cubie faces on that face must all be blank.
                    blank_present = True
                else:
                    if blank_present:
                        return False; # If one cubie face on a face is blank, then all cubie faces on that face must all be blank.
                    if cubie_face != 6: # Special checking for any sixes/nines present follows below.
                        if specific_number_present[cubie_face]:
                            return False; # Numbers other than 6 or 9 can only appear once
                        if orientations[face_index][cubie_face_index] != orientation:
                            return False # Numbers other than 6 or 9 must be correctly oriented
                    specific_number_present[cubie_face] = True
                    number_present = True;
        if specific_number_present[6]: # There is at least one 6 or 9 present.
            count_of_sixes = face.count(6)
            if count_of_sixes > 2:
                return False # The first two could be a 6 and a 9, but after that, a face is NOT ok.
            if count_of_sixes == 2: # The two orientations should differ by 180 degrees.
                i6 = [i for i, x in enumerate(face) if x == 6] # indexes of sixes
                rotation = abs(orientations[face_index][i6[0]] - orientations[face_index][i6[1]])
                if rotation != 2:
                    return False # The two orientations don't differ by 180 degrees.
            first_six_index = face.index(6) # Whether there are one or two sixes present.
            rotation = abs(orientations[face_index][first_six_index] - orientation)
            if rotation % 2:
                return False # The first six is oriented sideways, for either a six or a nine.
    return True

cubies_fitted = [-1] * 27
cubies_orientation = [-1] * 27
def display_solution():
    print('\n\nCubie IDs and rotations, starting left-down-front, then middle-down-front, etc.  First 9 define the front layer,')
    print('next nine the middle layer, and last nine the back layer.')
    print('0 means label upright and facing the front; 1 means label upright and facing right;')
    print('2 means label upright and facing back; 3 means label upright and facing right.')
    print('It turns out that the other twenty possible orientations are not used in any solution.\n')
    print('Solution: ', end = '')
    for i in range(27):
        print("{0}{1}".format(cubies[cubies_fitted[i]]['label'], cubies_orientation[i]), end = ' ')
    print()
    for i in range(0, 18, 3):
        # To correctly print any '9's masquerading as '6's, look at three orientations on a face:
        # There can only be one '9' on a solved face, so a majority vote of three orientations
        # will always give the 'correct'orientation for that face.
        ori_0 = orientations[i][0]
        ori_1 = orientations[i][1]
        ori_2 = orientations[i][2]
        ori = ori_0
        if ori != ori_1 and ori != ori_2:
            ori = ori_1
        print("\n{}-facing faces:".format(['Forward', 'Rightward', 'Backward', 'Leftward', 'Upward', 'Downward'][i // 3]), end = '')
        if i == 12:
            print(' (numbers upside-down)', end = '') # Added this to assist anyone using the output to arrange the physical cube.
        elif i == 15:
            print(' (middle and top layer numbers upside-down)', end = '')  # Again, added this to assist with the physical cube.
        print()
        for row in range(3):
            for j in range(3):
                for column in range(3):
                    number = faces[i + j][6 - row * 3 + column]
                    if number == 6 and orientations[i + j][6 - row * 3 + column] != ori:
                        number = 9 
                    print(number, end = ' ');
                print('  ', end = '')
            print()
    print()

cubies_in_use = [False] * 27
oc = {'faces': [0] * 6, 'orientations': [0] * 6} # oriented cubie.

# Try each unused cubie in the specified position, trying it in all possible orientations:
# if it doesn't cause any problems, recurse to fit the next cubie position.
def fit(cubie_posn):
    required_colour = 'orange' if cubie_posn % 2 == 0 else 'white'
    this_posn_to_face_posn = cubie_posn_to_face_posn[cubie_posn]
    cubie = -1 # Start looking through the list of cubies_in_use from the beginning.
    while (True): # Loop through all unused cubies.
        try:
            cubie = cubies_in_use.index(False, cubie + 1)
        except ValueError:
            break;
        # With the orientation of the core cubie locked (see below) to eliminate trivial rotated solutions,
        # there would still be trivial mirrored solutions by swapping the left/right, bottom/top, or front/back layers.
        # Since an orange cubie can only be located at the corner of the big cube, or the centre of its faces, we can
        # eliminate these mirrored solutions by restricting one orange cubie, say the first one, to just one corner or
        # one centre face position.
        if cubie == 0 and not(cubie_posn == 0 or cubie_posn == 4):
            continue
        # Cubies in even numbered locations must be orange (<= 13), cubies in odd-numbered locations must be white (> 13).
        if cubies[cubie]['colour'] != required_colour:
            continue

        for orientation in range(24):
            if cubie_posn == 0: # Display progress.
                print(F"Trying {cubies[cubie]['label']}-cubie in first position, in orientation {orientation} ", end = '\r')
            for i in range(6):
                oc['faces'][i] = cubies[cubie]['faces'][cubie_orientations[orientation][i]]
                oc['orientations'][i] = (cubies[cubie]['orientations'][cubie_orientations[orientation][i]] + cubie_orientations[orientation][i + 6]) % 4
            for cubie_face in range(6): # try the oriented cubie 
                face, position = this_posn_to_face_posn[cubie_face]
                faces[face][position] = oc['faces'][cubie_face]
                orientations[face][position] = oc['orientations'][cubie_face]
            if faces_ok():
                cubies_in_use[cubie] = True
                cubies_fitted[cubie_posn] = cubie
                cubies_orientation[cubie_posn] = orientation
                if cubie_posn < 26:
                    fit(cubie_posn + 1)
                else:
                    display_solution()
                cubies_fitted[cubie_posn] = -1
                # cubies_orientation[cubie_posn] = -1 # Orientations are only used for fitted cubies, so no need to null out when removing a cubie.
                cubies_in_use[cubie] = False
            if cubie_posn == 13:
                break # At core of assembled cube, we only fit a cubie in one orientation - excludes duplicate rotated solutions.

    for cubie_face in range(6): # Remove the last cubie tried at this position.
        (face, position) = this_posn_to_face_posn[cubie_face]
        faces[face][position] = -1

fit(0)
print()

# following 'modeline' configures my text editor, xed, to use Python-style 'tabs' (4 spaces)
# vi:si:et:sw=4:sts=4:ts=4
# it must be either the first line of the file (which conflicts with any shebang) or in the last three lines