15
\$\begingroup\$

What is the shortest sequence of moves that, from the solved state of the cube, creates a pattern that meets the following criteria:

  • 6 colors on each face
  • at most 2 facelets of the same color
  • no adjacent facelets of the same color

EDIT: I made up the name of the pattern. I asked this question in 2018 on Mathematics Stack Exchange and forgot about it. Thanks to uhoh for suggesting Code Golf. Who knows when I would have discovered this awesome community!


* In the Rubik's world, an algorithm is a sequence of moves, like: L, R, U, D, F, B etc.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ While this question is technically on topic here, you're likely to get more answers on Puzzling. Check out their rubiks-cube tag to see if a similar question was asked before. \$\endgroup\$
    – Bubbler
    Nov 21, 2023 at 23:08

2 Answers 2

22
\$\begingroup\$

Seven Face Turns

U D2 F2 B2 R L U'

With yellow (Y) at the top, red (R) at the front and green (G) at the right (with their opposites white (W), orange (O), and blue (B) respectively) that produces the net:

      O R G
      W Y W
      B O R
W R Y O G B W O Y R B G
G B R Y R W B G O Y O W
O G B W G Y R B G W B Y
      O Y B
      R W O
      G Y R

Here is Python code that finds this solution.

Try it online!

from dataclasses import dataclass


# Move functions (not the nicest to read but they do the job)
def U(state):
    return [
        state[0][6:] + state[0][:6],
        state[2][:3] + state[1][3:],
        state[4][:3] + state[2][3:],
        state[3],
        state[5][:3] + state[4][3:],
        state[1][:3] + state[5][3:],
    ]


def F(state):
    return [
        state[0][:4] + state[5][2:5] + state[0][7:],
        state[1][6:] + state[1][:6],
        state[0][6:7] + state[2][1:6] + state[0][4:6],
        state[2][6:8] + state[2][:1] + state[3][3:],
        state[4],
        state[5][:2] + state[3][:3] + state[5][5:],
    ]


def R(state):
    return [
        state[0][:2] + state[1][2:5] + state[0][5:],
        state[1][:2] + state[3][2:5] + state[1][5:],
        state[2][6:] + state[2][:6],
        state[3][:2] + state[4][6:] + state[4][:1] + state[3][5:],
        state[0][4:5] + state[4][1:6] + state[0][2:4],
        state[5],
    ]


def D(state):
    return [
        state[0],
        state[1][:4] + state[5][4:7] + state[1][7:],
        state[2][:4] + state[1][4:7] + state[2][7:],
        state[3][6:] + state[3][:6],
        state[4][:4] + state[2][4:7] + state[4][7:],
        state[5][:4] + state[4][4:7] + state[5][7:],
    ]


def B(state):
    return [
        state[2][2:5] + state[0][3:],
        state[1],
        state[2][:2] + state[3][4:7] + state[2][5:],
        state[3][:4] + state[5][6:] + state[5][:1] + state[3][7:],
        state[4][6:] + state[4][:6],
        state[0][2:3] + state[5][1:6] + state[0][:2],
    ]


def L(state):
    return [
        state[4][4:5] + state[0][1:6] + state[4][2:4],
        state[0][:1] + state[1][1:6] + state[0][6:],
        state[2],
        state[1][:1] + state[3][1:6] + state[1][6:],
        state[4][:2] + state[3][6:] + state[3][:1] + state[4][5:],
        state[5][6:] + state[5][:6],
    ]


# Names of the move functions above, first anticlockwise around one corner - UFR
# then their opposing faces (clockwise around the opposite corner) - DBL
FACES = "UFRDBL"
N_FACE_PAIRS = len(FACES) // 2

MOVE_FUNCTIONS = [eval(f) for f in FACES]

ROTATION_INDICATORS = ("", "2", "'")
ROTATIONS = tuple(clockwise_quarters for clockwise_quarters, indicator in enumerate(ROTATION_INDICATORS, start=1))

FIRST_FACES_TO_TURN = (FACES.index("U"),)  # one choice up to symmetry (arbitrary)
SECOND_FACES_TO_TURN = (FACES.index("D"), FACES.index("F"))  # two choices up to symmetry (one opposite, one adjacent)

SOLVED_STATE = [[i] * 8 for i in range(len(FACES))]


def adjacent(face_1, face_2):
    return face_1 % N_FACE_PAIRS != face_2 % N_FACE_PAIRS


@dataclass()
class Move:
    face: int
    rotation: int


def gen_move_sequences(depth):
    if depth > 0:
        for move_sequence in gen_move_sequences(depth - 1):
            if len(move_sequence) > 1:
                faces = (f for f in range(len(FACES))
                         if f != move_sequence[-1].face
                         and (f != move_sequence[-2].face
                              or adjacent(move_sequence[-1].face, move_sequence[-2].face)
                              )
                         )
                turn_stop = 3
            elif len(move_sequence) == 1:
                faces = SECOND_FACES_TO_TURN
                turn_stop = 3
            else:
                faces = FIRST_FACES_TO_TURN
                turn_stop = 2
            for face in faces:
                for turn in ROTATIONS[:turn_stop]:
                    yield move_sequence + [Move(face, turn)]
    else:
        yield []


def get_state(move_sequence):
    v = SOLVED_STATE
    for m in move_sequence:
        for i in range(m.rotation):
            v = MOVE_FUNCTIONS[m.face](v)
    return v


def print_move_sequence(move_sequence):
    print(' '.join(FACES[move.face] + ROTATION_INDICATORS[move.rotation - 1] for move in move_sequence))


def is_harlequin(state):
    for face in range(len(FACES)):
        # centre colour must not be an edge facelet colour
        if face in state[face][1::2]:
            return False
        # adjacent non-centre facelets must not have the same colour
        if any(a == b for a, b in zip(state[face], state[face][1:] + state[face][:1])):
            return False
        # face must have all colours
        if len(set(state[face] + [face])) < len(FACES):
            return False
        # No need to check the maximum repetitions to find the first "Harlequin" it seems, but if it were:
        # from collections import Counter  # move to top of module
        # if max(Counter(state + [face]).values()) > 2:
        #     return False
    return True


def main():
    depth = 1
    while depth:
        print(f"searching at {depth=}")
        for move_sequence in gen_move_sequences(depth):
            if is_harlequin(get_state(move_sequence)):
                print_move_sequence(move_sequence)
                break
        else:
            depth += 1
            continue
        break


if __name__ == "__main__":
    main()
\$\endgroup\$
5
  • 1
    \$\begingroup\$ If I have not made a mistake (particularly thinking about the pruning I have done in the next_moves function to avoid some simple redundant sequences) then yes. \$\endgroup\$ Nov 22, 2023 at 2:00
  • 1
    \$\begingroup\$ So... theoretically speaking... Could be possible that a shorter sequence could have been pruned? \$\endgroup\$
    – q-l-p
    Nov 22, 2023 at 2:03
  • 1
    \$\begingroup\$ If I have made an error in that logic. I think it is sound, just not 100% confident. \$\endgroup\$ Nov 22, 2023 at 2:07
  • 4
    \$\begingroup\$ I ran it without any pruning (i.e. just for n in range(6): ...yield cur + [(n, 1)]... to try every possible move) up to and including six moves without finding a valid state. So I don't believe any shorter solution exists. \$\endgroup\$ Nov 22, 2023 at 2:14
  • 7
    \$\begingroup\$ It's amazing how the answer has such a beautiful symmetry. It's like a... twisted checkerboard pattern. I was about to give up on Python, but your answer inspires me to keep learning. \$\endgroup\$
    – q-l-p
    Nov 22, 2023 at 2:24
4
\$\begingroup\$

While I was was sieving through hundreds of patterns, using Herbert Kociemba's Cube Explorer, I stumbled upon a pattern, shown in the animation* below, that can be generated by a 15-move algorithm. But I don't know if this is the shortest algorithm which generates a harlequin pattern.

Harlequin pattern on a rotating Rubik's Cube
D' F L2 D F U2 B U' R' L F B L2 D L'


UPDATE – I found another one!
F R B D B F2 R2 U2 L' F' L D2 B R2 U

Today I decided to systematically search for the shortest harlequin algorithm using Kociemba's program. I started by manually counting the number of harlequin search patterns to be used in the Pattern Editor. There are 7 ways to arrange the first 2 facelets of the 1st color (excluding rotation symmetry):
enter image description here

For patterns 1 and 5 there are only 13 ways to arrange the next 2 facelets of the 2nd color:
enter image description here

For patterns 2, 6 and 7 there are 15 ways to arrange the 2nd color facelet pair. For patterns 3 and 4 there are 14 ways.

So, there are 99 ways in which the first 4 facelets can be arranged. For pattern 1 I counted 80 ways in which the 3rd color facelet pair can be placed. Because the colors of the search pattern only tell the program the structure of the pattern and not the actual colors to be searched, it doesn't matter how we color the last 3 facelets as long as each has a unique color. So there are 80 search patterns that begin with pattern 1. Pattern 2 is the starting point for 110 search patterns. Pattern 3 generates 94 search patterns. But I ran into a roadblock. Some search patterns produce 7 results, some 164 and some... OVER 9000!!

I had to stop the program after letting it run for more than 24 hours. It was still searching for patterns.

Obviously, it is unfeasible to manually search for the shortest harlequin generator. I hope someone will find a better way to answer this question. I understand that the number of harlequin patterns may be so large that it renders such patterns as... not so special to worth the effort of investigating. I don't know enough math to go any further.

I am still interested in a mathematical solution to this puzzle.


* GIF created using Rubik's Cube Explorer and VirtualDub.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.