From hoey@aic.nrl.navy.mil Fri Jan 10 18:35:28 1992 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA29653; Fri, 10 Jan 92 18:35:28 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA00290; Fri, 10 Jan 92 18:32:36 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 10 Jan 92 18:32:35 EST Date: Fri, 10 Jan 92 18:32:35 EST From: hoey@aic.nrl.navy.mil Message-Id: <9201102332.AA13941@sun13.aic.nrl.navy.mil> To: tjj@lemma.helsinki.fi (Timo Jokitalo), Cube-Lovers@life.ai.mit.edu Subject: Re: Rubik's Cube, the minimax number of moves Keywords: Upper-Bounds, Thistlethwaite, RCC, NoRMC tjj@lemma.helsinki.fi (Timo Jokitalo) asks > I wonder how large the necessary tables for Thistlethwaite's method > for the cube are? I seem to recall reading that there were a few > hundred entries.... Well, this is the information from Singmaster's _Notes_on_Rubik's_ _Magic_Cube_ (1980). Thistlethwaite's method is to work from group to subgroup as follows: G0: G1: G2: G3: G4: The following table shows the number of cosets (the index of each subgroup in the next larger group). Then I include the number of HT moves proven, anticipated, and best possible, from the 1980 N_o_R_M_C. Finally, I include the number of HT claimed in the 1987 R_C_C. It is interesting to note that the improvement did not occur where Thistlethwaite anticipated it. Step | Number of Cosets | Number of HT, 1980 | #HT, 1987 | | Proven Anticipated Best | Proven | | | 1 | G0:G1 = 2,048 | 7 7 7 | 7 2 | G1:G2 = 1,082,565 | 13 12 10 | 13 3 | G2:G3 = 663,552 | 15 14 ? 13 ? | 15 4 | G3:G4 = 29,400 | 17 17 15 ? | 15 -----+-------------------+-----------------------------+----------- Total HT | 52 50 ? 45 ? | 50 Total QT | 101 97 ? 87 ? | 97 I had thought the tables contained one entry for each coset, and so there would be over a million entries for step 2. However, I was surprised just now to notice in N_o_R_M_C that tables were only needed in step 4, and then only 172 entries, so there must be some abbreviation or algorithmic approach. Of course, when Knuth's students improved step 4, they may have changed it to use a huge lookup table; I don't know. Still, this is much better than the situation I expected in my note two days ago. In listing QT I assume that in we can require steps 1, 2, and 3 to each end with a quarter-turn. So the number of QT is at most three less than twice the number of HT. > And, more important, have they been published, or does anyone have > them in an electronic format? The bibliography in N_o_R_M_C mentions Thistlethwaite's algorithms as being in typescript, but I don't know if they were available by request, and I don't know anyone who has them. I don't know anything about the improvements by Knuth's students, and there's nothing in the R_C_C bibliography that looks like a Stanford tech report. Dan