From cube-lovers-errors@mc.lcs.mit.edu Fri Jan 21 23:22:37 2000 Return-Path: Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38]) by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id XAA00709 for ; Fri, 21 Jan 2000 23:22:36 -0500 (EST) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu Message-Id: <19991231122908.11135.qmail@web109.yahoomail.com> Date: Fri, 31 Dec 1999 04:29:08 -0800 (PST) From: Jaap Scherphuis Reply-To: jaap@org2.com Subject: Square-1 tables of move sequences To: Cube-Lovers@ai.mit.edu Dear Cube-Lovers, I have just computed many new results for the Square-1 puzzle. I have written a program that applies a Kociemba-like algorithm to this puzzle, and used it to find many beautifully short sequences for nearly all standard moves of the edges and corners. This post is very long, and will list most of the results. First however I should quickly describe the puzzle and highlight some of its intricacies, since these might not be overly familiar even though it has been mentioned on this list in the past. -- Short description of the Square-1 puzzle: This puzzle is a cube consisting of three layers. The top and bottom layers are cut like a pie in 8 pieces; 4 edge pieces and 4 corner pieces, 30 and 60 degrees wide respectively. The top and bottom layers can rotate. The middle layer is cut in only two halves along one of the lines of the other layers. If there are no corner pieces in the way, you can twist half the cube 180 degrees so that pieces from the top and bottom layers mingle. The puzzle is unique in that the two types of pieces intermingle. The edge and corner pieces can freely move between the two outer layers. Of course, the puzzle will not necessarily be a cube shape when the pieces are mixed. The puzzle has six colours, each face has a single colour similar to the Rubik's cube. The aim is of course to return a mixed puzzle back to its original solved position. The number of positions: There are three categories of puzzle shapes. a. Both layers have 4 edges and 4 corners each. b. One layer has 3 corners, 6 edges, the other 5 corners 2 edges. c. One layer has 2 corners, 8 edges, the other 6 corners and no edges. There are 1, 3, 10, 10 and 5 layer shapes with 6, 5, 4, 3 and 2 corners. This means there are 5*1+10*3+10*10+3*10+1*5 = 170 shape combinations for the top and bottom layers (all of them can be attained). The middle layer has two shapes because half of it is assumed to be in a fixed position and only the other half moves. This means that there seem to be 170*2*8!*8! = 552,738,816,000 positions if we disregard rotations of the layers. Some layer shapes however have symmetry, and these have been counted too many times this way. To take account of the symmetries we can simply count the number of layer shapes differently. Instead of the numbers 1, 3, 10, 10, 5 we use the numbers 2, 36, 105, 112, 54, which are the number of shapes if we consider rotations different (e.g. a square counts as 3 because it has three possible orientations). By the same method as before we then get 19305*2*8!*8! or 627,768,369,664,000 positions. To exclude layer rotations, divide by 12^2 to get a total of 435,891,456,000 distinct positions. -- Notation I use a different notation to that found on other places on the web, because I find this one more descriptive. Hold the puzzle so that the yellow middle layer piece is on the left hand side with its 'Square-1' inscription the right way up. Denote a 180 degree turn of the right hand side of the puzzle by a / sign (a slash). Turns of the top and bottom layers are denoted by a pair of numbers (n,m). These numbers are the multiple of 30 degrees clockwise that the top/bottom layers are to turn respectively. Thus (3,0) means turn only the top layer clockwise 90 degrees, and (0,-1) means turn only the bottom layer 30 degrees anti-clockwise (i.e. one edge along). Note that I define the LENGTH OF A SEQUENCE of moves simply as the number of / moves in it. By labelling the faces by the letters U, D, L, R, F, B in the standard way for the Rubik's cube, the pieces of Square-1 can also be denoted in the usual way; a combination of two letters for an edge piece and three letters for a corner piece. -- Subtleties of the puzzle Generally the puzzle is solved by first bringing its shape back to a cube, and then placing the pieces correctly. The reason for this is that there are many moves that keep the top an bottom layers square, for example (1,0)/(0,-1). Each / does of course change the middle layer shape from a square to a kite shape, but this can be ignored because /(0,6)/(0,6)/(0,6) affects only the middle layer. Ignoring the middle layer, a cube can be formed in at most 7 moves. A difficulty arises from the fact that these cube moves swaps two pairs of corners and two pairs of edges, which is an even permutation. The pieces can however end up in an odd permutation. To solve this, you will have to leave the cube shape behind. One way is by doing /(3,3)/(1,2)/ which brings together four corner pieces in each layer. Now (2,-2)/(-2,2) will swap three pairs of corners, and by reversing the previous moves we can return to a cube. As you can see this has taken 7 moves, and in fact there is no shorter way of performing an odd permutation on the cube. -- The Search Algorithm The search algorithm in my program is very similar in design to the Kociemba algorithm for solving the Rubik's cube, as it solves it in two stages and uses tables to prune the search tree. During the first stage of the search a position is found in which the top and bottom layers are square and where the pieces lie in an even permutation. The second stage will then solve it with moves that keep the top and bottom layers square. The first stage uses a single look-up table, that holds the number of moves needed to bring the puzzle to a cube from the current shape. It is only when the cube shape is reached that the parity of the permutation is checked. In the future I may try to build a larger table which combines the permutation parity with the shape. The second stage uses in effect two look-up tables, one for the edges and one for the corners, and the number of moves needed to solve them is given. In reality the two tables are identical since cube-moves swap corners and edges in the same way. In virtually all other aspects the two phase search is performed in the same manner as the Kociemba algorithm, so I need not explain further. The only remaining difference is that my program continues searching for sequences of the same length as any already found. My reason for this is that some sequences require fewer turns of the top and bottom layers, and are therefore better despite being of the same length as defined above. -- Results I suspect that God's algorithm (the shortest possible way of solving any position) uses at most about 12 moves. Clearly this cannot be proved with this program, but nearly all the positions I have tried can be done in 12 or fewer moves. Most of the results that I have found using this program are on my website. Jaap's Puzzle page: http://www.org2.com/jaap/puzzles The most important ones are below. Sequence E6 is especially amazing, as it swaps three pairs of corners and nothing else in only 7 moves. Another highlight is C4, an edge swap in 10 moves. A. Sequences involving only edges, and where some of them change layer: 1. Swap DF-UF, DR-UR, DB-UB, DL-UL: (0,5)/(1,1)/(-4,2)/(1,1)/(2,3) 2. Swap DF-UF, DB-UB: (0,5)/(1,1)/(-1,6) 3. Swap DF-UB, DB-UF: (0,-1)/(1,1)/(-1,0) 4. Swap DR-UR, DB-UB: (0,2)/(0,3)/(1,1)/(-1,-4)/(0,-2) 5. Swap DR-UB, DB-UR: (0,2)/(0,3)/(1,-5)/(-1,5)/(0,3)/(0,-2) 6. Swap DB-UB, DR-UF: /(-3,0)/(0,5)/(6,1)/(0,3)/(-5,0)/(-1,6) 7. Swap DB-UF, DR-UB: (1,0)/(0,5)/(6,3)/(0,5)/(-5,0)/(-3,6)/(6,0) 8. Swap DR-UF, UR-UB: (1,0)/(-4,5)/(0,-3)/(1,1)/(-1,2)/(4,-5)/(-1,0) 9. Swap DR-UR, UF-UB: (1,3)/(0,3)/(0,3)/(-1,2)/(1,4)/(0,3)/(-1,0) 10. Swap DR-UB, UF-UR: (4,3)/(3,0)/(-4,5)/(1,1)/(-3,0)/(0,-3)/(2,3) 11. Cycle UF->UR->DR: (1,3)/(0,5)/(0,3)/(6,1)/(0,5)/(3,6)/(6,-3) 12. Cycle UF->UB->DR: (0,5)/(0,1)/(6,3)/(5,0)/(-5,0)/(0,3)/(-1,0)/(0,1) 13. Swap UF-DF: /(3,3)/(5,0)/(2,0)/(-4,4)/(2,0)/(-1,3)/(0,3)/(3,3)/(2,0)/(-2,1)/(5,2)/(4,-5)/(2,6) B. Sequences involving only edges of both layers where they do not change layer: 1. Swap UF-UB, UR-UL, DF-DB, DR-DL: (1,0)/(-3,3)/(2,2)/(3,3)/(-2,4)/(5,0) 2. Swap UF-UL, UR-UB, DF-DL, DR-DB: (0,2)/(-3,0)/(1,1)/(-4,2)/(1,1)/(5,-4)/(0,-2) 3. Swap UF-UB, DF-DB: (1,0)/(-1,5)/(1,-5)/(-1,6) 4. Swap UR-UB, DR-DB: (0,2)/(0,-3)/(1,1)/(-1,2)/(0,-2) 5. Swap UF-UB, DR-DB: (0,2)/(1,0)/(0,3)/(6,1)/(0,5)/(-3,0)/(5,6)/(6,-2) 6. Swap UF-UB, UL-UR, DF-DB: /(3,3)/(1,2)/(2,-4)/(-2,4)/(2,4)/(3,3)/(3,0)/(3,3)/(3,0) C. Sequences involving only edges of the top layer: 1. Swap UF-UB, UR-UL: /(3,-3)/(3,-3)/(6,-2)/(3,-3)/(3,-3)/(2,0) 2. Swap UF-UL, UR-UB: /(3,3)/(1,4)/(5,5)/(-3,0)/(3,3)/ 3. Cycle UF->UB->UR: (1,0)/(-1,2)/(-5,1)/(0,3)/(-3,0)/(5,2)/(-5,4)/(-4,0) 4. Swap UF-UB: /(3,3)/(3,2)/(-4,2)/(-2,4)/(-2,0)/(-4,2)/(-5,1)/(3,0)/(3,3)/(0,-3) 5. Swap UF-UR: /(3,3)/(-3,0)/(0,4)/(-2,4)/(-4,2)/(-1,0)/(3,3)/(0,4)/(-3,0)/(0,3)/(-1,2)/(-2,1)/(-1,0) 6. Cycle UF->UR->UB->UL: /(3,3)/(1,0)/(2,2)/(0,2)/(4,4)/(2,0)/(2,2)/(-1,0)/(-3,-3)/(0,3) D. Sequences involving only corners, and where some of them change layer: 1. Swap UFR-DFR, UBR-DBR, UBL-DBL, UFL-DFL: (4,0)/(2,2)/(-3,3)/(-2,-2)/(-1,-3) 2. Swap UFL-DFL, UBR-DBR: (4,0)/(2,2)/(6,-2) 3. Swap UFL-DBR, UBR-DFL: (-2,0)/(2,2)/(0,-2) 4. Swap UFL-DFL, UFR-DFR: (6,5)/(-3,0)/(4,4)/(2,5)/(0,1) 5. Swap UFL-DFR, UFR-DFL: (1,0)/(3,0)/(-4,2)/(-2,4)/(0,3)/(5,6) 6. Swap UFL-DFL, UBR-DFR: /(3,0)/(6,2)/(4,0)/(-3,0)/(6,-2)/(-4,0) 7. Swap UFL-DFR, UBR-DFL: (6,0)/(3,0)/(6,2)/(4,0)/(-3,0)/(6,-2)/(2,0) 8. Swap UFR-UBR, UFL-DFR: (4,3)/(0,3)/(3,0)/(2,5)/(-5,4)/(3,0)/(5,3) 9. Swap UFL-UBR, UFR-DFR: (0,5)/(0,3)/(0,3)/(-2,1)/(2,5)/(0,3)/(0,-2) 10. Swap UFL-UFR, UBR-DFR: (-2,0)/(0,3)/(6,3)/(2,2)/(-2,1)/(-3,0)/(-4,6) 11. Cycle UFL->UFR->DFR: (1,3)/(-4,0)/(6,3)/(0,4)/(-4,0)/(3,0)/(-3,3) 12. Cycle UFL->UBR->DFR: (-5,0)/(3,0)/(5,2)/(-5,4)/(0,3)/(-1,2)/(-2,4)/(-4,6) 13. Swap UFR-DFR: (-3,0)/(6,3)/(-1,4)/(-2,2)/(-4,4)/(-4,1)/(0,3)/(0,2)/(0,3)/(-2,4)/(-4,2)/(3,0)/(-3,4) E. Sequences involving only edges of both layers where they do not change layer: 1. Swap UFR-UBL, UFL-UBR, DFR-DBL, DFL-DBR: (1,0)/(-1,5)/(3,3)/(1,1)/(-3,3)/(5,0) 2. Swap UFR-UFL, UBL-UBR, DFR-DFL, DBL-DBR: (0,5)/(0,3)/(4,4)/(-3,3)/(2,2)/(0,-3)/(6,1) 3. Swap UFL-UBR, DFL-DBR: (0,5)/(-2,4)/(2,-4)/(0,1) 4. Swap UFL-UFR, DFL-DFR: (1,0)/(-3,0)/(2,2)/(1,-2)/(-1,0) 5. Swap UFL-UBR, DFL-DFR: (-2,0)/(0,2)/(0,3)/(-4,0)/(4,0)/(6,3)/(-2,0)/(2,6) 6. Swap UFL-UBR, UFR-UBL, DFL-DBR: /(3,3)/(-3,4)/(-2,4)/(-4,2)/(-4,3)/(3,3)/ F. Sequences involving only edges of the top layer: 1. Swap UFL-UBR, UFR-UBL: /(-3,3)/(-3,3)/(0,1)/(-3,3)/(-3,3)/(-1,6) 2. Swap UFL-UFR, UBR-UBL: /(3,3)/(-3,0)/(4,4)/(2,5)/(3,3)/ 3. Cycle UFL->UBR->UFR: (-5,0)/(-4,5)/(4,1)/(-3,0)/(0,3)/(-4,2)/(-2,1)/(2,0) 4. Swap UFL-UBR: /(3,3)/(-5,0)/(4,4)/(2,0)/(4,4)/(-2,5)/(3,3)/(0,5)/(-2,-2)/(5,0) 5. Swap UFL-UFR: (0,3)/(1,2)/(3,2)/(-4,0)/(0,4)/(-4,3)/(5,4)/(6,3)/(2,0)/(-2,4)/(-4,2)/(6,-2) 6. Cycle UFL->UBL->UBR->UFR: /(3,3)/(-5,0)/(4,4)/(2,0)/(4,4)/(-2,5)/(3,3)/(0,5)/(-2,-2)/(5,0) Copyright 2000 Jaap Scherphuis. Jaap's Puzzle Page: http://www.org2.com/jaap/puzzles ===== Jaap Scherphuis Visit the Psion Organiser II CM, XP & LZ Homepage: URL: http://www.org2.com email: jaap@org2.com