Twisty Puzzles

Twisty puzzles are a subset of combination puzzles, where the AI has to unscramble a three-dimensional puzzle by rotating (or twisting) the sides until each side is a solid block of colour. Most famously these include the Rubix Cube, (invented by Ernő Rubik in 1974,) a cube made of 26 smaller cubes that rotate around a central point; but the family of puzzles have expanded to include all sorts of shapes.

Notation and Scoring

A lot of confusion for these puzzles is generated by the labelling of the moves and the different scoring systems available. Here (as far as possible) we have adopted the World Cube Association standards as set out in the WCA regulations, (section 12) and use the outer block turn metric (OBTM) to count moves.

Notation for NxNxN Cubes (From WCA):

• Face Moves (outer slice):
  • Clockwise, 90 degrees: F (front face), B (back face), R (right face), L (left face), U (upper face), D (bottom face).
  • Counter-clockwise, 90 degrees: F’, B’, R’, L’, U’, D’.
  • 180 degrees: F2, B2, R2, L2, U2, D2.
• Outer Block Moves (outer slice with adjacent inner slices). For each of the moves defined below, n is the total number of slices to move, which must be in the range 1 < n < N (where N is the number of layers in the puzzle). n may be also be omitted, for an implicit value of n = 2 slices. Outer Block Moves are:
  • Clockwise, 90 degrees: nFw, nBw, nRw, nLw, nUw, nDw.
  • Counter-clockwise, 90 degrees: nFw’, nBw’, nRw’, nLw’, nUw’, nDw’.
  • 180 degrees: nFw2, nBw2, nRw2, nLw2, nUw2, nDw2.
• Rotations (entire puzzle):
  • Clockwise, 90 degrees: x (same direction as R or L’), y (same direction as U or D’), z (same direction as F or B’).
  • Counter-clockwise, 90 degrees: x’ (same direction as R’ or L), y’ (same direction as U’ or D), z’ (same direction as F’ or B).
  • 180 degrees: x2, y2, z2.
• Outer Block Turn Metric (OBTM) is defined as:
  • Each move of the categories Face Moves and Outer Block Moves is counted as 1 move.
  • Each move of the Rotations category is counted as 0 moves.

Note – Although the WCA notes that dropping the “2” prefix for outer block moves when n=2 is optional, here it is done in all cases.

Algorithms and Hints

Although in theory all twisty puzzles could be solved by a simple search algorithm, (as all future states can be accurately predicted) in reality all but the smallest puzzles have far too many possible combinations actually do this.

smallTablePuzzle Type	Positions (Possible States)
Cube 2x2x2	3,674,160
Cube 3x3x3	43,252,003,274,489,856,000
Cube 4x4x4	7.4 × 1045
Cube 5x5x5	2.8 × 1074
Cube 6x6x6	1.6 × 10116
Cube 7x7x7	2.0 × 10160

Instead, you could try splitting the puzzle into several smaller tasks (i.e. top layer, sides, bottom corners, whole cube) with the solution to each sub-puzzle keeping the previous state intact.

Alternatively, it has been shown that by using a deep neural network to predict how many moves a state is away from a solution, existing search algorithms (such as A*) can be adapted to produce good results.

API Interface

The Swagger specification for this API can be downloaded here.

The API is implemented as a single POST action which contains:

• The type of the puzzle, current valid values are:
  • Cube 2x2x2 (OBTM)
  • Cube 3x3x3 (OBTM)
  • Cube 4x4x4 (OBTM)
  • Cube 5x5x5 (OBTM)
  • Cube 6x6x6 (OBTM)
  • Cube 7x7x7 (OBTM)
  • Cube 8x8x8 (OBTM)
  • Cube 9x9x9 (OBTM)
  • Cube 10x10x10 (OBTM)
• A list of valid moves.
• The current state of the puzzle, encoded as a string.
• (Optional) the result of the last move, this contains:
  • The starting state.
  • The move made.
  • The end state.
  • If this move resulted in a solved puzzle.

The response should be the desired move, expressed as a string.

Making multiple moves

To make multiple moves in the same network response, separate the moves by spaces. For example:

<move>R D' R' U2</move>

The history object of the next request will only show the last move made.

State Encoding – Cuboids

The state of the puzzle is encoded as a string, with each character representing the colour of a single face.

Character	Colour
‘W’	White
‘O’	Orange
‘G’	Green
‘R’	Red
‘B’	Blue
‘Y’	Yellow

Each face is encoded row by row, from top left to bottom right.

JSON Example Request

{
  "history": {
    "startState": "OYWYYBRYOYBYRRRWRRBRYGGYGGRGOBGOOYBGOOBGBBOORWWGWWWBWW",
    "moves": "D'",
    "endState": "OYWYYBRYOYBYRRRGGRBRYGGYYBGGOBGOOOOROOBGBBWRRGWWWWWWWB",
    "success": false
  },
  "puzzleType": "Cube 3x3x3 (OTBM)",
  "moves": [
    "R", "L", "U","D","R'","L'"
  ],
  "state": "OYWYYBRYOYBYRRRGGRBRYGGYYBGGOBGOOOOROOBGBBWRRGWWWWWWWB"
}

JSON Example Response

{
  "move": "R D R'"
}

XML Example Request

<?xml version="1.0" encoding="UTF-8"?>
<TwistyRequest>
 <history>
<startState>OYWYYBRYOYBYRRRWRRBRYGGYGGRGOBGOOYBGOOBGBBOORWWGWWWBWW</startState>
  <moves>D'</moves>
<endState>OYWYYBRYOYBYRRRGGRBRYGGYYBGGOBGOOOOROOBGBBWRRGWWWWWWWB</endState>
  <success>false</success>
</history>
<puzzleType>Cube 3x3x3 (OTBM)</puzzleType>
<moves>R</moves>
<moves>L</moves>
<moves>U</moves>
<moves>D</moves>
<moves>R'</moves>
<moves>L'</moves>
<moves>U'</moves>
<moves>D'</moves>
<state>OYWYYBRYOYBYRRRGGRBRYGGYYBGGOBGOOOOROOBGBBWRRGWWWWWWWB</state>
</TwistyRequest>

XML Example Response

<?xml version="1.0" encoding="UTF-8"?>
<TwistyResponse>
	<move>R D R'</move>
</TwistyResponse>