To: CUBE-LOVERS@ai.mit.edu
Date: Thu, 30 Jan 1997 19:04:34 -0500
X-Mailer: Microsoft Internet Mail 4.70.1160
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="----=_NextPart_000_01BC0EE0.6E7ED400"
Content-Transfer-Encoding: 7bit
This is a multi-part message in MIME format.
[ And the moderator really wishes that people would -not- use MIME when
mailing to Cube-Lovers. It makes the archives considerably less useful.
- Alan (Cube-Lovers-Request) ]
------=_NextPart_000_01BC0EE0.6E7ED400
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
>Taco Bell has a number of toys for sale commemerating the Star
>Wars re-release. One of these toys is a 2x2x2 cube.
I checked into this, but it is not a real 2x2x2 magic cube. It is
one of those folding cube puzzles, where you can turn the
whole thing inside out and it has different graphics on each
assembled exterior.
Too bad though! An official Star Wars 2x2x2 Rubik's Cube would
really be a find!
ck1@flnet.com
http://www.flnet.com/~ck1/cubes.html
------=_NextPart_000_01BC0EE0.6E7ED400
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
>Taco Bell has a number of toys for =
sale commemerating the Star

>Wars re-release. One of these =
toys is a 2x2x2 cube.

I checked into this, but it is not a real =
2x2x2 magic cube. It is

one of those folding cube puzzles, =
where you can turn the

whole thing inside out and it has different =
graphics on each

assembled exterior.

Too bad though! An =
official Star Wars 2x2x2 Rubik's Cube would

really be a =
find!

ck1@flnet.com

http://www.flnet.com/~ck1/cubes.html

------=_NextPart_000_01BC0EE0.6E7ED400--
From cube-lovers-errors@curry.epilogue.com Mon Feb 3 01:23:19 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id BAA04774; Mon, 3 Feb 1997 01:23:19 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Sun, 2 Feb 1997 23:39:34 -0500 (EST)
From: Nicholas Bodley
To: Dennis Okon
cc: Cube-Lovers@ai.mit.edu
Subject: Re: Broken Cube
In-Reply-To: <9701281647.AA05417@MIT.MIT.EDU>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Realistically, IMHO, the only practical thing is to buy another. There
are several makes in existence, and they have at least minor detailed
differences in dimensions. I'd love to say something different! If,
however, you can find someone who's an expert plastic welder (no kidding),
such a person might be able to do a repair.
In any event, good luck!
|* Nicholas Bodley *|* Electronic Technician {*} Autodidact & Polymath
|* Waltham, Mass. *|* -----------------------------------------------
|* nbodley@tiac.net *|* When the year 2000 begins, we'll celebrate
|* Amateur musician *|* the 2000th anniversary of the year 1 B.C.E.
--------------------------------------------------------------------------
From cube-lovers-errors@curry.epilogue.com Mon Feb 3 17:42:34 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id RAA06909; Mon, 3 Feb 1997 17:42:34 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <32F66942.50AF@ibm.net>
Date: Mon, 03 Feb 1997 14:40:02 -0800
From: Jin "Time Traveler" Kim
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: Dennis Okon
CC: Cube-Lovers@ai.mit.edu
Subject: Re: Broken Cube
References:
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
As it so happens, I have a spare 'cube' which met with unfortunate
incident a number of years ago. Let's just say it involved a hacksaw
and a misguided attempt at.... modification.....
Anyway, if you're so inclined, I have no problems mailing you the center
piece if you really want it.. But like someone else said, you'd do just
as well buying a new one. And besides, the center piece may turn out to
be just a little bit off kilter. I think it was a knock-off.
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@curry.epilogue.com Wed Feb 5 15:45:07 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA01726; Wed, 5 Feb 1997 15:45:07 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Wed, 5 Feb 1997 18:19:35 +0200 (IST)
From: Rubin Shai
To: Cube-Lovers
Subject: Magazines about the Rubik cube
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Hi all
I'm going to write a report about a program that learn to solve the 2X2X2
Rubik cube by itself.
Does anyone know a magazine that will publish this kind of stuff?
Shai
From cube-lovers-errors@curry.epilogue.com Thu Feb 6 14:38:30 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id OAA03750; Thu, 6 Feb 1997 14:38:30 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <32F99BFC.7299@ibm.net>
Date: Thu, 06 Feb 1997 00:53:16 -0800
From: Jin "Time Traveler" Kim
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: Dennis Okon
CC: cube-lovers@ai.mit.edu
Subject: Re: Broken Cube
References: <9702032332.AA09252@MIT.MIT.EDU>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Dennis Okon wrote:
>
> It would be wonderful if you could mail it to me. And, actually I have two
> cubes with broken centers - one of the original type and one of the plastic
> snap in tiles, which apparently (from inspection) both have the same size
> centers.
>
I will mail you the piece as promptly as possible. I recently moved
into a new residence days ago, so you will have to bear with me as I
hunt for my puzzle box and hope that I didn't throw away my ravaged cube
in a fit of....confusion?
> Also, I'm interested in hearing more specifically what the modification you
> mentioned was. The hack sent my mind in all sorts of directions.
>
>
You want to hear the ugly truth? Ugh... Ok.. while thumbing through
Dr. Christoph Bandelow's excellent cube catalog (1992 edition, I think),
I stumbled upon an object called the "Fisher Cube," in which each
handmade cube had a unique "cut" to it. Basically on a standard cube
the "groove" lines run parallel to the faces of the cube. On fisher's
cube, two opposite faces had the groove lines running diagonally, which
meant that a scrambled cube looked absolutely jacked up. I got this
brilliant idea that I could make something similar, so out came the
hacksaw.... After about an hour and a half of cutting I realized that I
had completely ruined a perfectly good cube. And my bedroom floor (and
desk, and bed, and lamp, and clothes, etc....) was COVERED in black
plastic shavings which, despite their strangely appealing odor, had
managed to make a terrible mess. So after giving myself disgusted looks
into a mirror (as a form of "self scolding," if you will) I packed all
the pieces away, thinking that maybe someday I would take the Time to
reassemble it or fix it somehow. After acquiring 4 more cubes over a
period of 5 years, I have lost interest in that project.
Soooo, that's it. Nothing particularly drastic, but I think it might be
worth a chuckle or two to those of the mailing list, so what started as
a personal email has become my own public shame. So I also hope you
won't have a problem with your "private email" being part of this drawn
out response.
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
P.S. If I find it, you want the whole mess or just the middle?
From cube-lovers-errors@curry.epilogue.com Thu Feb 6 14:36:14 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id OAA03746; Thu, 6 Feb 1997 14:36:14 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-Id: <9702060020.AA18875@jrdmax.jrd.dec.com>
Date: Thu, 6 Feb 97 09:20:10 +0900
From: Norman Diamond 06-Feb-1997 0916
To: cube-lovers@ai.mit.edu
Subject: Re: Magazines about the Rubik cube
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=ISO-2022-JP
Rubin Shai wrote:
>I'm going to write a report about a program that learn to solve the 2X2X2
>Rubik cube by itself.
>Does anyone know a magazine that will publish this kind of stuff?
Shouldn't the program be smart enough to answer that question for you? :-)
It would obviously be of interest in Cubism For Fun, the journal of the
Dutch Cube Society (which has been published in English for about the past
10 years or so). I don't think you'd get paid for it, but the audience
would be right.
I would guess that Scientific American, Journal of Recreational Mathematics,
and Games might also be suitable, depending on possible characteristics of
the program.
-- Norman Diamond diamond@jrdv04.enet.dec-j.co.jp
[Speaking for Norman Diamond not for Digital.]
From cube-lovers-errors@curry.epilogue.com Sun Feb 9 17:45:35 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id RAA12140; Sun, 9 Feb 1997 17:45:34 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Sun, 9 Feb 1997 16:54:42 -0500 (EST)
From: Dale Newfield
Reply-To: DNewfield@cs.virginia.edu
To: cube-lovers@ai.mit.edu
Subject: Re: Broken Cube
In-Reply-To: <32F99BFC.7299@ibm.net>
Message-Id:
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
On Thu, 6 Feb 1997, Jin Time Traveler Kim wrote:
> I got this brilliant idea that I could make something similar, so out
> came the hacksaw.... After about an hour and a half of cutting I
> realized that I had completely ruined a perfectly good cube.
I finally got around to building a bandaged pair of cubes
XXX
XXX
XXXXX
XXX
XXX
and a bandaged 5-cube
XXX XXX
XXX XXX
XXXXXXX
XXX
XXXXXXX
XXX XXX
XXX XXX
I agree--the process was very painful and very full of black shavings,
but now that I am done, I am very pleased with the final result. :-)
The impetus for this fit of cube-construction came from the book "The
book of ingenious & diabolical puzzles" by Jerry Slocum and Jack Botermans.
Also resulting from the same fit are a round cube with what look like two
2x2x2's sticking out of it, and a regular cube in which two opposite
corners and all the adjacent pieces are round.
All of these came after taking a good look at pages 124 and 125 of this
book--a page full of a very interesting collection of sequential movement
puzzles. Thie is a really neat book that will make any collector drool,
so keep your eyes out for it :-)
-Dale
From cube-lovers-errors@curry.epilogue.com Mon Feb 10 15:31:13 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA14099; Mon, 10 Feb 1997 15:31:13 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: Re: Broken Cube
Date: 10 Feb 1997 01:18:36 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5dlt1c$baq@gap.cco.caltech.edu>
References:
X-Newsreader: NN version 6.5.0 #2 (NOV)
Dale Newfield writes:
>The impetus for this fit of cube-construction came from the book "The
>book of ingenious & diabolical puzzles" by Jerry Slocum and Jack Botermans.
>All of these came after taking a good look at pages 124 and 125 of this
>book--a page full of a very interesting collection of sequential movement
>puzzles. Thie is a really neat book that will make any collector drool,
>so keep your eyes out for it :-)
I believe Jerry is still selling copies of his books.
Write to him at
257 S. Palm Dr.,
Beverly Hills, CA 90212
(310)273-2270 FAX (310)274-3644
70410.1050@compuserve.com
and ask him to send you a flier of books and prices (nicely).
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
Save the earth. Then Quit and Shut Down.
From cube-lovers-errors@curry.epilogue.com Tue Feb 18 20:39:25 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id UAA04696; Tue, 18 Feb 1997 20:39:25 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
From: Stan Isaacs
Message-Id: <199702190137.AA255196278@hpcc01.corp.hp.com>
Subject: Super-skewb
To: cube-lovers@ai.mit.edu
Date: Tue, 18 Feb 1997 17:37:57 PST
X-Mailer: Elm [revision: 109.19]
Anybody have any good moves for super-skewb centers? That is, ones
that either twist centers in place, or move them without twisting.
Tony Fisher, in England, makes some wonderful puzzles based on the
Skewb, but in shapes such as an Icosahedron, or Dodecahedron, or
Rhombic Dodecahedron. These are all actually Super-Skewbs.
-- Stan Isaacs
From cube-lovers-errors@curry.epilogue.com Thu Feb 20 01:42:04 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id BAA09922; Thu, 20 Feb 1997 01:42:03 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <330BCC51.7CD7@ibm.net>
Date: Wed, 19 Feb 1997 20:00:17 -0800
From: Time Traveler
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: Stan Isaacs
CC: cube-lovers@ai.mit.edu
Subject: Re: Super-skewb
References: <199702190137.AA255196278@hpcc01.corp.hp.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Stan Isaacs wrote:
>
> Anybody have any good moves for super-skewb centers? That is, ones
> that either twist centers in place, or move them without twisting.
> Tony Fisher, in England, makes some wonderful puzzles based on the
> Skewb, but in shapes such as an Icosahedron, or Dodecahedron, or
> Rhombic Dodecahedron. These are all actually Super-Skewbs.
>
> -- Stan Isaacs
Tony Fisher still makes those things? It's HIS fault that I hacked one
of my cubes into fine powder! Ah, yes. A GOOD memory. :)
Happen to know how to get a hold of him?
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@curry.epilogue.com Thu Feb 20 13:45:33 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id NAA11182; Thu, 20 Feb 1997 13:45:33 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: IPP17?
Date: 20 Feb 1997 16:11:44 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5eht40$kmk@gap.cco.caltech.edu>
NNTP-Posting-Host: triskaideka.ugcs.caltech.edu
X-Newsreader: NN version 6.5.0 #3 (NOV)
Anyone on the mailing list going to the International Puzzle
Collector's Party in San Francisco?
It's be nice to meet some more people I know there...
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
Now surfing the Internet at 24 hours a week.
From cube-lovers-errors@curry.epilogue.com Thu Feb 20 17:01:07 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id RAA11888; Thu, 20 Feb 1997 17:01:06 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
From: Stan Isaacs
Message-Id: <199702202137.AA029444678@hpcc01.corp.hp.com>
Subject: Re: Super-skewb
To: Cube-Lovers@ai.mit.edu
Date: Thu, 20 Feb 1997 13:37:57 PST
X-Mailer: Elm [revision: 109.19]
Several people asked how to get the so-called "Super-skewbs" (the name
is from an earlier cube-lovers message, not from Tony Fisher.) They
are made by hand, by Tony Fisher (see below). He has about 9 puzzles,
and says he plans to have some new ones later this year. He makes
them by glueing parts onto Skewbs. The results, I think, are
excellent. One corner broke off of one of the puzzles I got, but is
easily glued back on. They move nicely (which means, I think, that
the original Skewbs moved nicely.) He says he just buys them in
shops, and then makes the transformations at home. They mostly cost
around $60 - $75 (American), although a triple 5x5x5 is $90, and a
mini-octahedron is $40. I don't know if these are permanent prices;
they may change if prices of the cubes (or plastic) goes up. besides
the skewb variations, he as "Siamese" versioin of both the skewb and
the 5x5x5 cube (ie, he combines two into one; I don't have these, so I
don't know exactly how the Siamese Skewb works.) He also has a Triple
"Triamese 5x5x5", and a mini-octahedron based on the Tetraminx (which
I also want to get a copy of. His address is:
Tony Fisher
9 Cauldwell Hall Road
Ipswich, Suffolk, IP4 4QD, Great Britain
I guess I ought to put the list of puzzles for clarity:
Skewb variations:
Icosahedron - $60
Dodecahedron - $60
Rhombic-Dodecahedron - $60
Octahedron - $55
Siamese Skewbs - $60
Mental Block - $75 (A strange object: looks like a 1x3x3
block, with 9 even squares on the top and bottom, but the edges are
cut by an 'X' in the middle, so there are 2 triangles and 2 pentagons
on each edge. When twisted, it makes all sorts of strange shapes.)
Siamese 5x5x5 - $75
Triamese 5x5x5 - $90
Mini-Octahedron (based on Tetraminx) - $40
Dave Singmaster pointed out that the instructions for "Sonic's Puzzle
Ball", but Christoph Bandalow, has some super-skewb moves in it. I've
just glanced at it, so I haven't had a chance to try them yet. He
seems to have about 3 moves that twist pairs of squares (and some
triangles), of lenght 10, 14 or 18.
-- Stan isaacs
-- isaacs@corp.hp.com
From cube-lovers-errors@curry.epilogue.com Fri Feb 21 13:46:38 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id NAA13909; Fri, 21 Feb 1997 13:46:38 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: Re: Super-skewb
Date: 21 Feb 1997 16:47:06 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5ekjia$as@gap.cco.caltech.edu>
References:
NNTP-Posting-Host: taphe.ugcs.caltech.edu
X-Newsreader: NN version 6.5.0 #3 (NOV)
Stan Isaacs writes:
>Anybody have any good moves for super-skewb centers? That is, ones
>that either twist centers in place, or move them without twisting.
>Tony Fisher, in England, makes some wonderful puzzles based on the
>Skewb, but in shapes such as an Icosahedron, or Dodecahedron, or
>Rhombic Dodecahedron. These are all actually Super-Skewbs.
If I remember correctly, all my moves for the Skewb are based on
the "R1L-1R-1L1" move. Repeating this four-move sequence at
different orientations does everything, including rotating centers
and moving them.
Unfortunately, I don't have any on hand at the moment, so I can't
test them out exactly.
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
Now surfing the Internet at 24 hours a week.
From cube-lovers-errors@curry.epilogue.com Fri Feb 28 13:51:54 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id NAA12878; Fri, 28 Feb 1997 13:51:54 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID:
From: "joyner.david"
To: "'cube-lovers@ai.mit.edu'"
Subject: impossiballs
Date: Fri, 28 Feb 1997 13:38:46 -0500
X-Mailer: Microsoft Exchange Server Internet Mail Connector Version 4.0.837.3
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Does anyone know of any impossiballs for sale in a
>store in the US? - David Joyner
>
From cube-lovers-errors@curry.epilogue.com Sat Mar 1 01:52:20 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id BAA00371; Sat, 1 Mar 1997 01:52:20 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <33176FB7.60E5@ibm.net>
Date: Fri, 28 Feb 1997 15:52:23 -0800
From: Time Traveler
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: "joyner.david"
CC: "'cube-lovers@ai.mit.edu'"
Subject: Re: impossiballs
References:
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
joyner.david wrote:
>
> Does anyone know of any impossiballs for sale in a
> store in the US? - David Joyner
>
Try Peter Beck of New Jersey. I don't remember his address (my address
book program was lost along with EVERYTHING else in a hard drive crash)
but I've seen his name on a list or two of puzzle sources. The last
Time I bought puzzles from him (ohh... about 3 years ago) he had ONE
used Impossiball available. But who knows, maybe things have improved
since then.
Speaking of which, does anyone know where I can get my hands on a
Rubik's Revenge? I saw some for sale at www.puzzlett.com, but someone
said that they were an unreliable source (i.e. they ripped him off).
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
[ Note from the moderator:
Peter Beck's electronic mail address is: pbeck@pica.army.mil
- Alan (aka Cube-Lovers-Request@AI.MIT.EDU) ]
From cube-lovers-errors@curry.epilogue.com Sun Mar 2 02:53:57 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id CAA04211; Sun, 2 Mar 1997 02:53:56 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Sun, 02 Mar 1997 00:50:27 -0500 (EST)
From: Jerry Bryan
Subject: An Enhancelment for Shamir with M-conjugacy
To: Cube-Lovers
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
Content-transfer-encoding: 7BIT
I now have a functioning Shamir program. I do not consider it quite up to
production quality just yet. I am still working on a number of
improvements. Also, all the results that are easily accessible to the
program have already been calculated by other means, so I have no new
search results to report at this time. I do expect some new results from
time to time, but the runs will probably take weeks or months. However,
in the process of developing the program, I came up with an enhancement
which I wished to report.
Recall that the heart of the Shamir method is a mechanism which will for
all s in S and all t in T produce all products st in lexicographic order.
This basic mechanism can be applied in a number of ways. For example, it
can be applied to the problem of determining a minimal solution for a
particular position. It can also be applied to the problem of conducting
a breadth first exhaustive search. The former is the basic method
developed by Shamir and first reported to this group by Alan Bawden. The
latter is the problem which I am currently addressing.
As already reported in several previous messages, my implementation of
Shamir seeks to incorporate M-conjugacy to the maximum extent possible to
reduce memory requirements. As such, it does not store the sets S and T.
Rather, it stores the sets A and B, where A and B contain only
representative elements of the M-conjugacy classes which are contained in
S and T, respectively.
A and B are about 48 times smaller than S and T. However, we cannot
obtain any meaningful results using only A and B. Rather, A and B have to
be expanded by M-conjugation to produce S and T. That is, we represent S
as A^M and T as B^M. There are no fewer positions, but only three bytes
or so are required to represent each position in A^M and B^M. So we
produce products st in lexicographic order for s in A^M and t in B^M.
This model is slow, but it is small.
At the back end of the algorithm, we determine which st values are
representatives and which are not. Those which are, we keep. Those which
are not, we simply discard. In my earlier messages about combining Shamir
with M-conjugacy, I lamented the difficulty of producing representatives
in lexicographic order. Simply discarding non-representatives is a crude
but effective way to accomplish the goal. It is not quite as good as not
producing the non-representatives in the first place, but it is a good bit
better than nothing.
As an example of the "better than nothing" idea, the Shamir method does
not directly produce ST in lexicographic order. Rather, it produces St in
lexicographic order for each t in T. The results then have to be merged.
The non-representatives are discarded prior to the merge, so that 48 times
fewer positions have to be merged. Also, the products st are tested byte
by byte as they are produced to determine if they are representatives. It
is usually possible to determine that a position is not a representative
after no more than two or three bytes, so there are some efficiencies in
the process of discarding non-representatives. That is, the only products
st which are calculated in their entirety are those for representatives.
The enhancement I want to report is that it is possible to discard entire
branches of the Shamir tree without examining any of the nodes in the
branch except the root of the branch. That is, it is possible to show
that entire branches of the tree contain only non-representatives. Such
branches can be pruned from the search without examining any of the nodes
individually. Approximately 47/48 of the search tree can be eliminated
from the search tree in this manner. Unfortunately, the speed up is not
times forty-eight as I hoped, but it is significant nonetheless.
The model is an S24xS24 model with S24 acting on 0..23. The corners are
therefore vectors of the form [a,b,c,....], which means 0->a, 1->b, 2->c,
etc. The identity is [0,1,2,....]. We focus on the corners because we
consider the order of the corners first in our lexicographic order, using
the order of the edges only to break ties on the corners. We call a
representative element of each M-conjugacy class a canonical form, and all
other elements we call non-canonical.
The nature of the Shamir search is that it produces successively more
complete partial permutations as a tree is searched. That is, it produces
[a,?,?,...] at the zeroth level of the tree, [a,b,?,?,...] at the first
level of the tree, [a,b,c,?,?,...] at the second level of the tree, and so
forth until a complete permutation is constructed.
The enhancement to the method consists of determining which of the partial
permutations are canonical, which are non-canonical, and which are
neither. A partial permutation is canonical if all daughter nodes are
canonical, a partial permutation is non-canonical if all daughter nodes
are non-canonical, and a partial permutation is neither if there are
daughter nodes of both types.
>From a theoretical point of view, the type of each node could be
determined by examining each daughter and backing up the results
appropriately, similar to an alpha-beta search. From a practical point of
view, the whole purpose is to determine the type of node without examining
any of the daughters. And in practice, we only detect non-canonical nodes
vs. other than non-canonical nodes. There is no disadvantage to this
procedure because it is only the non-canonical nodes which we wish to
eliminate from the search.
Determining non-canonical nodes depends both on the particular numbering
scheme which is used for the cube facelets and also upon the particular
representative element function which is chosen. We number the Front
corner facelets of the cube as follows:
0 1
3 2
The Back corner facelets are then numbered 4..7, with opposite facelets
summing to 7. All other facelets are numbered by adding 8 to the Front or
Back facelet as you look at the facelets of the cubie in clockwise order.
For example, the flt cubie is (0,8,16), and the ftr cubie is (1,9,17).
The representative element function returns the M-conjugate which of all
the elements in the M-conjugacy class is first in lexicographic order.
Consider the partial permutation [0,?,?,...]. Its M-conjugates are of the
form [?,1,?,?...], [?,?,2,?,?,...], [?,?,?,3,?,?,...], etc. It is easy to
see that if a representative begins with 0, then there is at least one of
the eight corner cubies somewhere in the cube which is properly
positioned, both with respect to location and with respect to twist.
Also, it is easy to see that the partial permutation [0,?,?,...] has both
canonical and non-canonical forms as daughters.
But consider the partial permutations [1,?,?,...] and [3,?,?,...]. They
are conjugate, but the canonical form is [1,?,?,...]. Hence, no canonical
form can begin with 3. Therefore, we eliminate all permutations which
begin with 3 from the search, and we have eliminated 1/24 of the search
tree.
I have calculated a table of non-canonical cutoff points for the corners.
The results are as follows. Notice that not all cutoffs are at the zeroth
level of the tree as is the cutoff for 3, but nonetheless there are 17
cutoffs at the zeroth level. That means that there are only 7 (out of 24)
ways to begin a canonical permutation.
Level Noncanonical Positions
Nodes Trimmed
i= 0 count= 17 62460720
i= 1 count= 63 11022480
i= 2 count= 487 4733640
i= 3 count= 7610 4931280
i= 4 count= 17830 962820
i= 5 count= 138978 833868
i= 6 count= 622745 622745
Total trimmed 85567553
The positions trimmed figure is based on a corners only search, just to
give a sense of proportion to the numbers. The corners only group
contains about 88 million positions. For the complete cube, the numbers
would be larger, but the proportions would be the same.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7127
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@curry.epilogue.com Thu Mar 6 15:48:05 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA01483; Thu, 6 Mar 1997 15:48:05 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
From: bagleyd
Message-Id: <199703061759.MAA19236@megahertz.njit.edu>
Subject: winpuzzles and xpuzzles
To: cube-lovers@ai.mit.edu
Date: Thu, 6 Mar 1997 12:59:28 -0500 (EST)
X-Mailer: ELM [version 2.4 PL24]
Content-Type: text
Hi
I made a new release of my puzzles.
They are available for Windows 3.1 and above at
http://megahertz.njit.edu/~bagleyd/
as
winpuz64.zip
source is available also for each puzzle.
For X
ftp://sunsite.unc.edu//pub/Linux/games/x11/strategy/xpuzzles-5.4.1.tgz
Also available at the site below, you may need a mirror though to get it from
ftp.x.org since they only allow 50 users.
They puzzles include:
I updated all the txt/manual files. So they now contain a little history
of the origins of each with references.
Fixes for the Masterball
Auto solve capability for Panex thanks to Rene Jansen
(based on the algorithm in Quantum Jan/Feb 96).
Panex with 3 tiles on each side is known to be solvable in 42 moves
The version here solves it in 45. Rene and I would both like to improve this.
For the X versions I added: Username, concurrency check, configure
--
Cheers,
/X\ David A. Bagley
// \\ bagleyd@bigfoot.com http://megahertz.njit.edu/~bagleyd/
(( X xlockmore, new stuff for xlock @ ftp.x.org//contrib/applications
\\ // altris, tetris games for x @ ftp.x.org//contrib/games/altris
\X/ puzzles, magic cubes for x @ ftp.x.org//contrib/games/puzzles
From cube-lovers-errors@curry.epilogue.com Sat Mar 8 21:56:13 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id VAA08731; Sat, 8 Mar 1997 21:56:13 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
From: Mitch269@aol.com
Date: Sat, 8 Mar 1997 21:37:53 -0500 (EST)
Message-ID: <970308213750_1383812770@emout11.mail.aol.com>
To: Cube-Lovers@ai.mit.edu
Subject: RUBIK'S CUBE/RUBIK'S REVENGE
Does anyone know of an address I could send to order Rubik's Puzzles? I
can't seem to find either one anywhere. Thanks.
Mitch Brewer
mitch269@aol.com
From cube-lovers-errors@curry.epilogue.com Sun Mar 23 14:19:14 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id OAA02111; Sun, 23 Mar 1997 14:19:14 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-Id: <199703231549.QAA15923@sun529.rz.ruhr-uni-bochum.de>
Comments: Authenticated sender is
From: bandecbv@rz.ruhr-uni-bochum.de
To: cube-lovers@ai.mit.edu
Date: Sun, 23 Mar 1997 17:47:14 +0000
MIME-Version: 1.0
Content-type: text/plain; charset=ISO-8859-1
Content-transfer-encoding: Quoted-printable
Subject: Super-skewb
Priority: normal
X-mailer: Pegasus Mail for Windows (v2.42a)
> Anybody have any good moves ... (Stan Isaacs, 19 Feb 1997)
> Several people asked ... (Stan Isaacs, 20 Feb 1997)
>
Hi, Cube-Lovers!
My name is Chistoph Bandelow, and I am new in this exclusive club.
Having finally aquired a modem and the necessary software a few weeks
ago, I'm still overwhelmed and confused by everything. I have read
all the contributions from July 1996 till now and the complete "Index
by Subject".
To begin with something, I would like to make some remarks about the
Skewb, especially the wonderful Skewb variations made by Tony Fisher. I
suggest to call them "Fisher's Icosahedron", "Fisher's Dodecahedron", and
so on..Owing all of these puzzles, I am very enthusiastic because of their
originality and first-class quality. Just in case you are considering to
acquire one or the other from him: Tony Fisher is a very reliable, modest
and decent person.
THE SKEWB has been first described to a larger public by Douglas R.
Hofstadter in the July 1982 edition of Scientific American. This
treatise is included in Hofstadter's book "Metamagical Themas" (Basic
Books 1985 and Bantam Books 1986). It was here where Hofstadter
suggested the name 'skewb' as a reminder of skew and cube.
One of the wonderful features of the Skewb is that we don't have to
quarrel how to count single moves: no trouble with outer layer moves
versus slice moves or with 90=B0 moves versus 180=B0 moves, there is just
one type of move rotating one half of the Skewb by 120=B0 against the
other half.
>From 1985 to 1988 I had an intensive correspondence with Ronald
Fletterman where I used the following
NOTATION: Hold the (ordinary cubical) Skewb such that there is a
unique Right upper corner, Left upper corner, Front upper corner and
Back upper corner. R, L, F and B respectively denote a clockwise 120=B0
rotation of the associated half cube (as seen from the outside). R',
L', F' and B' denote counterclockwise turns. Small letters r, l and
so on are used for rotations around the bottom corners. Though this
notation is short and handy, it is probably not as good as the one
used by D. J. Joyner in his Skewb page (see
http://www.nadn.navy.mil/MathDept/wdj/rubik.html)
But I stick on my old notation, especially after Ronald Fletterman,
used this notation in two papers in CFF (Cubism For Fun, the
newsletter of the Dutch Cubist Club) in which he provides an
enormous collection of Skewb maneuvers, see CFF 17 (May 1988) and
CFF 18 (September 1988). The square center pieces of the Skewb can
only rotate pairwise and only by 180=B0, not by 90=B0. Ronald
Fletterman's collection covers these "invisibles". He, the
perfectionist, gives maneuvers for all 5 possible cases: 2
neighboring squares, 2 opposing squares, 4 squares all but 2
neighborings, 4 squares all but 2 opposing, all 6 squares. However,
all his other maneuvers (those for the corner pieces of the Skewb)
pay absolutely no heed to the orientation of the center pieces. Every
short and elegant solution method for the new Skewb variations of
Tony Fisher or for the beautiful round versions of the Skewb like
Mickey's Challenge or Sonic's Puzzle Ball or the Mach Balls require
maneuvers for the corner pieces which do not twist the center pieces.
Some of those maneuvers are given in my 80 page booklet about
Mickey's Challenge or about Sonic's Puzzle Ball or on the leaflets
accompanying some other puzzle balls from Meffert. Here is a
selection:
SOME SUPER SKEWB MANEUVERS.
1. (FL'R)^6 (18) twists the 2 neighboring squares on the left side.
2. R'BLF'L'FRLB'R'FRF'L' (14) achieves the same thing.
3. FfRr'f'FfF'R'f'rRF'R' (14) twists the top and bottom square.
4. (RF')^2 (R'F)^2 (8) twists the four top corner pieces:
... the right and front one clockwise, the left and back one counter-
... clockwise, in short: (+R) (+F) (-L) (-B).
5. R'FR' (F'R)^2 fF'f (Ff')^2 (14) twists 2 corner pieces: (+R)(-L)
6. rF'rfR'F'rfR'r'F (11) twists the top front corner piece clockwise
... and exchanges (3-cycles) the 3 neighboring corner pieces,
... in short: (+F) (L,R,f). The very last notation does not precisely
... describe the effect of the maneuver since the orientation of the
... three corner pieces is not given. A remarkable and fundamental
... difference between Rubik's Cube and the Skewb is that the Skewb
... does not allow pure corner-3-cycles: It is impossible to achieve
... (L,R,f) without any other corner piece change!
CALL TO CUBE-LOVERS: I'm convinced that the maneuvers given above,
especially number 2, 3 and 5, may be improved. Who can give shorter
maneuvers or a good maneuver for (+L) (+R) (+f) ?
PROPAGANDA. One last remark: I don't want to offend the good rules of
netiquette by doing any kind of advertising here. But to avoid
unnecessary questions and loss of time, allow me to say that I will
send my free mail order cube catalog (1996 edition, this is still the
latest) to everybody who requests one and provides his postal
address.
Christoph
Christoph Bandelow
mailto:Christoph.Bandelow@rz.ruhr-uni-bochum.de
From cube-lovers-errors@curry.epilogue.com Thu Mar 27 11:43:20 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id LAA12287; Thu, 27 Mar 1997 11:43:20 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Thu, 27 Mar 1997 04:56:51 -0500 (EST)
From: Nicholas Bodley
To: bandecbv@rz.ruhr-uni-bochum.de
cc: cube-lovers@ai.mit.edu
Subject: "Propaganda": OK with me!
In-Reply-To: <199703231549.QAA15923@sun529.rz.ruhr-uni-bochum.de>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Here's one list recipient who thinks Christoph Bandelow was quite
courteous in his "propaganda"; I was quite glad to finally have a
convenient way to request his catalog. I hope he's not overwhelmed by
requests! As some (perhaps most) of you know, he has quite a reputation
(and a good one) already.
Christoph: It's fine with me! Next message (private) will be a
catalog request to you. Welcome to the 'Net!
|* Nicholas Bodley *|* Electronic Technician {*} Autodidact & Polymath
|* Waltham, Mass. *|* -----------------------------------------------
|* nbodley@tiac.net *|* When the year 2000 begins, we'll celebrate
|* Amateur musician *|* the 2000th anniversary of the year 1 B.C.E.
--------------------------------------------------------------------------
From cube-lovers-errors@curry.epilogue.com Thu Mar 27 14:21:52 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id OAA12601; Thu, 27 Mar 1997 14:21:52 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <333AC80B.4811@ibm.net>
Date: Thu, 27 Mar 1997 11:18:35 -0800
From: Time Traveler
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: Super-skewb
References: <199703231549.QAA15923@sun529.rz.ruhr-uni-bochum.de>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
bandecbv@rz.ruhr-uni-bochum.de wrote:
> PROPAGANDA. One last remark: I don't want to offend the good rules of
> netiquette by doing any kind of advertising here. But to avoid
> unnecessary questions and loss of time, allow me to say that I will
> send my free mail order cube catalog (1996 edition, this is still the
> latest) to everybody who requests one and provides his postal
> address.
>
> Christoph
> Christoph Bandelow
> mailto:Christoph.Bandelow@rz.ruhr-uni-bochum.de
I must vouch for Dr. Bandelow, as I had an opportunity to purchase a
number of pieces from him some years ago, specifically an intriguing
variant of the spherical skewb called the Moody Ball by Gerd Braun.
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@curry.epilogue.com Tue Apr 1 15:56:31 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA28238; Tue, 1 Apr 1997 15:56:31 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Tue, 1 Apr 1997 06:36:01 -0800 (PST)
Message-Id: <199704011436.GAA22709@f5.hotmail.com>
X-Originating-IP: [194.239.24.235]
From: Philip Knudsen
To: cube-lovers@ai.mit.edu
Subject: Greg's Cubes
Content-Type: text/plain
Hi everybody!
I'm Philip Knudsen, and i live in Copenhagen, Denmark. Last year i found out
about this list, and read most of the old messages. The past few months i have
subscribed to the list using a free email account at my library.
Now for my 1st message: Since the talk is of Fisher's Skewb variants (which
sound very interesting indeed), i would like to mention to those whom it might
interest, that Greg Stevens, Seattle, is making various types of cube variants.
I have one of his catalogues, and have also received from him an "Off Center
Cube".
His designs, about 12 different, seem to be in the following categories:
1) Bandaged Cubes, made from standard 3x3x3
2) Shape modifications, made from standard 3x3x3
3) 1) and 2) combined
4) Bandaged Square-1
5) Bandaged 4x4x4 (where did he get the raw material???)
6) Shape variations of Pyraminx, i.e. "Pyraminx Star"
The "Off Center-Cube" is a 3. It is well made, and very tough to solve. In fact
i still need to find out how to turn the center pieces, which by the way are
disguised as edge pieces.
Last but not least - Greg also is a very reliable and decent person.
If anyone's interested i shall forward his postal address to the list.
---------------------------------------------------------
Get Your *Web-Based* Free Email at http://www.hotmail.com
---------------------------------------------------------
From cube-lovers-errors@curry.epilogue.com Wed Apr 2 15:54:57 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA00887; Wed, 2 Apr 1997 15:54:57 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Wed, 2 Apr 1997 06:24:45 -0800 (PST)
Message-Id: <199704021424.GAA18542@f17.hotmail.com>
X-Originating-IP: [194.239.24.235]
From: Philip Knudsen
To: cube-lovers@ai.mit.edu
Subject: Greg's Cubes
Content-Type: text/plain
Greg is not online. His postal address is:
Greg Stevens,
313 N.E. 151st,
Seattle, WA 98155,
U.S.A.
I'll try and find his phone number too.
Good Luck! Philip K
---------------------------------------------------------
Get Your *Web-Based* Free Email at http://www.hotmail.com
---------------------------------------------------------
From cube-lovers-errors@curry.epilogue.com Wed Apr 2 15:54:25 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id PAA00883; Wed, 2 Apr 1997 15:54:25 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID:
From: "joyner.david"
To: "'cube-lovers@ai.mit.edu'"
Subject: RE: Greg's Cubes
Date: Wed, 2 Apr 1997 07:14:54 -0500
X-Mailer: Microsoft Exchange Server Internet Mail Connector Version 4.0.837.3
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
I have bought cubes from Greg Stevens and can second Philip Knutsen's
opinion about his reliability. - David Joyner
>----------
>From: Philip Knudsen[SMTP:philipknudsen@hotmail.com]
>Sent: Tuesday, April 01, 1997 9:36 AM
>To: cube-lovers@ai.mit.edu
>Subject: Greg's Cubes
>
>Hi everybody!
>
>I'm Philip Knudsen, and i live in Copenhagen, Denmark. Last year i
>found out
>about this list, and read most of the old messages. The past few months
>i have
>subscribed to the list using a free email account at my library.
>Now for my 1st message: Since the talk is of Fisher's Skewb variants
>(which
>sound very interesting indeed), i would like to mention to those whom
>it might
>interest, that Greg Stevens, Seattle, is making various types of cube
>variants.
>I have one of his catalogues, and have also received from him an "Off
>Center
>Cube".
>His designs, about 12 different, seem to be in the following
>categories:
>1) Bandaged Cubes, made from standard 3x3x3
>2) Shape modifications, made from standard 3x3x3
>3) 1) and 2) combined
>4) Bandaged Square-1
>5) Bandaged 4x4x4 (where did he get the raw material???)
>6) Shape variations of Pyraminx, i.e. "Pyraminx Star"
>
>The "Off Center-Cube" is a 3. It is well made, and very tough to solve.
>In fact
>i still need to find out how to turn the center pieces, which by the
>way are
>disguised as edge pieces.
>Last but not least - Greg also is a very reliable and decent person.
>If anyone's interested i shall forward his postal address to the list.
>
>
>
>
>---------------------------------------------------------
>Get Your *Web-Based* Free Email at http://www.hotmail.com
>---------------------------------------------------------
>
>
From cube-lovers-errors@curry.epilogue.com Thu Apr 3 12:16:11 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id MAA01927; Thu, 3 Apr 1997 12:16:11 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-ID: <01BC4004.EC0AAA20@p10.ts3.danve.MA.tiac.com>
From: Karen Angelli
To: "'Cube-Lovers@AI.MIT.EDU'"
Subject: Cube History: Triumph and Defeat
Date: Thu, 3 Apr 1997 07:58:25 -0500
A recent addition to the Cube-Lovers list, I would like to share one of
the least known events in the history of Cube entertainment, and its
repercussions in the mass media and ultimate disgrace of one of the most
powerful men in entertainment.
It was the early '80s and Rubik's-Cube-Mania was all the rage. Although
not nearly as accomplished as some of this list's members were, I could
solve the cube in about one minute. I was also a lifeguard at a public
pool, and a locally renowned under-water swimmer (with a personal best
of 75 meters). With such amazing and narrowly acclaimed accomplishments
in such diverse fields of endeavor, it was only natural that I would
feel public pressure to combine the two. Thus was born underwater cube
solutions.
I took my best lubricated cube, a dive mask and a weight belt, and
started solving the cube in 10 feet of water. After several practice
attempts, to ensure that I could hold my breath long enough to complete
the cube, I volunteered my services to the local synchronized swimming
club which was looking for an opening act for their show.
The show took place before a not so overflowing crowd during the busiest
season of the year, the local Nordic Fest celebration of Scandinavian
heritage. The international crowd of aquatic enthusiasts was stunned
when I was introduced. My bikini clad assistant handed the pristine
cube to one of the audience members to randomize and returned to me.
Then, in four and a half feet of water, I submerged and started solving
the cube.
After about 10 seconds of hurried twisting, I dropped the cube and lost
my place - I had to start over. In practice, it had never taken me more
than about 1 min, 15 seconds to solve the cube, and I had practiced
holding my breath comfortably for about 1 min, 25 seconds. I wasn't
sure whether I would complete the task. After about 1 min 30 seconds,
my sister started yelling for someone to help me. However, at the 1 min
38 second mark, I surfaced - to thunderous applause. Certainly one of
the greatest moments of cube history. How sad that this would lead to
infamy and no greater laurels.
After hearing the story of how I wowed a normally reserved Iowan crowd,
my classmates in college in Pennsylvania encouraged me to find a larger
audience, on a national stage. Naturally, I wrote to NBC's Late Night
with David Letterman to pitch my idea for a stupid human trick.
Uncharacteristically, however, Dave turned down a good idea. I haven't
forgiven him since.
I hope I haven't disappointed any Dave fans out there, but the truth had
to surface some day. Thanks for keeping the flame alive Cube-lovers.
Pete Reitan
From cube-lovers-errors@curry.epilogue.com Fri Apr 4 11:35:52 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id LAA04602; Fri, 4 Apr 1997 11:35:52 -0500
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Fri, 4 Apr 1997 09:28:08 -0500 (EST)
From: Jiri Fridrich
X-Sender: fridrich@bingsun2
To: Cube-Lovers@ai.mit.edu
Subject: Pretty patterns with Kociemba (help)
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
I would like to ask for your help to find short algorithms for some
pretty patterns below. The algorithms are just working algorithms and
are probably too long. Can anybody apply Kociemba's algorithm to
those positions?
The patterns form a small portion of a very large collection of
pretty patterns found by Mirek Goljan and Peter Nanasy from Czech
Republic. The algorithms below are the awkward "outliers" for which
we were unable to find a reasonably short "logical" algorithm. It
looks like Kociemba's algorithm is the only chance.
Thanks in advance for your help!
Jiri Fridrich
P.S.: Visit my speed cubing page at
http://ssie.binghamton.edu/~jirif. The complete collection of
pretty patterns will be there soon.
F'R2D'RsF RsF D'R2D F'L2F D'R2D2B LsU'F' 28,23,20 DLV
U'R B'R'U R'D2F U F U'F'D'U2BsLsD F 22,20,18 U4V
R2F'D'F2L F'R F R'aF'D B LsDsF'U2 22,19,17 U5V
F'R2D'RsF RsF D'R2D F'L2F D'R2D2F UsL'U' 28,23,20 LV
D B'L'B2L B D2B'L'B2L B D'L2B2D2 22,16 L'2
D2B2D2B2U2F2U R2U F2U2R2D R2D 26,15 L'8
FaR2F'aD'aR2U'F2D R2D2F2U F2U 24,17 L'9
D2F2L2U2D B R B2R'B'D2R'B'R2B R D 24,17 L'10
LsF2R2D'FsU'F2sDFsDR2F2Rs 24,18,13 [SS']
U L D R2U R U'R B'D B'D'B2D'L'U' 18,16 [VH]
R'D2R B'U2B R'D2R B'U2B . U B2L BsL2R'FsU2D L'B2U' [VHH']
R U'R B'D B'D'B L B'U R'U R U2B2R2L'U 22,19 [VSS']
LsF2R2D'FsU'F2sDFsDR2F'L'FsU F'U'BsR [SS'H]
U'R F'R'F L F'DsBsL U'R'D R D'F 18,18,16 [DOO']
U L D R2U R U'L DsBsR'B L'B'L2B'D'F' 22,20,18 [DVH]
LsF2R2D'FsU'F2sDFsDR2F'R'DsBR'F'LsU [DSS'H]
B'L'D L'U'BsLsU'R DsR'D R U R'D L 20,20,17 [DHOO']
B'L F'L2FsR'B R F'LsB'R B2L F L' 20,18,16 [VO]
LsU FsD F2sU'FsU'F L'FsU F'U'BsR 24,22,16 [SHH']
R'F2L'D'L F2B D B'D'FsL B L2D L F'R 22,19,18 [SS'O]
D'L F R U2L U2R2U2L'U R2U R'F'L'D 22,17 [VHO]
R'F'L BsD'F'D B'L'B L F R'DsBsR U 20,20,17 [DSO']
LsU FsD F2sU'FsU'F R'DsB R'F'LsU 24,22,16 [DSHH']
R'D B D R'DsB L B'U'aR B'D'R2B'D'R 20,19,18 [DVSO]
D F'UsL'DsF UsL2F'L DsF'LsD BsR'D B'R' 26,25,19 [DU3U4]
U L F'L DsF'LsD BsR'D LsU'L'U'F'aU'BsL F2U 28,27,22 [DU2U3]
R2sF2R2F2sR2F2.FD'L'DLD'L'DLD'L'DLF'
FD'L'DLD'L'DLD'L'DLF'. F2sR2sD F2sU2R2sD
D'F'D F DsB L'D L UsB'D'B R'F'D'F'D 20,20,18 [WORKS(14)]
U'B2RaU2R'B'U L'B UsR'B U'R B'DsB2R2U 26,22,20 [WS(14)S'(23)]
R D'F2D F'R F UsF DsF'R2D F D'R D F'D' 23,21,19 [ORKK'S(14)(23)]
R U'F R'B'D2R'U'BsLsD B L U'R'U'F U'Ls 23,22,19 [DK]
D'R'BULsB'UB'U'BL'BLB'UB'U'BRsDB'DsF'UsLB 30,30,26 giant meson 1
L D R2D'L2U B'D'B D'R'D R DsL D'B2D 22,19,18 giant meson 2
R2L'DBR'D'BLBL'D'B'D2LDL'U'FD'F'RFL'FLF2R'D2U
DFRsU'B'D'R'aD'LsBDFD2F2DF'R'B'L'DLBF2RD'R2D
Notation:
Ra = antislice RL, Fa = FB, etc.
Fs = slice move FB', Rs = RL', etc.
F2s = 180 deg. slice move, etc.
The three-tuple in the second column means the number of quarter,
face, and slice moves. You can Ignore the cryptic notation in square
brackets.
**********************************************************************
| Jiri FRIDRICH, Research Associate, Dept. of Systems Science and |
| Industrial Engineering, Center for Intelligent Systems, SUNY |
| Binghamton, Binghamton, NY 13902-6000, Tel.: (607) 797-4660, |
| Fax: (607) 777-2577, E-mail: fridrich@binghamton.edu |
| http://ssie.binghamton.edu/~jirif/jiri.html |
**********************************************************************
......................................................................
Remember, the less insight into a problem, the simpler it seems to be!
----------------------------------------------------------------------
From cube-lovers-errors@curry.epilogue.com Tue Apr 15 13:20:28 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id NAA18947; Tue, 15 Apr 1997 13:20:28 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Message-Id: <199704151245.NAA02212@mail.iol.ie>
From: Goyra
To: Cube-Lovers@ai.mit.edu
Subject: Java cubes
Date: Tue, 15 Apr 1997 10:53:27 +0100
X-MSMail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1155
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Yo!
The world's largest collection of Java
Rubik puzzles is now under construction at
http://www.iol.ie/~goyra/Rubik.html
All comments are appreciated. An up-to-date Java
browser is required.
Goyra
From cube-lovers-errors@curry.epilogue.com Fri May 9 15:02:56 1997
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA18562; Fri, 9 May 1997 15:02:55 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Fri, 09 May 1997 18:03:26 BST
From: David Singmaster Computing & Maths South Bank Univ
To: cube-lovers@ai.mit.edu
Message-ID: <009B402B.C196AB40.297@vax.sbu.ac.uk>
Subject: Underwater cube solving
I found the story in my Cubic Circular 1, p. 16. Pete promised to
marry his lady when she got down to 60 seconds, which wasn't too hard as she
was already at 70 seconds. Her name was Chris Clark. The TV recorded only
showed a lot of bubbles! One would need a underwater TV camera to get
antything interesting.
DAVID SINGMASTER, Professor of Mathematics and Metagrobologist
School of Computing, Information Systems and Mathematics
Southbank University, London, SE1 0AA, UK.
Tel: 0171-815 7411; fax: 0171-815 7499;
email: zingmast or David.Singmaster @sbu.ac.uk
From cube-lovers-errors@oolong.camellia.org Fri May 9 15:21:07 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA18614; Fri, 9 May 1997 15:21:07 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Fri, 09 May 1997 17:16:09 BST
From: David Singmaster Computing & Maths South Bank Univ
To: cube-lovers@ai.mit.edu
Message-ID: <009B4025.26B4C360.894@vax.sbu.ac.uk>
Subject: Underwater cube solving
I've been away from my email for some time and have just seen the
message of 3 Apr 1997 from Pete Reitan via Karen Angelli.
In England, we also had some underwater cube solving. This is probably
in my Cubic Circular somewhere, but I can't find it.
A lecturer in mathematics at the open University, Pete Strain, got
interested in the Cube when I brought early examples to the Open University in
early 1979. He got married about that time and took on the name Strain-Clark,
and his wife was also interested. They performed underwater for Anglia
Television, probably in 1980. This is a regional television and I've never
seen the program. They had similar problems to Pete - in particular, her
face mask leaked and she couldn't see for the last 15 seconds and had to
solve the cube by memory!
I've looked through my Cubic Circular again and can't find that
I ever included the above.
Some day I may assemble another issue, mostly of anecdotes.
DAVID SINGMASTER, Professor of Mathematics and Metagrobologist
School of Computing, Information Systems and Mathematics
Southbank University, London, SE1 0AA, UK.
Tel: 0171-815 7411; fax: 0171-815 7499;
email: zingmast or David.Singmaster @sbu.ac.uk
From cube-lovers-errors@oolong.camellia.org Sat May 10 00:03:41 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA19501; Sat, 10 May 1997 00:03:40 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705100139.CAA28245@mail.iol.ie>
From: Goyra
To: cube-lovers@ai.mit.edu
Subject: Strange new Rubik puzzle in Java
Date: Sat, 10 May 1997 02:28:38 +0100
X-MSMail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1161
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Those of you with Java browsers may want to
see a new Rubik puzzle I've just posted at
http://www.iol.ie/~goyra/Rubik.html
It's a dodecahedron sliced on 8 axes. I would not have
believed that it was possible that you could take the
20 evenly spaced corners of a dedecahedron and find
8 of them that are ALSO evenly spaced - but there
it is.
David Byrden
From cube-lovers-errors@oolong.camellia.org Sat May 10 15:47:13 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA22647; Sat, 10 May 1997 15:47:13 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <3.0.1.32.19970510154818.0069490c@pop.tiac.net>
X-Sender: kangelli@pop.tiac.net
X-Mailer: Windows Eudora Light Version 3.0.1 (32)
Date: Sat, 10 May 1997 15:48:18 -0400
To: cube-lovers@ai.mit.edu
From: karen angelli
Subject: Extra-long Rubik's magic rings
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
I just ran across a store selling a double long rubik's magic rings (the
flat folding puzzle) that instead 2x4 squares with three rings was 2x8 (I
think)with about six rings. They were made by matchbox in 1987. I would
have purchased one, but the price seemed like it might be steep. Does
anyone know if these are common or can be found elsewhere? Or should I rush
back and buy one before they disappear? Please let me know.
Pete Reitan
From cube-lovers-errors@oolong.camellia.org Sun May 11 16:56:07 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA25020; Sun, 11 May 1997 16:56:07 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <3375DC72.44B3@ipass.net>
Date: Sun, 11 May 1997 10:49:22 -0400
From: "Richard W. Pearson, Jr."
Reply-To: rwpearso@ipass.net
X-Mailer: Mozilla 3.0Gold (Win95; I)
MIME-Version: 1.0
To: karen angelli
CC: cube-lovers@ai.mit.edu
Subject: Re: Extra-long Rubik's magic rings
References: <3.0.1.32.19970510154818.0069490c@pop.tiac.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
> I just ran across a store selling a double long rubik's magic rings (the
> flat folding puzzle) that instead 2x4 squares with three rings was 2x8 (I
> think)with about six rings. They were made by matchbox in 1987. I would
> have purchased one, but the price seemed like it might be steep. Does
> anyone know if these are common or can be found elsewhere? Or should I rush
> back and buy one before they disappear? Please let me know.
> Pete Reitan
I'd say they're pretty uncommon. I've been looking for one for about 5
years now. Would you mind sending me the address and phone number of
the company that is selling them. I've also been looking for a "Rubik's
Magic Create the Cube." It was originally described as a 'Level 2'
Rubik's Magic. I snapped the strings on mine and haven't seen one
since.
Thanks,
Ricky Pearson
rwpearso@ipass.net
From cube-lovers-errors@oolong.camellia.org Sun May 11 17:46:25 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA25168; Sun, 11 May 1997 17:46:24 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <3.0.1.32.19970511174453.00a5aba0@mail.interlog.com>
X-Sender: aaweint@mail.interlog.com
X-Mailer: Windows Eudora Pro Version 3.0.1 (32)
Date: Sun, 11 May 1997 17:44:53 -0400
To: cube-lovers@ai.mit.edu
From: Aaron Weintraub
Subject: Re: Extra-long Rubik's magic rings
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
>I'd say they're pretty uncommon. I've been looking for one for about 5
>years now. Would you mind sending me the address and phone number of
>the company that is selling them. I've also been looking for a "Rubik's
>Magic Create the Cube." It was originally described as a 'Level 2'
>Rubik's Magic. I snapped the strings on mine and haven't seen one
>since.
I have one of these that I bought when they originally came out. I
wouldn't really call it a "level 2" puzzle, as the mechanics are identical
to that of the original Rubik's Magic. The goal is different, however.
Each plate is divided into different coloured quarters. The object is to
get both the proper shape - a cube resting on one of it's edges, centred
atop a "platform" of the two other plates - and the proper colour
orientation - the three faces that join in each corner of the cube must
have identical colours in the quadrant at that corner.
-Aaron
From cube-lovers-errors@oolong.camellia.org Mon May 12 13:39:03 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA28182; Mon, 12 May 1997 13:39:03 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705121154.HAA01989@life.ai.mit.edu>
From: Pete Beck
To: cube-lovers@ai.mit.edu
Subject: Re: Extra-long Rubik's magic rings
Date: Mon, 12 May 1997 07:53:38 -0400
X-Msmail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1155
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
As I recollect the 12 panel Magic Rings was called the Master's Edition.
Since they have been out of manufacture for quite awhile suggest you buy it
when you see it.
The 8 panel edition has been released by ODDZON and is in some toy stores
along with some other Rubik's items.
As some of you might remember there also was a 4 panel magic sold. If you
have ever taken one apart you know that any multiple of 4 is possible.
Awhile back I posted intstructions on CUBE LOVERS for restringing and or
making your own variant. The panels are just 2 pieces of plastic with the
design sandwiched in bewteen. They are not glued but held together by the
strings.
Does anybody know where to get I BET YOU CAN"T ?? a variant made with
hexagon panels.
THE FUTURE IS PUZZLING,
BUT CUBING IS FOREVER !!!
Pete, aka JUST PUZZLES
From cube-lovers-errors@oolong.camellia.org Mon May 12 13:40:54 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA28190; Mon, 12 May 1997 13:40:54 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: Re: Extra-long Rubik's magic rings
Date: 12 May 1997 15:47:57 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5l7e3d$5k5@gap.cco.caltech.edu>
References:
NNTP-Posting-Host: blend.ugcs.caltech.edu
X-Newsreader: NN version 6.5.0 #2 (NOV)
"Richard W. Pearson, Jr." writes:
>> I just ran across a store selling a double long rubik's magic rings (the
>> flat folding puzzle) that instead 2x4 squares with three rings was 2x8 (I
>> think)with about six rings. They were made by matchbox in 1987. I would
>> have purchased one, but the price seemed like it might be steep. Does
>> anyone know if these are common or can be found elsewhere? Or should I rush
>> back and buy one before they disappear? Please let me know.
>> Pete Reitan
>I'd say they're pretty uncommon. I've been looking for one for about 5
>years now. Would you mind sending me the address and phone number of
>the company that is selling them. I've also been looking for a "Rubik's
>Magic Create the Cube." It was originally described as a 'Level 2'
>Rubik's Magic. I snapped the strings on mine and haven't seen one
>since.
It has 12 panels and 5 rings, and was marketed as "Unlink the Rings".
I have one with the original packaging. They are hard to find;
I only found mine through a very lucky occurence (and paid only $1
for it!)
I am still searching for a "Make the Cube." I also have a broken one.
Perhaps I should just take the string from one of my normal Magics
and transfer it.
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
The cynical poet -- is worst of the worst.
What others are thinking -- he says out loud first.
From cube-lovers-errors@oolong.camellia.org Mon May 12 21:52:48 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA00981; Mon, 12 May 1997 21:52:48 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 13 May 1997 02:50:14 BST
From: David Singmaster Computing & Maths South Bank Univ
To: Goyra@cheerful.com
CC: cube-lovers@ai.mit.edu
Message-ID: <009B42D0.D8685A60.2@vax.sbu.ac.uk>
Subject: RE: Strange new Rubik puzzle in Java
What Goyra is describing as 'Strange new Rubik puzzle in Java' is
clearly based on the fact that one can inscribe a cube in a dodecahedron
using 8 of the dodecahedron's vertices. This is pretty well known and one
can probably see versions of it in some of the books on polyhedra.
Adapting a cube to having a dodecahedral appearance was certainly considered
in the 1980s, thoguh I can't remember if anybody ever made them for sale
- e.g Greg Stevens or Jean-Claude Constantin. I don't have any in my
collection, so I'd be grateful to hear hpw to get one.
Incidentally, a 2x2x2 version is being made in Spain in the shape
of Mickey Mouse's head (and perhaps Donald Duck's head). These are
supposed to be coming on the market here soon.
DAVID SINGMASTER, Professor of Mathematics and Metagrobologist
School of Computing, Information Systems and Mathematics
Southbank University, London, SE1 0AA, UK.
Tel: 0171-815 7411; fax: 0171-815 7499;
email: zingmast or David.Singmaster @sbu.ac.uk
From cube-lovers-errors@oolong.camellia.org Mon May 12 23:04:42 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id XAA01374; Mon, 12 May 1997 23:04:41 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 13 May 1997 03:38:27 BST
From: David Singmaster Computing & Maths South Bank Univ
To: cube-lovers@ai.mit.edu
Message-ID: <009B42D7.94F5F2E0.2@vax.sbu.ac.uk>
Subject: Rubik's Magic
Peter Beck says one can make these with any number of panels which is
a multiple of four. Actual any even number is possible. I have several
example of 2 x 3. Actually, there are two examples - the third is the
one with six hexagons.
Both the 2 x 3 examples were promotional items for magazines, one
in Italy and one in France. I happened to be in France when the French
example was attached to a magazine called Super in Jun 1988. I bought about
a dozen example, but I have no spares left!
The 2 x 2 was marketed in four forms and one could assemble all
four into a bigger pattern. However, I've also got three Hungarian versions.
One has religious symbols and comes in a folder with a picture of the Pope
on the front, apparently commemorating the Pope's visit to Hungary or
Austria.
DAVID SINGMASTER, Professor of Mathematics and Metagrobologist
School of Computing, Information Systems and Mathematics
Southbank University, London, SE1 0AA, UK.
Tel: 0171-815 7411; fax: 0171-815 7499;
email: zingmast or David.Singmaster @sbu.ac.uk
From cube-lovers-errors@oolong.camellia.org Mon May 12 23:04:11 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id XAA01370; Mon, 12 May 1997 23:04:10 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 13 May 1997 03:27:02 BST
From: David Singmaster Computing & Maths South Bank Univ
To: whuang@ugcs.caltech.edu
CC: cube-lovers@ai.mit.edu
Message-ID: <009B42D5.FC6B2820.2@vax.sbu.ac.uk>
Subject: Re: Extra-long Rubik's magic rings
Several people have remarked about having broken strings on a
version of Rubik's Magic. When one of mine first came apart, I thought
it would be impossible to get it back together correctly as I thought
there would be some critical weaving of the strings. However, once
one examines it closely, one sees that no magic is needed. Simply rethread
the strings along the correct paths and it works. All one needs is a small
screwdriver to stretch the end of a loop over the corner of a panel. So
it is much easier to assemble or to reassemble than one initially thinks
and I'd encourage anyone who has a little manual dexterity to remake a
broken one using strings from other ones.
DAVID SINGMASTER, Professor of Mathematics and Metagrobologist
School of Computing, Information Systems and Mathematics
Southbank University, London, SE1 0AA, UK.
Tel: 0171-815 7411; fax: 0171-815 7499;
email: zingmast or David.Singmaster @sbu.ac.uk
From cube-lovers-errors@oolong.camellia.org Tue May 13 12:38:16 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id MAA03375; Tue, 13 May 1997 12:38:16 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 13 May 1997 11:50:30 +0100
Message-Id: <9705131050.AA12905@mentda.me.ic.ac.uk>
X-Sender: ars2@mentda.me.ic.ac.uk
X-Mailer: Windows Eudora Light Version 1.5.2
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: cube-lovers@ai.mit.edu
From: "Andrew R. Southern"
Subject: Re: Extra-long Rubik's magic rings
At 07:53 12/05/97 -0400, you wrote:
>As I recollect the 12 panel Magic Rings was called the Master's Edition.
>Since they have been out of manufacture for quite awhile suggest you buy it
>when you see it.
>
>The 8 panel edition has been released by ODDZON and is in some toy stores
>along with some other Rubik's items.
>
>As some of you might remember there also was a 4 panel magic sold. If you
>have ever taken one apart you know that any multiple of 4 is possible.
>Awhile back I posted intstructions on CUBE LOVERS for restringing and or
>making your own variant. The panels are just 2 pieces of plastic with the
>design sandwiched in bewteen. They are not glued but held together by the
>strings.
>
>
>Does anybody know where to get I BET YOU CAN"T ?? a variant made with
>hexagon panels.
>
I must point out at this point that the magic's stringing pattern actually
revovles around just two patterns, which are equivalent to each other in
some positions.
These patterns actually only require three tiles. Three tiles will not make
a circuit, but they will make a nice line or L-shape.
For a bit of real(?) excitment(??) you could try to make one out of just two
panels. This is highly possible, as I did it back when I was 12 or 13 in
Senior school. The secret is that you loop one of the "Ligaments" as I used
to call them back around one panel twice. I cannot remember whether or not
this could go around for ever or whether it had a definiate start and end
point, but it certainly confused my classmates.
I also know that it is possible to add just two panels onto an ordinary
Rubik's Magic, creating a 2x5 array, which I don't have to say, is not
exactly divisible by four. This was fully functional, but when it was folded
in half, it did not go into "Loop" or "Tie Fighter", it went into "Fish"
from either side, unless the last two squares were folded in before folding
along the centre line. I called this the "Diabolical Edition" because it was
harder than the Master Edition, and I made about four of them for members of
my old school (Blue Coat, Liverpool).
loop:
!--!
!__!
tie fighter:
\/\/
/\/\
Fish:
\/-\
/\_/
I also created a "master Edition" from Two ordinary magics when someone drew
freehand the "Sandwich Filler" pieces of paper.
But my Piece de Resistance is the 64-panelled monstrousity that used to take
me an hour to solve, and was a complete work-out as there was so much
to-and-fro ing of the entire magic. I had to use the pictures from 12
magics, and is just an extension of the master editions solution. When it is
in a 32x2 state, it was higher than my (then) best friend, and you require
quite substantial floor space to solve it.
-Andy Southern
(The artist formerly known as the Unofficail Thermo-Fluids Fan Club of the UK).
From cube-lovers-errors@oolong.camellia.org Tue May 13 15:14:04 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA03658; Tue, 13 May 1997 15:14:03 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705131902.UAA24724@mail.iol.ie>
From: Goyra
To: cube-lovers@ai.mit.edu
MMDF-Warning: Parse error in original version of preceding line at moag.epilogue.com
Subject: Re: Strange new Rubik puzzle in Java
Date: Tue, 13 May 1997 20:03:49 +0100
X-MSMail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1161
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
> From: David Singmaster Computing & Maths South Bank Univ
> Adapting a cube to having a dodecahedral appearance was certainly
considered
> in the 1980s, thoguh I can't remember if anybody ever made them for sale
This puzzle is depicted on page 335 of "Metamagical Themas"
by Douglas Hofstadter, which has just come back into print. He says that
it was in Meffert's catalogue way back then, called the "Pyraminx Ball"
David Byrden
From cube-lovers-errors@oolong.camellia.org Tue May 13 23:24:09 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id XAA05612; Tue, 13 May 1997 23:24:09 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <3.0.1.32.19970513222622.006933b8@pop.tiac.net>
X-Sender: kangelli@pop.tiac.net (Unverified)
X-Mailer: Windows Eudora Light Version 3.0.1 (32)
Date: Tue, 13 May 1997 22:26:22 -0400
To: cube-lovers@ai.mit.edu
From: karen angelli
Subject: 2x6 Rubik's Magics
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Wow, what a response.
Yes, you are all correct, the ones I saw are 6x2, not 8x2. However, as I
now know, almost any number are possible. I saw the puzzles for sale at
The Games People Play at 1100 Massachusetts Ave, Cambridge, Ma 02138
617-492-0711 (not far from the cube-lovers administrators at MIT) (They are
also available from Puzzletts in Seattle). The owner of Games People Play
had about five for sale, and also several of the original black background
8panel Magics. She sells the 12 panel for $20 and the 8 panel for $15.
However, the buyer must beware. Each of the 12 panel ones I looked at in
Games People play had one broken string each. I bought one despite the
flaw, because she gave me the phone number for someone who knows how to fix
them, and the $20 price was substantially below the $35 plus s.h. from
Puzzletts. I had lunch with my Rubiks Magic repair-man today, got a lesson
in Rubiks magicology and now have a fully functional toy.
According to my sources, the Magics can function with as few as half of
the original strings. Each string set is double strung for extra strength.
Accordingly, the thing will still work properly if any one breaks, or if
any number break, so long as both strings on any particular loop both
break. He suggests removing any broken string as soon as possible so that
it does not get in the way of the other ones and create a cascading loose
loop catastrophe.
He happened to have a number of extra loops of fishing line because he
fixes the puzzles for a puzzle mail-order company. The company told him
that there was a large batch of puzzles made with defective strings. They
send him the puzzles, and he canabalizes them to make n-1 Magics from n
defective magics.
He fixes the Magics by wrapping the loop around the same path as the one
path that has only one loop around it. There are only a couple of rules to
follow: the string paths on one side cross the string paths on the other
side at 90degree angles, and when the two strings from one side pass the
strings from the other side between panels, the two from one side must be
either both outside of the two from the other side, or both inside the ones
from the other side.
Personally, I've always been too paranoid about my puzzles to abuse them
enough to actually find out how to take them apart. I also usually
hesitated at spending the money to get several puzzles when one seemed
sufficient. I guess I need to learn how to live life on the wild side.
'e-ya later,
Peter Reitan
From cube-lovers-errors@oolong.camellia.org Tue May 20 13:57:16 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA29197; Tue, 20 May 1997 13:57:15 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705201447.HAA16982@f16.hotmail.com>
X-Originating-IP: [194.239.24.234]
From: Philip Knudsen
To: cube-lovers@ai.mit.edu
Subject: Triamid
Content-Type: text/plain
Date: Tue, 20 May 1997 07:47:33 PDT
Hi everybody!
I recently purchased a Rubik's Triamid, Matchbox version.
Do any of you know whether that version differs from the new Oddzon release? The
Oddzon Tangle certainly is different from the Matchbox Tangle.
The leaflet that comes with the new Oddzon Tangle says the following puzzles are
in the new series:
Tangle, 2x2x2 Mini Cube, Rubik's Cube, Snake, and Triamid.
I'd like to know if they have re-released even more of the old stuff.
None of them are available where i live (Copenhagen, Denmark)
Also, if anyone has a Rubik's Hat they's like to part with, i'd be real
interested.
Philip K
---------------------------------------------------------
Get Your *Web-Based* Free Email at http://www.hotmail.com
---------------------------------------------------------
From cube-lovers-errors@oolong.camellia.org Thu May 22 16:39:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA04555; Thu, 22 May 1997 16:39:15 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: Re: Triamid
Date: 22 May 1997 18:49:46 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5m24ga$qie@gap.cco.caltech.edu>
References:
NNTP-Posting-Host: liquefy.ugcs.caltech.edu
X-Newsreader: NN version 6.5.0 #2 (NOV)
Philip Knudsen writes:
>I recently purchased a Rubik's Triamid, Matchbox version.
>Do any of you know whether that version differs from the new Oddzon release? The
>Oddzon Tangle certainly is different from the Matchbox Tangle.
As far as I can tell, the only difference is the Tangle.
(Well, and the colors of the Snake and the Magic.)
>The leaflet that comes with the new Oddzon Tangle says the following puzzles are
>in the new series:
>Tangle, 2x2x2 Mini Cube, Rubik's Cube, Snake, and Triamid.
I believe the Magic was released in this release as well.
>I'd like to know if they have re-released even more of the old stuff.
>None of them are available where i live (Copenhagen, Denmark)
>Also, if anyone has a Rubik's Hat they's like to part with, i'd be real
>interested.
Heh heh. (No, I don't have one. I do have a Rubik's Maze, though.)
>Philip K
>---------------------------------------------------------
>Get Your *Web-Based* Free Email at http://www.hotmail.com
>---------------------------------------------------------
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
The cynical poet -- is worst of the worst.
What others are thinking -- he says out loud first.
From cube-lovers-errors@oolong.camellia.org Tue May 27 15:51:48 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA13327; Tue, 27 May 1997 15:51:48 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705271134.EAA07180@f9.hotmail.com>
X-Originating-IP: [194.239.24.233]
From: Philip Knudsen
To: cube-lovers@ai.mit.edu
Subject: Tangle & Triamid
Content-Type: text/plain
Date: Tue, 27 May 1997 04:34:47 PDT
Thanks alot for the info on Triamid (no major difference).
Pete Beck asked:
How is tangle different. I know it is plastic and the strings are raised
but is the puzzle different?
The Oddzon version has only nine pieces, which are double-sided. For these 18
sides, all pieces from the original tangle, except the six with a straight
yellow line are used. Of the 9 puzzle pieces, 3 have straight red on both sides,
3 have a straight green, and 3 a straight purple. The result is a somewhat
easier puzzle, at least it's solveable without computer aid.
Back to the Triamid: Has anyone ever tried to build a large one out of several
small? To build a 4x4 one would need three Triamids to get enough connector
pieces. The question is, would the puzzle work, or would it be too hard to
disconnect a 3x3 top from a 4x4 base?
Me, i'm seriously considering buying 2 extra.
Philip K
---------------------------------------------------------
Get Your *Web-Based* Free Email at http://www.hotmail.com
---------------------------------------------------------
From cube-lovers-errors@oolong.camellia.org Tue May 27 15:52:28 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA13331; Tue, 27 May 1997 15:52:28 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705271845.TAA31887@mail.iol.ie>
From: Goyra
To: cube-lovers@ai.mit.edu
Subject: Java Rubik Gallery now open
Date: Tue, 27 May 1997 19:46:27 +0100
X-MSMail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1161
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Those of you with Java browsers, powerful
PCs and fast Internet connections may want to
revisit my Rubik Gallery at
http://www.iol.ie/~goyra/Rubik.html
I have just installed Rubik cubes of all sizes up to 11.
I intend to maintain the Gallery as the world's
largest collection of "Rubik" puzzles, a place where
you can play with that obscure puzzle you were never
able to find in the shops. Any suggestions as to what
should go in it next, are welcome.
David Byrden
From cube-lovers-errors@oolong.camellia.org Tue May 27 17:37:53 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA13588; Tue, 27 May 1997 17:37:53 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705272118.RAA09157@life.ai.mit.edu>
Date: Tue, 27 May 97 17:18:18 EDT
From: Nichael Cramer
To: Goyra
cc: cube-lovers@ai.mit.edu
Subject: Re: Java Rubik Gallery now open
>From: Goyra
>Subject: Java Rubik Gallery now open
>Date: Tue, 27 May 1997 19:46:27 +0100
>
>
> Those of you with Java browsers, powerful
>PCs and fast Internet connections may want to
>revisit my Rubik Gallery at
>
> http://www.iol.ie/~goyra/Rubik.html
> [...]
I freely admit that I tuned in fully expecting to be disappointed. But this
is really slick.
N
From cube-lovers-errors@oolong.camellia.org Wed May 28 16:35:19 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA17056; Wed, 28 May 1997 16:35:19 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199705281233.IAA05016@life.ai.mit.edu>
Date: Wed, 28 May 97 8:30:53 EDT
From: Nichael Cramer
To: cube-lovers@ai.mit.edu
Subject: [gknauth: Professor cracks Rubik's cube mystery]
[Simply passing along bits --N]
----- Forwarded message # 1:
Date: Wed, 28 May 97 08:13:32 EDT
From: gknauth@BBN.COM
Subject: Professor cracks Rubik's cube mystery
> From: Andy Lee
Professor cracks Rubik's cube mystery
LOS ANGELES (May 27, 1997 5:43 p.m. EDT) - A University of California
computer science professor has solved the long-standing mystery of Rubik's
cube, university officials said Tuesday.
Richard Korf found a way to line up the colored squares of the cube in an
average 18 moves and a maximum of 20, officials said without explaining
exactly how it is done.
Rubik's cube, launched in the 1970s by the Hungarian Erno Rubik, became a
worldwide phenomenon, with people spending hours trying to manipulate it
into color-coordinated rows.
Korf is due to reveal his method at a national conference on artifical
intelligence July 28 in Providence, Rhode Island.
Copyright 1997 Nando.net, Agence France-Presse
----- End of forwarded messages
From cube-lovers-errors@oolong.camellia.org Wed May 28 17:37:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA17223; Wed, 28 May 1997 17:37:15 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338CA4A0.79A7@snowcrest.net>
Date: Wed, 28 May 1997 14:33:20 -0700
From: Joe McGarity
Reply-To: joemcg3@snowcrest.net
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: "Mailing List, Rubik's Cube"
Subject: Solved in 20 moves?
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Forgive me for saying so, but, "Bulls**t"
From cube-lovers-errors@oolong.camellia.org Wed May 28 17:40:08 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA17238; Wed, 28 May 1997 17:40:08 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Sender: mark@ampersand.com
To: cube-lovers@ai.mit.edu
Cc: Nichael Cramer
Subject: Re: [gknauth: Professor cracks Rubik's cube mystery]
References: <199705281233.IAA05016@life.ai.mit.edu>
From: Mark Atwood
Date: 28 May 1997 17:38:41 -0400
In-Reply-To: Nichael Cramer's message of Wed, 28 May 97 8:30:53 EDT
Message-ID:
X-Mailer: Gnus v5.2.40/Emacs 19.31
Nichael Cramer writes:
>
> ----- Forwarded message # 1:
>
> Date: Wed, 28 May 97 08:13:32 EDT
> From: gknauth@BBN.COM
> Subject: Professor cracks Rubik's cube mystery
>
> ...
>
> Richard Korf found a way to line up the colored squares of the cube in an
> average 18 moves and a maximum of 20, officials said without explaining
> exactly how it is done.
> ...
>
Is this a new upper bound?
--
Mark Atwood | We must not remind them
zot@ampersand.com | that Giants walk the Earth.
From cube-lovers-errors@oolong.camellia.org Thu May 29 00:28:22 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA18141; Thu, 29 May 1997 00:28:21 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Wed, 28 May 1997 15:18:10 -0700
From: Richard E Korf
Message-Id: <199705282218.PAA17014@denali.cs.ucla.edu>
To: Cube-Lovers@ai.mit.edu
Subject: rumor control
Dear Cube-Lovers,
Apparently some work I did recently has gotten badly mangled by the press. I
have NOT resolved the question of whether or not 20 face turns is the maximum
distance one can get from a scrambled cube.
What I did is to write a heuristic search program that finds optimal
solutions to arbitrary scrambled cubes. The algorithm is very different from
the method of Fiat, Moses, Shamir, et al, and seems to be competitive with their
algorithm in terms of time and space. The current version of my program is
practical for cubes up to 18 moves away from solved.
Out of 10 randomly generated cubes, one was solved in 16 moves, 3 required 17
moves, and 6 required 18 moves, suggesting that the median optimal solution
length is probably 18 moves.
A paper on this work will be presented at the National Conference on
Artificial Intelligence (AAAI-97) in Providence, RI in July. I'd be happy to
send a postscript copy of the paper to anyone who is interested, unless there
are a lot of requests, in which case I'll just post it on my web site and put a
pointer here. In addition, if there is enough interest, I could write a short
summary of the paper for this list. Thanks for your attention.
-rich korf
From cube-lovers-errors@oolong.camellia.org Thu May 29 00:28:49 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA18145; Thu, 29 May 1997 00:28:48 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338CEAA0.6CBB@idirect.com>
Date: Wed, 28 May 1997 19:32:00 -0700
From: Mark Longridge
Organization: Computer Creations
X-Mailer: Mozilla 2.01 (Win16; U)
MIME-Version: 1.0
To: Nichael Cramer
CC: cube-lovers@ai.mit.edu
Subject: Re: [gknauth: Professor cracks Rubik's cube mystery]
References: <199705281233.IAA05016@life.ai.mit.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Nichael Cramer wrote:
>
> [Simply passing along bits --N]
>
> ----- Forwarded message # 1:
>
> Date: Wed, 28 May 97 08:13:32 EDT
> From: gknauth@BBN.COM
> Subject: Professor cracks Rubik's cube mystery
>
> > From: Andy Lee
>
> Professor cracks Rubik's cube mystery
>
> LOS ANGELES (May 27, 1997 5:43 p.m. EDT) - A University of California
> computer science professor has solved the long-standing mystery of Rubik's
> cube, university officials said Tuesday.
>
> Richard Korf found a way to line up the colored squares of the cube in an
> average 18 moves and a maximum of 20, officials said without explaining
> exactly how it is done.
>
> Rubik's cube, launched in the 1970s by the Hungarian Erno Rubik, became a
> worldwide phenomenon, with people spending hours trying to manipulate it
> into color-coordinated rows.
>
> Korf is due to reveal his method at a national conference on artifical
> intelligence July 28 in Providence, Rhode Island.
>
> Copyright 1997 Nando.net, Agence France-Presse
>
> ----- End of forwarded messages
Let's say the cube-lovers of the world are skeptical...
Are we talking about q turns or q+h turns?
My own conjecture (which I have kept to myself until now) was that Mike Reid's
12-flip pattern in 24 q turns was the antipode in q turns only. I have no
proof of this fact.
It is possible Professor Korf has found a totally new approach to the rubik
problem. Dik Winter (months and months before) never did find any position on
the 3x3x3 which required more than 20 moves in the q+h metric.
Conventional wisdom (using Kociemba type algorithms) was that the god's algorithm
for the standard 3x3x3 cube was intractible.
In case case, without more evidence, this news message does not add to the
existing level of cube knowledge.
I'm still waiting and watching for any optimal solutions to the Megaminx
spot patterns!
Perhaps Professor Korf has a mathematical proof. It does seem unlikely that he
sifted through all the possible positions.
-> Mark
From cube-lovers-errors@oolong.camellia.org Thu May 29 00:29:17 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA18149; Thu, 29 May 1997 00:29:16 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
To: cube-lovers@ai.mit.edu
Subject: Professor cracks Rubik's cube mystery
Message-ID: <19970528.222126.9494.2.shaggy34@juno.com>
X-Mailer: Juno 1.15
X-Juno-Line-Breaks: 0,2-3,5-6,9-10,12
From: Josh D Weaver
Date: Wed, 28 May 1997 23:22:16 EDT
What do the skeptics have to say about the 20 move solve? It was said
that in theory it could be done; but is it really possible?
Does anyone know how long time wise it took Richard Korf to solve it
using the 20 move method?
I'm just a 15 year old who can solve the cube so I don't know much about
theories or mathematical patterns. So if someone can explain it to me
that would be great.
If it all that is claims to be, then I can't wait to know how to use the
method.
From cube-lovers-errors@oolong.camellia.org Thu May 29 00:30:06 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA18159; Thu, 29 May 1997 00:30:06 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Wed, 28 May 1997 23:39:18 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970528233918.21401a3a@iccgcc.cle.ab.com>
Subject: Re: Solved in 20 moves?
From: SMTP%"joemcg3@snowcrest.net" 28-MAY-1997 22:02:17.57
To: SCHMIDTG
CC:
Subj: Solved in 20 moves?
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338CA4A0.79A7@snowcrest.net>
Date: Wed, 28 May 1997 14:33:20 -0700
From: Joe McGarity
Reply-To: joemcg3@snowcrest.net
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: "Mailing List, Rubik's Cube"
Subject: Solved in 20 moves?
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
On the subject of a new upper bound for Rubik's cube solution, Joe
McGarity wrote:
>Forgive me for saying so, but, "Bulls**t"
While it's certainly possible that the news release may have distorted the
original message, I certainly would not in any way discount the work of
Dr. Korf as he is a recognized authority in the area of computer search
(you'll find his name within the index of any decent book on the subject).
As far as I know he is also the first, and only, person to have developed
a computer program capable of discovering a general solution to the cube
starting only from basic knowledge of cube states and operators.
Forgive me for keeping an open mind on this one.
-- Greg
From cube-lovers-errors@oolong.camellia.org Thu May 29 15:24:53 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA19669; Thu, 29 May 1997 15:24:52 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: Benjamin Wong
To: Josh D Weaver
Date: Thu, 29 May 1997 17:34:55 +1000 (EST)
X-Sender: chi@pipe13.orchestra.cse.unsw.EDU.AU
cc: cube-lovers@ai.mit.edu
Subject: Re: Professor cracks Rubik's cube mystery
In-Reply-To: <19970528.222126.9494.2.shaggy34@juno.com>
Message-ID:
On Wed, 28 May 1997, Josh D Weaver wrote:
._@_.
._@_.What do the skeptics have to say about the 20 move solve? It was said
._@_.that in theory it could be done; but is it really possible?
._@_.
There was a prove that within 16-18 face move, the number of possible
pattern exceed the number of possible pattern of the cube,
hence they deduce that any pattern can be acheive within 16-18 move,
ie: it can be done,
if u can move forward 18 move,
by backtracking, it can be move backward within 18 move.
._@_.Does anyone know how long time wise it took Richard Korf to solve it
._@_.using the 20 move method?
._@_.
._@_.I'm just a 15 year old who can solve the cube so I don't know much about
._@_.theories or mathematical patterns. So if someone can explain it to me
._@_.that would be great.
._@_.
._@_.If it all that is claims to be, then I can't wait to know how to use the
._@_.method.
I don't think "the method",(if it actually exist,) can be applied to human,
i think it involved a lot of AI research, where computer will think
faster and can plan say 5 to 6 move ahead, and see if it recognise any pattern
I will not put much hope on trying to solve in 20 move
with a real cube by hand.
o------------------------------------------------------o
|Error: Reality.sys Corrupt? Reboot Universe [Y,N,Q] |
+---------------o--------------------------------------o
| Benjamin Wong | E-mail: chi@cse.unsw.edu.au |
| | or benjaminwong@hotmail.com |
| | http://www.cse.unsw.edu.au/~chi |
o---------------o--------------------------------------o
|=A1u=C2=E5=A5=CD=A1I=BD=D0=B0=DD=A1y=BA=B5=BF=DF=B2=B4=A1z=AA=BA=A6=A8=A6]=ACO=AC=C6=BB=F2=A1H=A1v |
|Quick Quiz: Describe Universe ? Give Three Example. |
o------------------------------------------------------o
From cube-lovers-errors@oolong.camellia.org Thu May 29 15:26:00 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA19676; Thu, 29 May 1997 15:26:00 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338D2A8E.56E4@snowcrest.net>
Date: Thu, 29 May 1997 00:04:46 -0700
From: Joe McGarity
Reply-To: joemcg3@snowcrest.net
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: "Mailing List, Rubik's Cube"
Subject: Okay, I give.
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I have been reprimanded.
And justly so. Of course the first step to science is to retain an open
mind. My comment was not to be taken 100% seriously, but to hopefully
point out with a bit of humor that the burden of proof here is on those
making the claim. In retrospect the post should have read, "Bulls**t
:-)" With the additional challange of proving me wrong invited and
openly reviewed by myself. I would be delighted to be proved wrong in
this matter, but I maintain that the evidence should be carefully
examined and discussed as a group before we jump to a concensus on the
subject.
Having climbed out of the hole I dug for myself, I will now remove my
feet from my mouth and check out what Prof. Korf has to say.
By the way, I will do PR work for interested corporations and
politicians for a fee.
Joe McGarity
From cube-lovers-errors@oolong.camellia.org Thu May 29 16:30:21 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA19799; Thu, 29 May 1997 16:30:21 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
To: Cube-Lovers@AI.MIT.EDU
From: Wei-Hwa Huang
Subject: Re: rumor control
Date: 29 May 1997 19:55:39 GMT
Organization: California Institute of Technology, Pasadena
Message-ID: <5mkmvr$b2v@gap.cco.caltech.edu>
References:
NNTP-Posting-Host: pyro.ugcs.caltech.edu
X-Newsreader: NN version 6.5.0 #3 (NOV)
Richard E Korf writes:
>Dear Cube-Lovers,
> Apparently some work I did recently has gotten badly mangled by the press.
My symphathies. I remember a news article a few years ago when the
largest Mersenne prime was discovered; it went something like:
"Mathematicians have discovered a number that has 224,375 digits and
is divisible by 1."
> A paper on this work will be presented at the National Conference on
>Artificial Intelligence (AAAI-97) in Providence, RI in July. I'd be happy to
>send a postscript copy of the paper to anyone who is interested, unless there
>are a lot of requests, in which case I'll just post it on my web site and put a
>pointer here. In addition, if there is enough interest, I could write a short
>summary of the paper for this list. Thanks for your attention.
Please do so. I am sure many people on this list would be interested in
seeing it.
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
-------------------------------------------------------------------------------
Question everything. Learn something. Answer nothing. -- Engineer's Motto
From cube-lovers-errors@oolong.camellia.org Thu May 29 21:58:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA20780; Thu, 29 May 1997 21:58:15 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Thu, 29 May 1997 17:24:45 -0700
From: Richard E Korf
Message-Id: <199705300024.RAA18247@denali.cs.ucla.edu>
To: Cube-Lovers@ai.mit.edu
Subject: Description of algorithm for finding minimal-move solutions to Rubik's Cube
Dear Cube-Lovers,
Here is the promised short description of my algorithm for finding optimal
solutions to Rubik's Cube. I use the face-turn metric, meaning any twist of a
face, even 180 degrees, counts as a single move. A twist of a center slice
can only be accomplished by two twists of the outside faces.
The algorithm is a heuristic search, called Iterative-Deepening-A*, or IDA*,
for any artificial intelligence (AI) folks in the group. Given a scrambled
cube, it first looks for solutions one move long, then solutions two moves long,
then three moves, etc. Each iteration searches for solutions of successively
greater length, until a solution is found. At that point it quits, returning
what must be an optimal solution, barring program bugs. This is a completely
brute-force approach to the problem. At a million twists per second, searches
to depth 10 would take almost 3 days.
To make this approach practical, we need a function that given a cube state
will efficiently calculate a lower bound on the number of moves needed to solve
it. This is called a heuristic evaluation function. For example, we can
precompute the number of moves needed to solve each edge cubie individually from
each possible position and orientation. Then given a state of the cube, we sum
the number of moves needed to solve all 12 edge cubies individually, and divide
by 4, since each move moves 4 edge cubies. This heuristic, called 3D Manhattan
Distance, has an average value of 5.5. The important thing is that this function
always return a lower bound on the number of moves needed to solve a state.
During our search we compute the Manhattan Distance of each state. If we
are looking for solutions of length 10, for example, and we have a state that is
5 moves from the initial state, and its Manhattan Distance from the solved state
is 6 moves, we don't have to search that path any deeper, since it will take at
least 11 moves to get to the goal along that path, since 6 is a lower bound on
the number of moves needed to solve the state. Adding the Manhattan Distance
heuristic to our search algorithm lets us search to depth 14 in about 3 days.
We could do the same thing with the corner cubies, and take the maximum of the
two values, but that doesn't help much.
To do better, we need a more accurate heuristic function. For that, we use
an idea call "Pattern Databases" due to Culberson and Schaeffer. See Culberson,
J.C., and J. Schaeffer, Searching with pattern databases, Proceedings of the
11th Conference of the Canadian Society for the Computational Study of
Intelligence, published in Advances in Artificial Intelligence, Gordon McCalla
(Ed.), Springer Verlag, 1996.
For example, if we consider just the corner cubies, there are only about 88
million possible states they could be in (8!x3^7). We exhaustively build and
store a table, using breadth-first search, that tells us the minimum number of
moves needed to solve just the corner cubies from every possible combination,
ignoring the edge cubies. This value ranges from 0 to 11 moves, averages 8.764
moves, and requires only 4 bits per state. (We could reduce this further using
an idea of Dan Hoey's published in this list awhile ago.) This table only has
to be computed once, taking about a half hour, and requires about 42 megabytes
of memory to store (a megabyte is 1048576 bytes).
Then, during the search, we compute the heuristic lower bound on the number
of moves to the goal by looking up the configuration of the corner cubies, and
using the number of moves stored in the table. 8.764 is a lot better than 5.5.
Finally, we divide the edge cubies into two groups of six, and compute a
similar table for each group. There are too many combinations of all 12 edge
cubies to build a single table. The final heuristic function we use is the
maximum of 3 different values, the moves needed to solve the corner cubies, and
the moves needed to solve each group of six edge cubies. The total memory for
all three tables is 82 megabytes.
Given more memory, we could built larger tables, for example, considering 7
edge cubies at a time. This would give a more accurate heuristic value, and
reduce the running time of the search algorithm. In fact, an informal analysis
of the performance of the algorithm suggests that its speed will increase
linearly with the amount of available memory. Thus, given twice as much memory,
the algorithm should run in roughly half the time. Disks and other secondary
storage are of no use, since the access time is much too slow to be worthwhile.
The current version of the program is written in C on a Sun Ultra-Sparc
Model-1 workstation with 128 megabytes of memory. It generates about 700,000
states per second. Depth 16 searches typically take less than 4 hours, depth 17
searches take about 2 days, and complete depth 18 searches take about 27 days. A
complete depth 19 search would take about a year. Each depth takes roughly
13.34847 times longer than the previous, which is the branching factor of the
problem space.
The algorithm is easily parallelized. Given 18 processors, for example, we
make all 18 possible first moves, and hand each of the resulting states to a
different processor to solve. This will give roughly linear speedup with the
number of processors, since the amount of time needed to search to the deeper
levels is very consistent from one state to the next.
Sorry for the length of this message, but I hope it will of interest to some
of you. If you'd like the full paper, just send me a message. Thanks very much.
-rich
From cube-lovers-errors@oolong.camellia.org Thu May 29 22:04:04 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA20824; Thu, 29 May 1997 22:04:03 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Thu, 29 May 1997 21:54:21 -0400 (EDT)
From: Ed Schwalenberg
Message-Id: <199705300154.VAA27472@husky.odi.com>
To: joemcg3@snowcrest.net
Cc: cube-lovers@ai.mit.edu
In-Reply-To: Joe McGarity's message of Thu, 29 May 1997 00:04:46 -0700 <338D2A8E.56E4@snowcrest.net>
Subject: Okay, I give.
Organization: Object Design, 25 Mall Rd, Burlington, MA 01803 - 617-674-5337
Date: Thu, 29 May 1997 00:04:46 -0700
From: Joe McGarity
I have been reprimanded.
And justly so. ...
This all reminds me of a time a few years ago when I read an article in
the Boston Globe about a physics professor from Iowa who claimed to have
discovered a "black box" way to remove radioactivity. I sneered at the
idea, until a friend of mine pointed out that the professor didn't say how
long you had to leave the radioactive material in the box....
[ The moderator will allow no further messages on the topic of
how the press screws up explaining science, mathematics and
technology to the public. ]
From cube-lovers-errors@oolong.camellia.org Fri May 30 14:28:22 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id OAA22894; Fri, 30 May 1997 14:28:22 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338F18FB.22DC@snowcrest.net>
Date: Fri, 30 May 1997 11:14:19 -0700
From: Joe McGarity
Reply-To: joemcg3@snowcrest.net
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: "Mailing List, Rubik's Cube"
Subject: The rest of us
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I hope that I am not alone in that much of Prof. Korf's description is a
little over my head. Perhaps the Professor or others can recomend books
on AI or group theory to those of us whose education only goes as far as
trigonometry. This is a very interesting subject and I find myself
wanting to understand it better. Is there anything out there aimed at
the beginner? If so I would very much like to see it.
From cube-lovers-errors@oolong.camellia.org Fri May 30 18:38:34 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id SAA23400; Fri, 30 May 1997 18:38:33 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338F3C40.6EEC@ibm.net>
Date: Fri, 30 May 1997 13:44:48 -0700
From: Jin "Time Traveler" Kim
Organization: The Fourth Dimension
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: The rest of us
References: <338F18FB.22DC@snowcrest.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Joe McGarity wrote:
>
> I hope that I am not alone in that much of Prof. Korf's description is a
> little over my head. Perhaps the Professor or others can recomend books
> on AI or group theory to those of us whose education only goes as far as
> trigonometry. This is a very interesting subject and I find myself
> wanting to understand it better. Is there anything out there aimed at
> the beginner? If so I would very much like to see it.
Prof. Korf's solution to the Cube sounds like it basically maps all
possible iterations within a given number of steps. Once you know all
the possible combinations given the maximum number of turns, you can
then just compare a scrambled cube to the map and see if it falls within
one of the available templates. And of course, the more moves you
calculate out to, the longer it's going to take due to the geometrically
increasing number of possible movements.
Yes, the solution, as the good Professor explains it, is definately over
my head, but I think I know how he is going about solving it. Brute
force. Of course, the DETAILS of how it's done are over my head as
well. Ultimately I think the cube is more satisfying if I solve it
myself, even if it takes me 3 minutes and dozens of twists.
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@oolong.camellia.org Fri May 30 19:43:03 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id TAA23535; Fri, 30 May 1997 19:43:02 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Fri, 30 May 97 19:41:15 EDT
Message-Id: <9705302341.AA06714@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: chrono@ibm.net
Cc: cube-lovers@ai.mit.edu
Reply-To: hoey@aic.nrl.navy.mil
Subject: Re: The rest of us
> Prof. Korf's solution to the Cube sounds like it basically maps all
> possible iterations within a given number of steps. Once you know all
> the possible combinations given the maximum number of turns, you can
> then just compare a scrambled cube to the map and see if it falls within
> one of the available templates.
No, you've misunderstood. Rich doesn't attempt to "map all possible
iterations" (by which you seem to imply some sort of preprocessing so
as to be able to recognize any position at a given depth). After all,
according to his estimate of the median, there should be over 10^18 of
them at depth 18f, and finding them all would take his program many
thousands of years.
Instead, he takes advantage of knowing what the target cube is by
using a measure called a "heuristic". A heuristic estimates how far a
given process is from solving the cube, such as the "oriented distance
from home" (ODH) that appears in the archives. Then if you have tried
7f turns and you know it will take at least 12f more, you know you're
on the wrong track, and look elsewhere.
But there are lots and lots of wrong tracks, and you need to recognize
and discard them quickly. The ODH isn't that good an estimate, so it
doesn't discard enough of them--it would still take 250 years to
search for one position. Finding better ways of estimating how far
you are from the goal is what the research is about.
So just because he says it's "brute force" doesn't mean you list all
the positions in advance. You definitely need to know what the goal
position is for Rich's approach to work. In particular, his method
does not seem to be applicable to finding what the furthest position
is.
Dan Hoey
Hoey@AIC.NRL.Navy.Mil
From cube-lovers-errors@oolong.camellia.org Fri May 30 20:33:43 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id UAA23656; Fri, 30 May 1997 20:33:43 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338F7124.73A6@hrz1.hrz.th-darmstadt.de>
Date: Sat, 31 May 1997 02:30:28 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: Description of algorithm for finding minimal-move solutions to Rubik's Cube
References: <199705300024.RAA18247@denali.cs.ucla.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Richard E Korf wrote:
>
> Dear Cube-Lovers,
> Here is the promised short description of my algorithm for finding optimal
> solutions to Rubik's Cube.
>From the description it is evident, that the algorithm Richard E Korf
uses is basically identical to the the sub-algorithm which is used in
each stage of my two stage algorithm to solve the cube. What he calls
"heuristic functions" are the "pruning tables" of Dik Winter and Michal
Reid and the "filters" in the original description of the algorithm in
CFF 28 (April 1992) of the Dutch Cubist Club. Here is a short summary of
this algorithm in the version I implemented in a windows95 program
requiring 16Mbyte of Ram. When I will have included a help-function
within the next weeks, I will offer it to all interested cubists for
free:
In phase 1, the cube is transformed to an element of the subgroup
generated by __. This is equivalent to restore the
orientation of the 8 corners and 12 edges and to put the 4 edges of the
UD-slice in that slice. There are 3^7=2187 possible states for the
corner orientations, 2^11=2048 possible edge orientations and
12*11*10*9/(1*2*3*4)=495 possible positions for the 4 edges of the
UD-slice. The "heuristic functions" consist of three tables, using 4
bits for each entry. The first table stores the minimum numbers to solve
the 2187*2048 possible states to restore the orientation of both edges
and corners, the other tables have 2187*495 and 2048*495 entries and
store the corresponding minimum numbers.
Dik Winter proved, that 12 moves always suffice to get to this subgroup.
In phase 2, the cube is solved in this subgroup, using only
U,D,R2,L2,F2, and B2. Now we have do restore the permutations of the
corners, edges and middle slice. There are 8! states for the corner
permutations, 8! states for the edge permutations and 4! states for the
permutations of the UD-slice. The "heuristic functions" consist of only
two tables, storing the minimum numbers to restore both edges and
UD-Slice and both corners and UD-Slice, having 8!*4! entries each.
The table for the minimum numbers to restore both edges and corners
would have 8!*8! entries and is not possible with the current hardware.
Michael Reid proved, that 18 moves always suffice in this subgroup.
Having found a solution in stage1 and stage2 the algorithm does not
stop, but generates other solutions in stage1. So if for example we have
10 moves in stage1 and 12 moves in stage2, there might be a solution
with 11 moves in stage1 but only 10 moves in stage2. Running long
enough, the algorithm will find the overall optimal solution, having no
moves in stage2 then.
Due to the smaller size of the subgroups a first solution usually will
be
found within seconds. This first solution is optimal for phase1, but
indeed (usually) not optimal for the overall solution. Typically you
will have solutions with less then 20 moves within minutes and the
optimal solution for states with lets say less then 16 moves will be
found within a reaseonable time.
Herbert
From cube-lovers-errors@oolong.camellia.org Fri May 30 21:24:38 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA23782; Fri, 30 May 1997 21:24:38 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Sender: Haym Hirsh
Date: Fri, 30 May 97 21:10:39 EDT
From: Haym Hirsh
Reply-To: Haym Hirsh
To: joemcg3@snowcrest.net
Subject: Re: The rest of us
In-Reply-To: Your message of Fri, 30 May 1997 11:14:19 -0700
Cc: cube-lovers@ai.mit.edu
Message-ID:
Here's a brief attempt at a "layman's" description of Professor Korf's
work:
Imagine you have a function that takes as input a messed-up Rubik's
cube, and outputs a guess of how many moves it will take to get it to
the solved state. Further, assume this guess is never greater than
the correct number of moves -- sometimes your solution-length guesser
may make a correct guess, but sometimes (or even perhaps always) it
may underestimate the number.
There is an algorithm called A* that is guaranteed to find a shortest
solution sequence for any Rubik's cube it is given, as long as it is
given a solution-length guesser that has this never-overestimates-the-
number-of-moves-to-solved guarantee.
The problem is that A*'s guarantee is only that it will return a
shortest solution to any cube, with no guarantee on how long it will
take to find it. Due to this run-time issue A* is only applicable to
the most trivial of problems.
However, in the mid-80s Professor Korf presented a tractable variant
of A*, called IDA* (Iterative Deepening A*) that has the same
guarantee as A* on finding shortest solutions, but is much faster.
The problem now, though, is that even IDA* can also take a long time.
Its salvation, however, is that, loosely speaking, the better the
solution-length-guessing-function is, the faster IDA* will run. Thus,
for example, you could use a function that always returned 0 as the
guess for how many moves you are from the start. It's not a
particularly clever guess, but it obeys the rule that it never
overestimates the solution length. Therefore, you could use it with
IDA* (or, for that matter, A*) to find shortest solutions to any cube.
Except that it would run too slow, because the solution-length guesser
is so dumb. A better solution-length guesser would help IDA* run
faster.
Professor Korf came up with a way to more intelligently guess what the
solution length will be for arbitrary cubes -- it gives something much
closer to the true value, but still without overestimating. A
simplified form of this would be to figure out how many moves at
minimum it will take to get the corners in place, and use this
corners-only solution length as a guess. This will never overestimate
the solution length, since to get everything in place you certainly
have to get at least the corners into their proper positions, and it
is better than a guesser that always returns 0.
Professor Korf also had to figure out how to compute these guesses in
an efficient fashion, since guesses will be requested many many times
by IDA* as it explores possible intermediate cubes in its search for
the solution. To do this he enumerated all 88 million configurations
of corners (different cubes with different arrangements of edges but
with identical corners are considered identical configurations). For
each he figured out the minimum number of moves that would be
necessary to get them into their correct position in a solved cube if
edges were ignored (taking a non-trivial, but non-infinite, amount of
time to do this for each of the 88 million configurations). Finally,
he generated a table with 88 million entries, with each entry
corresponding to a corner configuration and containing the solution
length for that configuration. This created a way to quickly compute
his more accurate corner-centric solution-length guesser, via table
lookups.
In truth Professor Korf improves on this even further by developing a
better solution-length guesser that does similar things with edges as
I just described with corners, also using tables for efficient guess
calculation. The result is a solution-length guesser that is accurate
enough to allow IDA* to solve the 10 random cubes that he generated.
More specifically, Professor Korf generated random cubes by taking a
solved cube and making 100 random turns to it. He did this 10
separate times, and got 10 messed-up cubes. He then ran IDA* using
his table-based solution-length guesser, and solved all 10, one in 16
moves, three in 17 moves, and the rest in 18 moves. Because he used
IDA*, and because his solution-length guesser never overestimates
solution lengths, his solutions are guaranteed to be optimal (due to
IDA*'s mathematical guarantees).
This does not argue that 18 is the longest solution possible for any
cube. Just that for the 10 he generated randomly, none required more
than 18. Perhaps some cubes are more than 18 moves away from start.
None simply happened to arise amongst his 10 cases.
From cube-lovers-errors@oolong.camellia.org Sat May 31 00:19:54 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA24209; Sat, 31 May 1997 00:19:53 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Fri, 30 May 97 23:15:17 EDT
Message-Id: <9705310315.AA19052@sun13.aic.nrl.navy.mil>
From: Dan Hoey
To: Haym Hirsh , cube-lovers@ai.mit.edu
Subject: More on Korf's method
Herbert Kociemba wrote:
> From the description it is evident, that the algorithm Richard E Korf
> uses is basically identical to the the sub-algorithm which is used in
> each stage of my two stage algorithm to solve the cube. What he calls
> "heuristic functions" are the "pruning tables" of Dik Winter and Michal
> Reid and the "filters" in the original description of the algorithm in
> CFF 28 (April 1992) of the Dutch Cubist Club.
First, the term "heuristic function" is not Rich's invention for the
lower-bound function of A*. I learned that term in 1970 from
Nillson's textbook on Artificial Intelligence. And second, even if
"pruning tables" and "filters" are essentially nothing but heuristic
functions, that still does not make the algorithms "basically
identical". From the description, I think Rich's heuristic functions
are quite a different type from what you use (though I do not
understand either exactly yet). I also suspect that the difference
between A* and IDA* (which has not really been explained here yet) may
play a larger role than you give it credit for.
But thanks for the description of your algorithm (some of which has
previously filtered into the archives), and the offer of a program
(what language?). My guess is that your heuristics have a good chance
of being more effective at finding optimal solutions for random cubes
than Rich's, though perhaps some ideas from Rich need to be
incorporated.
Haym Hirsh wrote:
> Here's a brief attempt at a "layman's" description of Professor
> Korf's work:
[ which I omit ]
Thanks very much for the explanation. It agrees with my understanding
of the paper, as far as that goes. But do you have a succinct
explanation of what makes IDA* more tractable than A*? That's the
part I missed.
Now when Rich found his first ten random cubes (well, he doesn't _say_
they're the _first_ he tried, but they had better be) took under 18f
moves each, you mention
> This does not argue that 18 is the longest solution possible for any
> cube. Just that for the 10 he generated randomly, none required more
> than 18. Perhaps some cubes are more than 18 moves away from start.
> None simply happened to arise amongst his 10 cases.
First, we know 18f is not optimal, because the 12-flip is proven to
require 20f moves exactly (unless Mike Reid made a mistake, or I
misunderstood).
But we _can_ say there's at most one chance in 1024 that the first ten
random cubes you pick will all be closer than the median to solved.
So this demonstrates Rich's claim that the median optimal solution is
very likely 18f.
Dan
From cube-lovers-errors@oolong.camellia.org Sat May 31 16:03:06 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA27651; Sat, 31 May 1997 16:03:06 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id:
In-Reply-To: <199705300024.RAA18247@denali.cs.ucla.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 31 May 1997 10:26:59 -0400
To: Cube-Lovers@ai.mit.edu
From: Nichael Lynn Cramer
Subject: Website [was: Description of algorithm for ...]
Cc: Richard E Korf , joemcg3@snowcrest.net, chrono@ibm.net,
Hoey@aic.nrl.navy.mil, kociemba@hrz1.hrz.th-darmstadt.de,
hirsh@cs.rutgers.edu
Because of interest I've run into from friends elsewhere, I'm planning to
collect the (useful) messages from this thread and hang them on a (possibly
short-term) page on my website.
Of course, this all assumes that there are no objections from the
"participants"; in particular if you are in the CC list above, I'm
currently planning to include one of your messages. (Similarly, I'll be
including any future "relevant" messages, again assuming the poster doesn't
object.)
Any other (relevant) matter is welcome.
Nichael "Pull down...
nichael@sover.net ...tear up."
http://www.sover.net/~nichael/ -D. Martin
From cube-lovers-errors@oolong.camellia.org Sat May 31 16:02:29 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA27647; Sat, 31 May 1997 16:02:29 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: Tiffp1@aol.com
Date: Sat, 31 May 1997 09:15:49 -0400 (EDT)
Message-ID: <970531091548_-1732449048@emout01.mail.aol.com>
To: hirsh@cs.rutgers.edu, joemcg3@snowcrest.net
cc: cube-lovers@ai.mit.edu
Subject: Re: The rest of us
DOES ANYONE KNOW ANY STORES NEAR HENDERSON,DURHAM,OR RALEIGH WHERE I CAN BUY
A RUBIK'S CUBE AND A RUBIK' S TRIAMID
From cube-lovers-errors@oolong.camellia.org Sat May 31 16:03:43 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id QAA27659; Sat, 31 May 1997 16:03:42 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sat, 31 May 1997 14:15:25 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970531141525.2140f541@iccgcc.cle.ab.com>
Subject: A* versus IDA*
On Haym Hirsh's description of Professor Korf's work, Dan Hoey wrote:
>Thanks very much for the explanation. It agrees with my understanding
>of the paper, as far as that goes. But do you have a succinct
>explanation of what makes IDA* more tractable than A*? That's the
>part I missed.
Sorry, perhaps not so "succinct", but here goes:
For problems with constant or near constant branching factors, such
as the cube, both A* and IDA* exhibit exponential time complexity.
In "big O" complexity notation this would be O(b^d) where b is the
branching factor and d is the depth of the search.
The major difference between the two algorithms is in respect to
the space complexity. A* minimally requires that all frontier nodes
be stored in memory. This is true of all breadth-first-search (BFS)
algorithms and thus requires O(b^d) space complexity (i.e. exponential
storage -- very bad!). BFS may also incur some additional time complexity
that depends upon the implementation details of how the stored nodes are
searched and managed.
On the other hand, IDA* is a depth-first-search (DFS) algorithm. DFS
algorithms require only a linear amount of storage with respect to search
depth (i.e. it has O(d) storage requirements) since it only needs to store
the current path it is exploring. It uses a cost threshold to determine
when it has gone deep enough and should backtrack to the next unexplored
node (as determined by the current path). Since the cost threshold is based
on a heuristic estimate (really just an informed "guess"), a solution
may not be immediately found if the guesss was too low, and the search may
have to be repeated with an increased cost threshold, in order to find a
solution. At first glance, this may seem inefficient, however when one
considers the branching factor (e.g. somewhere in the neighborhood of 13
for the cube) only a small percentage of the search time may be taken up
by the earlier searches.
The bottom line is that A*'s exponential memory requirements limit
its usefulness to small, one might even say "toy", problems. So an
even bigger issue is that one is likely not to have the memory capacity
to solve the problem at hand using A*. Note that secondary mass storage
devices do not typically help, since they drastically reduce the number
of node evaluations per second.
Having said that, I've neglected the effect of some other factors such as
duplicate node detection. BFS can detect duplicate nodes if it stores all
of them and searches through its list of nodes. IDA* implicitly avoids many
of them because their high cost. IDA* can also be augmented in other ways
(e.g. hash tables) to account for duplicate node checking if this is a
signficant issue with the search space at hand.
There are also some problem dependent factors such as the nature of the
search space and the quality of the cost heuristic. Consider the limiting
case where we have a "perfect cost heuristic" capable of always leading us
down the optimal path. If we had such as thing, the time complexity of
these algorithms would be O(b*d) (i.e. linear with respect to depth).
In that case, it would be overkill to use either of these search methods,
but the notion of a "perfect cost heuristic" helps demonstrate the
importance of good heuristics and corresponding reduction in search
exploration.
Professor Korf has consistently broken new ground with respect to solving
previously unsolved problems. During the mid 80's he was the first to solve
random instances of the 15 puzzle using IDA*. Since he has used so called
"admissible" heuristics, (heuristics which never overestimate the cost
to the goal state) the solutions are guaranteed optimal. I have been
writing search programs for over twelve years and consider IDA* to be a
real "gem". As an aside, I've applied IDA* (augmented with hashing for
duplicate node detection) to solve all but a few hundred of the 32000
instances of Microsoft's "FreeCell" puzzle game that comes packaged
with Win95 and NT.
So to summarize, neglecting details, both A* and IDA* have similar time
complexity requirements, namely exponential. A* also has exponential
storage requirements whereas IDA* has linear memory requirements. The
space advantage of IDA* therefore greatly increases the scope of problems
that can be attacked by this method.
Hope I've served to clarify rather than to further obfuscate.
-- Greg
From cube-lovers-errors@oolong.camellia.org Sat May 31 17:19:14 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA27882; Sat, 31 May 1997 17:19:13 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sat, 31 May 97 16:55:01 EDT
Message-Id: <9705312055.AA16150@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: cube-lovers@ai.mit.edu
Subject: Searching and Metrics in (Korf 1997)
INTRODUCTION
I've read through Rich Korf's paper now, and I have a few ideas on the
paper and how the method might be improved. This is fairly long, so
I've broken it up into two parts. Part 1 has a bit about searching
methods (answering the question I asked in my last message) and some
concerns about the face-turn vs quarter-turn metric. Part 2 covers
some ideas I have on the heuristics he uses. Eventually I hope to air
my concerns over how realistic the memory-based analysis is, but I'm
not sure I understand it well enough yet.
SEARCHING
I asked yesterday what made IDA* a more tractable method than A*. I
think I've got it now. Both use a heuristic function h(p) that is
guaranteed not to underestimate the number of moves to solve position
p. And both may have to check every position p (encountered at depth
g(p)) for which g(p)+h(p) is less than the optimum.
But A* is essentially a breadth-first algorithm. You have to make a
list of all the nodes for which g(p)+h(p) is minimum before you try a
higher value. For this problem, there are too many positions to store
conveniently. IDA* is a variant that allows depth-first search. If
you have a lower bound L, you search depth-first for all positions
that have g(p)+h(p)<=L. You will find a solution if and only if the
optimal solution is at depth L; if you fail you try again with L+1.
The big advantage of IDA* is that you don't need to represent a
database of all the frontier positions at once, you try them one at a
time. IDA* has two disadvantages, though. First, whenever you fail a
search, you lose all the information from previous searches with
smaller values of L, except that they failed. But if the number of
positions at each depth is much larger than the previous (ten or
thirteen times larger, in this case) this loss is small. Second, your
depth-first search may visit the same position more than once, if it's
reachable by more than one near-optimal path. This seems to occur for
only a few percent of positions as far as we've seen, but it
eventually gets to be all of them near the global maximum. The issue
of duplication leads to my question about metrics.
METRICS
Rich uses the face-turn metric, which has been discussed here earlier.
But the justification he gives is one I haven't seen before. He
claims the face metric
... leads to a search tree with fewer duplicate nodes. For
example, two consecutive clockwise twists of the same face leads
to the same state as two counterclockwise twists.
But this is a bad example of duplication. No one who is familiar with
the cube-lovers archives (e.g. my message of 9 January 1981) would
generate both of the above nodes, any more than they would generate
the duplicate nodes caused by composing two commuting moves like F, B
in both possible orders. Rich knows not to do the latter, as he
discusses in the paper.
In case I haven't been sufficiently explicit about this, the way to
avoid this kind of duplication in the quarter-turn metric is to
require:
1. The move after F must not be F',
2. The move after F' or FF must not be F or F',
3. The move after B must not be F, F', or B',
4. The move after B' or BB must not be F, F', B, or B',
5. The same as rules 1-4 with F,B replaced by R,L, respectively, and
6. The same as rules 1-4 with F,B replaced by T,D, respectively.
So two questions remain. First, is there really a difference in the
duplication of positions in the two metrics? I think Jerry Bryan's
table shows that only about 1.74% of the 63 billion positions are
duplicated at 11q. Do we have statistics on duplication for the
face-turn metric? Second, is there any technical justification for
using the face-turn metric? I'm aware that most of the published
literature uses it, and that small numbers of moves sound more
impressive than large ones, but these aren't very satisfying reasons.
As far as I know, the problem of finding optimal solutions can be
fruitfully approached in either of the metrics, or in any of several
other metrics.
[ End of part 1. ]
From cube-lovers-errors@oolong.camellia.org Sat May 31 17:56:04 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA27975; Sat, 31 May 1997 17:56:04 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sat, 31 May 97 17:26:17 EDT
Message-Id: <9705312126.AA16157@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: cube-lovers@ai.mit.edu
Subject: Heuristics in (Korf 1997)
[ As I mentioned, before, this is part 2. Just after I sent part 1, I
saw Greg Schmidt's explanation of IDA*. I hope someone finds the
parts of our messages that don't duplicate each other to be
instructive enough to justify the parts that do. ]
HEURISTIC FUNCTIONS
Herbert Kociemba notes three interesting heuristics based on the
number of moves to reach the subgroup . In fact,
Mike Reid calculated (and Dik Winter verified) the exact distances in
this 2.2-billion element coset space (see archives at 7 Jan 1995 and
following). Mike shows how you could look up this distance in a
64-megabyte table, and Dik suggests how this could be made into a
database half the size (though I think the performance penalty might
be too high).
These coset differences form an admissible heuristic. There are a lot
of other interesting subgroups, and some of their coset spaces may
yield useful heuristics.
But the coset spaces Rich uses are those relative to the subgroup that
fixes a certain number of pieces: The corners, or either of two
subsets of six edges. It's unfortunate he didn't notice that the
latter two tables could use the same database. The way you do this is
to choose your two sets S, T of 6 edges such that there is a whole
cube move m in M for which m(S)=T.
Here's a formalism of how the database for fixing set S works. Make a
database that maps a position p to the length of the shortest sequence
x for which px fixes each piece s in S. Thus the distance h(p) from
position p to the goal position q is the length of pq', for which we
get a lower bound by looking up pq' in the database.
To find the heuristics based on fixing the pieces in T, we could make
a new database. But px(s) = s exactly when (mpm' mxm')(m'(s))=m'(s).
That is to say, when the m-conjugate position (mpm' mxm') fixes the
piece m'(s). So if we look up mpm' in our database, it will give the
length of the shortest sequence mxm' that fixes each m'(s) -- i.e.,
that fixes each t in T.
This also gives us 94 more admissible heuristics for free, at least in
terms of table space. Of course we can use the other 46 elements of
M. What might not be obvious is that the lower bound we get by
looking up x in the database is probably not the same as the lower
bound we get by looking up x'. But the length of x is the length of
x', so we could get 48 more heuristics by looking up the inverse and
it's M-conjugates. By taking the maximum of the 96 values formed by
looking up mpq'm' and mqp'm' in the data base, we may get a much
better lower bound for the solution length.
Of course, we could take any database of lower bounds and use this
process to get up to 96 times as many bounds. The distance to
Kociemba's subgroup is such a lower bound, but it unfortunately is so
symmetric that I think we only get a 6-fold improvement (or perhaps
3-fold; I'm losing my intuition on inverses in those cosets). Perhaps
just fixing an asymmetric subset of edges and corners might be the
best solution.
[ End of part 2. ]
From cube-lovers-errors@oolong.camellia.org Sat May 31 18:34:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id SAA28044; Sat, 31 May 1997 18:34:14 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 1 Jun 1997 00:20:40 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9705312220.AA22245=dik@hera.cwi.nl>
To: cube-lovers@ai.mit.edu
Subject: Re: More on Korf's method
Herbert Kociemba:
> From the description it is evident, that the algorithm Richard E Korf
> uses is basically identical to the the sub-algorithm which is used in
> each stage of my two stage algorithm to solve the cube.
This is right.
Dan Hoey:
> From the description, I think Rich's heuristic functions
> are quite a different type from what you use (though I do not
> understand either exactly yet).
Not really. Rich's heuristic functions are (precomputed) distances
along some coordinates of a multidimensional space. His best apparently
are the corner positions and twice one half of the edge positions.
Similarly in both phases of Herbert's algorithm similar heuristic
functions (pruning tables, filters, ...) are used.
Of course the choice of heuristic function plays an essential role.
For instance, Herbert's original algorithm uses in the first phases
three heuristic functions all three based on a single coordinate
in a three dimensional space. I modified it to use three heuristic
functions based on two dimensional coordinate planes in that same
space. Depending on the problem to solve, this may be better or not,
in this case it is (much) better. A similar modification did I do
in the second phase.
> My guess is that your heuristics have a good chance
> of being more effective at finding optimal solutions for random cubes
> than Rich's, though perhaps some ideas from Rich need to be
> incorporated.
As far as the first is concerned, I think so too. When Herbert's
algorithm is run through to the end it will find an optimal solution
indeed, and in the search for that optimal solution it will use a
new heuristic function for the total solution: the result of previous
suboptimal solutions that come in pretty fast, which is used to prune
the second phase rigorously. I have been able to proof (with my
modification of Herbert's algorithm) some pretty large (18-20 turn)
solutions optimal. I do not think Rich's algorithm will be able to do
that in reasonable time.
> First, we know 18f is not optimal, because the 12-flip is proven to
> require 20f moves exactly (unless Mike Reid made a mistake, or I
> misunderstood).
No, this is right indeed.
> But we _can_ say there's at most one chance in 1024 that the first ten
> random cubes you pick will all be closer than the median to solved.
> So this demonstrates Rich's claim that the median optimal solution is
> very likely 18f.
Something I did estimate already a long time ago. I have done a few
hundred random cubes (a few thousand? I do no longer remember) back
so many years ago. As I remember, I let the program look for optimal
solutions upto 18f (longer is a bit time consuming). As I remember,
there were only very few that could *not* be solved in 18f. There must
be a discussion about this in the archives.
dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From cube-lovers-errors@oolong.camellia.org Sat May 31 19:10:39 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id TAA28171; Sat, 31 May 1997 19:10:38 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 1 Jun 1997 00:57:00 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9705312257.AA23367=dik@hera.cwi.nl>
To: cube-lovers@ai.mit.edu
Subject: Re: Searching and Metrics in (Korf 1997)
> So two questions remain. First, is there really a difference in the
> duplication of positions in the two metrics? I think Jerry Bryan's
> table shows that only about 1.74% of the 63 billion positions are
> duplicated at 11q. Do we have statistics on duplication for the
> face-turn metric?
I do not think there are really statistics. But I have done a complete
analysis on similar puzzles (domino, 2x2x2) where the number of positions
from start increases roughly by the factor you would expect if you
eliminate elementary duplicates as you listed. This both for face
turns and quarter turns. This increase goes on until shortly before
the maximum of turns when the number of new configurations drops
dramatically. I think the figures are in the archives. I have no
reason to expect the case to be different for the cube, rather all my
experiments lead me to predict that the same is the case with the cube.
> Second, is there any technical justification for
> using the face-turn metric?
None, except that the diameter of the group will be larger. (But not
much larger.) And that makes it in Rich's algorithm only computationally
more expensive.
> I'm aware that most of the published
> literature uses it, and that small numbers of moves sound more
> impressive than large ones, but these aren't very satisfying reasons.
> As far as I know, the problem of finding optimal solutions can be
> fruitfully approached in either of the metrics, or in any of several
> other metrics.
The last is almost certainly not true. In the archives there must be an
article by Michael Reid where he made an attempt to generalize Kociemba's
algorithm. I.e. find a subgroup of the total group, phase 1 is to
find a path to that subgroup and phase 2 is to find a path to the
solution. I disremember the entire contents, but as far as I remember
the optimal partitions all used a subgroup which needed only half turns
for at least one face pair. Looking for quarter turn optimization is
not really feasable with such a partition.
dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From cube-lovers-errors@oolong.camellia.org Sat May 31 19:11:01 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id TAA28175; Sat, 31 May 1997 19:11:01 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Sender: Haym Hirsh
Date: Sat, 31 May 97 19:07:01 EDT
From: Haym Hirsh
Reply-To: Haym Hirsh
To: Dan Hoey
Cc: cube-lovers@ai.mit.edu
Subject: Re: More on Korf's method
In-Reply-To: Your message of Fri, 30 May 97 23:15:17 EDT
Message-ID:
> Thanks very much for the explanation. It agrees with my understanding
> of the paper, as far as that goes. But do you have a succinct
> explanation of what makes IDA* more tractable than A*? That's the
> part I missed.
Here are a couple of attempts to explain why and how IDA* is a win over A*.
In my attempt to generate a description for the layman I tried to err
on the side of saying too much rather than too little -- my apologies
if I belabor the obvious for anyone.
The highest-level explanation is that A* may need to store a number of
intermediate results whose number is some exponential function of the
length of the solution -- e.g., b^l: l is the solution length, b,
roughly speaking, is the number of new cubes you can get from a given
cube, aka the "branching factor", and "^" means exponentiation --
whereas IDA* will only store a number of intermediate results whose
number is a linear function of the solution length -- e.g., b*l. The
apparent paradox is that, to do this, IDA* does redundant work --
exploring some intermediate results many times because of its inferior
"bookkeeping". However, it is usually the case that the extra work is
more than paid off by memory savings. This is particularly true for
Rubik's cube, since the higher the branching factor (i.e., roughly 18
for the cube if you count crudely), the less the redundant work.
In a bit more detail, the difference between A* and IDA* is similar to
the difference between breadth-first search and depth-first iterative
deepening. Imagine you want to generate all cubes that are reachable
in d steps from the start. What you can do is generate all cubes that
are one step away, then generate all that are one step away from those
that are one step away (resulting in a list of all that are two steps
away), then all that are one step away from those that are two steps
away (resulting a list of all that are three steps away), etc. At the
final step in this process you have a list of all cubes that are d-1
steps away, and you generate all cubes that are one step away from any
item in this list. This generates all cubes that are d steps away.
The process is known as breadth-first search. It's main problem is
that the list of all cubes that are d-1 steps away will have size
roughly b^(d-1).
Depth-first search, on the other hand, generates all cubes that are
one step away from start, puts all but one of them (i.e., b-1 of them)
on a list, and takes the one that wasn't placed on the list and
(recursively) generates all cubes that are d-1 steps away from it.
When you are done with this first depth-one cube, take one of the
other cubes that are one step from start (which is one of those
stashed away in the afore-mentioned list) and do the same thing,
generating, in turn, all cubes that are d-1 steps away from it. This
continues until all the items that were put on the list have been
explored -- i.e., they have had all cubes at depth d-1 from them
returned. This is depth-first search. Because at each recursion
level it saves only b-1 things, at worst it winds up saving roughly
(b-1)*d cubes in its search.
Now imagine you have a cube that you know is at most (but not
necessarily exactly) d steps from the start, and you want to know what
the shortest solution to it is. One approach would be to do a
breadth-first search to depth 1 and see if you have it, continue to
depth 2 and see if you have it, etc., until you reach depth d. A
second possible approach would appear to be to use depth-first search
to depth d, but this is not guaranteed to give a shortest solution.
To see this, imagine that the cube is two moves from start, but it is
also four moves away if you make the wrong first move. If the result
of that wrong first move is the cube that depth-first search chooses
to "expand" first (with the "correct" one waiting its turn on the list
of cubes to be seen later if you haven't found your cube), you will
find your desired cube via the depth-four solution. You didn't find
the depth-two solution.
This problem with depth-first search leads to the idea of depth-first
iterative deepening. The basic idea of iterative deepening is simple.
First do a depth-first search to depth 1. If you haven't found it,
throw away all your work and start over, doing a depth-first search to
depth 2. Again, if you haven't found it, throw away all your work and
start over, doing a depth-first search to depth 3. This continues,
until you hit the right depth for finding it. This process is
guaranteed to find the shortest solution, but seems silly,
regenerating everything you did in the previous depth-first search
when you add one to the depth. The interesting observation that makes
this a win is that the percent of overall effort spent on previous
depths is only a small fraction of the effort spent on the final
depth-first search. So you penalize yourself a little redundancy, but
are rewarded with much more modest and realistic memory requirements.
The step from this to A* vs IDA* is actually not too large. The basic
idea is to use depth-first search, but instead of using a depth bound
d, instead don't go any farther from a cube if the sum of the number
of steps to get to it plus the guess on how many more steps are needed
to get to a solved cube exceeds some threshold. You start with a
small threshold, and slowly keep increasing it, each time starting
over again from scratch, until the threshold is just barely high
enough to find the solution. If you do this in the correct way (for
example, upping the threshold each time in the appropriate fashion
based on the values you observed in your previous iteration), you can
prove that the solution IDA* finds is the shortest possible (as long
as the solution-length guesser never over-estimates the correct value).
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 00:58:07 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA28890; Sun, 1 Jun 1997 00:58:06 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 0:19:28 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970601001928.2140f226@iccgcc.cle.ab.com>
Subject: Re: Searching and Metrics in (Korf 1997)
Dan Hoey wrote:
>I've read through Rich Korf's paper now, and I have a few ideas on the
>paper and how the method might be improved...
I feel that there is a fundamental point regarding cube solving approaches
that is worth making. First there is what I shall call the "Kociemba approach".
I would loosely paraphrase this approach as follows:
"If one examines the behavior of the cube in great detail and applies group
theoretic concepts to the spaces generated by the cube, one can apply this
analysis to great effect towards producing an algorithm capable of solving
the cube."
Then there is what I shall refer to as the "Korf approach". Loosely
paraphrased as:
"The cube is a difficult combinatorial puzzle that provides a fertile
ground for advancing the state of the art of search methods."
It should be apparent that the goal of these two approaches is quite
different. The "Kociemba approach" is focused only on solving the
cube. All domain specific knowledge about the cube problem, such as
specific group theoretic properties of the cube, can and should be
applied. Whereas the "Korf approach" attempts to be a general
approach, applicable to other problems, not just the cube (i.e. the
cube problem is merely incidental). This approach should not rely
on methods that are specific to a single (or at least very narrow)
class of problems. This is close to the definition of so called
"weak" methods in AI. Weak methods are those that do not rely
heavily on human provided domain specific knowledge. For example,
an expert system does not classify as a weak method, whereas a
search method that is given little more than a description of
the problem space and a desired goal does.
Stepping back a bit, I would say that Korf's method applies to
a broad class of problems, much larger than the cube alone. In
effect, his method says:
"If one can partition the desired end goal of a problem into subgoals,
and for each subgoal provide a cost to achieve that subgoal, then one
can use this information to produce a higher quality (i.e. "more informed"
in search parlance) heuristic. An effective way to achieve this is by
firt precomputing the cost information associated with each subgoal and
storing it in a table. This table can be reused across multiple problem
instances and represents an effective way to utilize available memory
to improve the effectiveness of the search."
And so I feel it is necessary to say that any suggestion for improving
Korf's method, should take this distinction into account since solving
the cube is only incidental to the emphasis of the research work that
professor Korf is involved in.
In no way am I intending to imply that methods which are not consistent
with the "Korf approach" should not be considered. In fact, I find this
a fascinating topic. I'm just pointing out it is both a virtue and a
goal of his approach that he hasn't leveraged extended knowledge of
"cube principles" in order to devise an effective algorithm.
I hope I haven't misrepresented Mr. Kociemba or Mr. Korf in this
discussion. If so, please speak up.
-- Greg
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 05:20:49 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id FAA29296; Sun, 1 Jun 1997 05:20:49 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <33913E47.F3C@hrz1.hrz.th-darmstadt.de>
Date: Sun, 01 Jun 1997 11:17:59 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Generalisation of Korf's method?
References: <9705312220.AA22245=dik@hera.cwi.nl>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Greg wrote:
> It should be apparent that the goal of these two approaches is quite
> different. The "Kociemba approach" is focused only on solving the
> cube. All domain specific knowledge about the cube problem, such as
> specific group theoretic properties of the cube, can and should be
> applied. Whereas the "Korf approach" attempts to be a general
> approach, applicable to other problems, not just the cube (i.e. the
> cube problem is merely incidental).
Maybe. But I'm not sure about that. I am no specialist concerning IDA*
search, but I think it is worth while to examine, for which general
class of problems a two phase algorithm is profitable, that means doing
IDA* search to some subgoal which consists of an appropriate subset
(including the end goal) of the problem space (phase1) and appropriate
heuristic functions, then doing IDA* search from here to the end goal
(phase2). Then continuing with IDA* search in phase1, creating more
solutions and then doing IDA* search in phase2 with a maximal length of
L=N-n1-1, where N is the length of the already found (usually not
optimal) last solution and n1 is the lenght in phase1.
L decreases for two reasons when the alogrithm is running: Every new
solution found will have an length N at least one smaller then the
previous solution and nl will increase also.
If you have enough time, you wait until nl=N, then you have the
guaranteed optimal overall solution.
This approach could be valuable, if the problem space is very large, and
in this case you get a sequence of solutions with decreasing length
which might be better than waiting for the optimal solution for 100
years with single IDA* search.
In the case of Rubik's cube the sequences of solutions seem to converge
very quick to a solution with minimal overall length in many cases,
though it might be difficult to prove this rigorously.
I would be interesting to see, how the two phase algorithm handles the
10 cubes, Rich Korf solved.
Dik.Winter@cwi.nl wrote:
> Of course the choice of heuristic function plays an essential role.
> For instance, Herbert's original algorithm uses in the first phases
> three heuristic functions all three based on a single coordinate
> in a three dimensional space.
This is not quite true. I don't think that the algorithm would have
worked then satisfactory. I did not add the details in the description
of the algorithm in CFF28, because I did not want to hide the
principles.
Because of the limited memory (1MB!! at this time) I worked in four
dimensional space and also used heuristic functions based on
two-dimensional coordinate-planes. To get 4 dimensions, I did not use
the turns of the 6 faces, but I fixed the DLB-corner. Instead of the L,
B, and D turns I did R, F and U turns together with a slice move then,
which is of course identical with L, B and D turns and then turning the
whole cube. The additional coordinate is the position of the
center-cubies(24 states). In this way you have only 7! corner
permutations (instead of 8!) and 3^6 possible corner orientations
(instead of 3^7). Only this fact made it possible for me use two
dimensional coordinate planes for the heuristic functions.
Herbert
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 17:21:28 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA00898; Sun, 1 Jun 1997 17:21:28 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
X-Sender: ddyer@10.0.2.1
Message-Id:
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sun, 1 Jun 1997 14:09:08 -0800
To: cube-lovers@ai.mit.edu
From: Dave Dyer
Subject: new search heuristics
I wonder about the local "shape" of the distance heuristics accuracy. How inaccurate are
they typically, and how inaccurate can the worst cases be? Is it typically the case
that all the estimates for nearby positions are similar, or are there outliers?
Are the good and bad guesses uniformly distributed, or are they clustered? Depending
on the shape of the space, I can imagine strategies specifically designed to improve,
by looking a little harder for a good estimate.
Are there useable heuristics which are guaranteed to overestimate
distance? If so, then they could be used in concert with positions
known to be distant from solved to improve the bounds for A*. For example,
with an overestimating heuristic (n) for a position known to be more than 18
moves from start, we could use 18-n as an independant underestimate of distance
from start.
---
My home page: http://www.andromeda.com/people/ddyer/home.html
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 18:00:42 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id SAA00994; Sun, 1 Jun 1997 18:00:42 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 01 Jun 1997 17:59:49 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Description of algorithm for finding minimal-move solutions to
Rubik's Cube
In-reply-to: <338F7124.73A6@hrz1.hrz.th-darmstadt.de>
To: Cube-Lovers
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Sat, 31 May 1997, Herbert Kociemba wrote:
> Having found a solution in stage1 and stage2 the algorithm does not
> stop, but generates other solutions in stage1. So if for example we have
> 10 moves in stage1 and 12 moves in stage2, there might be a solution
> with 11 moves in stage1 but only 10 moves in stage2. Running long
> enough, the algorithm will find the overall optimal solution, having no
> moves in stage2 then.
I have always been curious about the termination criteria for your
algorithm -- that is, how long is "long enough"?. It appears that you are
effectively moving moves from stage2 to stage1 until stage2 is empty. I
wonder if you could describe this process a little further. I have always
rather naively assumed that you were (for example) combining an R at the
end of stage1 with an R' at the end of beginning of stage2, simply
cancelling out the moves. But you certainly appear to be doing some a
little more elaborate than simple cancellation.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:39:09 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01501; Sun, 1 Jun 1997 21:39:09 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 1 Jun 97 19:45:11 EDT
Message-Id: <9706012345.AA19309@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: SCHMIDTG@iccgcc.cle.ab.com, cube-lovers@ai.mit.edu
Subject: Re: Searching and Metrics in (Korf 1997)
I wrote:
>I've read through Rich Korf's paper now, and I have a few ideas on the
>paper and how the method might be improved...
Greg Schmidt replies:
> ...And so I feel it is necessary to say that any suggestion for improving
> Korf's method, should take this distinction into account since solving
> the cube is only incidental to the emphasis of the research work that
> professor Korf is involved in....
The method I suggested for reusing tables for new heuristics should be
applicable to any group-theoretic puzzle for which there are
symmetries mapping generators to generators. For instance, the N^2-1
puzzles have the 8-fold symmetry D4, and so could have one set of
tables used for 16 heuristics.
Given the central nature the memory-performance tradeoff plays in the
paper, I imagine this is quite relevant to Rich's research.
Of course, I also discussed a number of other topics in that message,
but I don't think they were the ones you were addressing in your remarks.
Dan
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:38:37 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01493; Sun, 1 Jun 1997 21:38:36 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 01 Jun 1997 18:20:28 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Description of algorithm for finding minimal-move solutions to
Rubik's Cube
In-reply-to: <338F7124.73A6@hrz1.hrz.th-darmstadt.de>
To: Cube-Lovers
Reply-to: Jerry Bryan
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Sat, 31 May 1997, Herbert Kociemba wrote:
> Dik Winter proved, that 12 moves always suffice to get to this subgroup.
>
> Michael Reid proved, that 18 moves always suffice in this subgroup.
If I interpret this correctly, what you have at this point is a
Thistlethwaite algorithm with G -> ____ -> I, proving that
any position can be solved in no more than 30f moves. Is this the correct
interpretation? But more importantly, is there anything in the part of
your algorithm where you combine stage1 and stage2 which would establish
an upper bound which is less than 30f?
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:38:55 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01497; Sun, 1 Jun 1997 21:38:55 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 01 Jun 1997 18:35:50 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Description of algorithm for finding minimal-move solutions to
Rubik's Cube
In-reply-to: <338F7124.73A6@hrz1.hrz.th-darmstadt.de>
To: Cube-Lovers
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Sat, 31 May 1997, Herbert Kociemba wrote:
>
> In phase 1, the cube is transformed to an element of the subgroup
> generated by ____.
.....
> The "heuristic functions" consist of three tables, using 4
> bits for each entry. The first table stores the minimum numbers to solve
> the 2187*2048 possible states to restore the orientation of both edges
> and corners, the other tables have 2187*495 and 2048*495 entries and
> store the corresponding minimum numbers.
Obviously, any conjugate of ____ would do as well as any
other. Have you looked for conjugate positions in your table? For
example, you might have a position x which is 10 moves from
____, but position y which is a conjugate of x might be only
be 9 moves from ____. In this case, you might as well solve
y, knowing that the number of moves to solve x is the same as the number
of moves to solve y, and knowing that the solutions are conjugate. Also,
by subjecting your entire table to this kind of analysis (if you haven't
already), you might find an upper bound for stage1 which is less than 12f.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:39:26 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01505; Sun, 1 Jun 1997 21:39:26 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 1997 01:45:38 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9706012345.AA07277=dik@hera.cwi.nl>
To: cube-lovers@ai.mit.edu
Subject: Re: Description of algorithm for finding minimal-move solutions to Rubik's Cube
> I have always been curious about the termination criteria for your
> algorithm -- that is, how long is "long enough"?.
"Long enough" means that it is certain that no shorter solutions can
be found.
> It appears that you are
> effectively moving moves from stage2 to stage1 until stage2 is empty.
Not really. What is happening is a breadth first search in phase1. The
search is continued although phase1 solutions are found (and a lot are
found on the way). This is continued until you find that deepening the
search in phase1 will not give shorter solutions. For each phase1
solution a phase2 solution is looked for, also in a breadth first manner,
and also as deep as is needed to find shorter total solutions.
This method finds very quickly solutions for phase1 in about 10-12 turns
with matching solutions in phase2 with 12-14 turns for a total of about
22-26 (very rarely the first solution found has over 26 turns). When
for instance a solution is found with 10 turns in phase1 and 12 in phase2
(breadth first so this is optimal with the particular path in phase1),
search in phase1 continues and for each new solution in phase1 solutions
are searched for in phase2 with limited depth. So first 10 turns in
phase1 and at most 11 in phase2, followed by 11 in phase1 and at most
10 in phase2.
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:39:51 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01513; Sun, 1 Jun 1997 21:39:51 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 01 Jun 1997 21:06:18 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Description of algorithm for finding minimal-move solutions to
Rubik's Cube
In-reply-to: <199705300024.RAA18247@denali.cs.ucla.edu>
To: Richard E Korf
Cc: Cube-Lovers@ai.mit.edu
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Thu, 29 May 1997, Richard E Korf wrote:
> For example, if we consider just the corner cubies, there are only about 88
> million possible states they could be in (8!x3^7). We exhaustively build and
> store a table, using breadth-first search, that tells us the minimum number of
> moves needed to solve just the corner cubies from every possible combination,
> ignoring the edge cubies. This value ranges from 0 to 11 moves, averages 8.764
> moves, and requires only 4 bits per state. (We could reduce this further using
> an idea of Dan Hoey's published in this list awhile ago.) This table only has
> to be computed once, taking about a half hour, and requires about 42 megabytes
> of memory to store (a megabyte is 1048576 bytes).
I have an old program, developed on a 286 PC with a 10MB harddisk, which
stores the entire solution for the corners in about 2.5MB. Details are in
the archives, but it uses representatives of the form Repr{m'Xmc}. The
representatives consitute the solution of the 2x2x2 and take about .625MB.
The remaining storage is in a format I call Repr{m'Xmc}*C to take care of
the corners of the 3x3x3. However, I would guess that even though this
format would save a great deal of memory, it would also very much slow
your program down, rather than speeding it up, because of the rather
arcane indexing required.
This brings up a point which I think has been taken for granted in the
archives but which I think has never been spelled out in detail. In its
most simple-minded form, a search involves storing both permutations and
distances from Start. But sometimes you can get by with storing only the
permutations, and sometimes you can get by with storing only the
distances.
In this case, you are storing the entire corner group, and therefore you
can get by with storing only the distances. That is, you have obviously
developed an easy-to-calculate function and an inverse to map between the
corner permutations and an index set, say 1..|GC| or maybe 0..|GC-1|.
Hence, you don't need to store the permutations themselves. My
Repr{m'Xmc} technique stores only a subset of the permutations. There is
a one-to-one correspondence between the subset which is stored and an
index set, but it is not very easy to calculate (actually, it involves
some binary searching).
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:40:09 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA01521; Sun, 1 Jun 1997 21:40:08 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 21:22:20 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970601212220.2140c63e@iccgcc.cle.ab.com>
Subject: Re: Generalisation of Korf's method?
Herbert Kociemba wrote:
>Greg wrote:
>
>> It should be apparent that the goal of these two approaches is quite
>> different. The "Kociemba approach" is focused only on solving the
>> cube. All domain specific knowledge about the cube problem, such as
>> specific group theoretic properties of the cube, can and should be
>> applied. Whereas the "Korf approach" attempts to be a general
>> approach, applicable to other problems, not just the cube (i.e. the
>> cube problem is merely incidental).
>
>Maybe. But I'm not sure about that. I am no specialist concerning IDA*
>search, but I think it is worth while to examine, for which general
>class of problems a two phase algorithm is profitable, that means doing
>IDA* search to some subgoal which consists of an appropriate subset
>(including the end goal) of the problem space (phase1) and appropriate
>heuristic functions, then doing IDA* search from here to the end goal
>(phase2). Then continuing with IDA* search in phase1, creating more
>solutions and then doing IDA* search in phase2 with a maximal length of
>L=N-n1-1, where N is the length of the already found (usually not
>optimal) last solution and n1 is the lenght in phase1.
>L decreases for two reasons when the alogrithm is running: Every new
>solution found will have an length N at least one smaller then the
>previous solution and nl will increase also.
>If you have enough time, you wait until nl=N, then you have the
>guaranteed optimal overall solution.
>
>This approach could be valuable, if the problem space is very large, and
>in this case you get a sequence of solutions with decreasing length
>which might be better than waiting for the optimal solution for 100
>years with single IDA* search.
I think the two phase approach is relevant to a larger class of problems
than just the cube, or for that matter, combinatorial puzzles in general.
In fact, I think the two phase aspect is what is commonly referred to
as "bidirectional search". When it can be applied, it has the potential
for reducing search complexity from O(b^d) to O(b^(d/2)). That is to
say that it can cut the exponent of an exponential search in half.
My earlier comment was more in regards to leveraging specific knowledge
of cube groups. I'm not sure that specific knowledge of cube groups is
highly applicable to Korf's work as this seems in conflict with the
desire to develop general search methods that are domain independent.
I suspect that he might consider this "cheating" with respect to the
thrust of his work having greater applicability outside combinatorial
puzzle problems. But if the goal is to develop a highly optimized
Rubik's cube solver, then inputting specific knowledge of the cube
problem is reasonable.
Although I don't yet fully understand the pruning tables used in Kociemba's
algorithm, I suspect they are different than Korf's tables (which I do
understand), especially with respect to how they are applied to pruning
the search.
I have a hunch that combining Korf's heuristic methods with a Kociemba
style two phase approach (a.ka. "bidirectional search) could result in
a more effective cube solver.
-- Greg
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:10:30 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03412; Mon, 2 Jun 1997 13:10:30 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 22:39:43 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970601223943.2140c63e@iccgcc.cle.ab.com>
Subject: Re: A* versus IDA*
Jerry Bryan wrote:
>On Sat, 31 May 1997 SCHMIDTG@iccgcc.cle.ab.com wrote:
>
>> As an aside, I've applied IDA* (augmented with hashing for
>> duplicate node detection) to solve all but a few hundred of the 32000
>> instances of Microsoft's "FreeCell" puzzle game that comes packaged
>> with Win95 and NT.
>>
>
>Interesting. I once upon a time found some notes on the Web that
>indicated that all but one of the prepackaged instances of FreeCell had
>been solved by hand (by humans). I gather that many people worked on the
>project in a parallel processing mode. Only one of the games was said to
>be unsolvable, and this was claimed to have been proven by computer
>search.
The unsolvable instance is FreeCell game #11982. And you are correct
to point out that a computer program has proven the unsolvability of
this particular instance. It is a curious fact that only one of the
32000 instances turned out to be unsolvable.
[...some discussion of Baker's game deleted...]
>Nevertheless, my program demonstrated that the game can be won about 60%
>of the time. I am sure that your IDA* FreeCell program, were it to be
>adapted to Baker's Game, would be vastly more effective than my rather
>primitive program was. Would you have any interest in investigating
>Baker's Game with your program.?
I am familiar with Baker's game and as you mentioned, it is harder
to win at than FreeCell. It would be fairly simple to adapt my
program to Baker's game and it would be interesting to compare performance.
As I mentioned, my program uses a sort of "hash cache" for duplicate
node checking (as the search space for FreeCell is a graph, not a tree).
There is a flaw in this mechanism as some false hits can occur and effectively
over prune the search tree. I believe that was why I was unable to solve
approximately 300 of the 32000 instances. I don't know if that flaw would
be amplified in Baker's game where there are fewer paths to a solution as
compared to FreeCell. Unfortunately, eliminating this behavior would
require a complete overhaul of the duplicate node checking mechanism
as opposed to a simple "quick fix".
At any rate, I'm willing to make this program available to interested
parties (BTW, its written in C++). I would prefer to upload it to an
FTP site if possible. Is anyone aware of an FTP site available for use
by cube-lovers?
-- Greg
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:10:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03408; Mon, 2 Jun 1997 13:10:15 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 22:03:44 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970601220344.2140c63e@iccgcc.cle.ab.com>
Subject: Re: Searching and Metrics in (Korf 1997)
Dan Hoey wrote:
>The method I suggested for reusing tables for new heuristics should be
>applicable to any group-theoretic puzzle for which there are
>symmetries mapping generators to generators. For instance, the N^2-1
>puzzles have the 8-fold symmetry D4, and so could have one set of
>tables used for 16 heuristics.
>
>Given the central nature the memory-performance tradeoff plays in the
>paper, I imagine this is quite relevant to Rich's research.
I suppose it depends upon where one is willing to draw the line with
respect to so called "weak methods" (i.e. search techniques that don't
rely on information about the problem domain). If the methods are specific
only to group theoretic puzzles, I think they are interesting and useful,
but somewhat less relevant to advancing the state of the art of weak methods
as applied to larger classes of problems. I'm under the impression that
Rich's research is focused on the latter, as opposed to the goals of the
typical hard-core cube enthusiast.
By the way, if someone is aware of a paying full-time research position
focusing only on solving the cube, and related, puzzles, please let me
know and I'll sign up tomorrow! :)
Having said that, I think the table optimization you described is a very
clever way to take advantage of symmetries for these types of problems.
Eventually, I hope that the knowledge gained by this, and related, threads
can be synthesized into a new algorithm that surpasses all previous cube
solving program. Now that would be exciting to cube-lovers!
-- Greg
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:10:47 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03416; Mon, 2 Jun 1997 13:10:46 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <3.0.32.19970601235733.0068d4f0@pop.radix.net>
X-Sender: pilloff@pop.radix.net (Unverified)
X-Mailer: Windows Eudora Pro Version 3.0 (32)
Date: Sun, 01 Jun 1997 23:57:43 -0400
To: cube-lovers@ai.mit.edu
From: Hersch Pilloff
Subject: 5x5x5 practical Q's
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Hello,
I'm proud to say that after significant quantities of blood, sweat, and
tears, I have finally solved the 5x5x5 cube. I used some techniques from
the good old 3x3x3 cube as well as some general techniques I've found
useful over the past (often of the form A R A' R' where A is a set of
rotations preserving one face and R is a rotation of that face). One
problem I faced along the way and have not been able to solve to my
satisfaction is an issue of parity. I often put the big cube in a state
where exactly two "equivalent" off-center edge pieces on the upper face
were interchanged with one another. They had the correct orientation, I
simply needed to switch the two pieces. I would like to know if anyone has
an effective means of dealing with this situation.
It was immediately apparent that the ARA'R' technique would not work
because interchanging two pieces requires a change in parity which the
ARA'R' won't produce. I tried interchanging "identical" pieces from the
interior of the cube and then returning to the top face to see if any
change had resulted. This was met with only marginal sucess-- after enough
fiddling I was able to produce two pairs of interchanged, properly
oriented, off-center edge pieces on the upper face which I could, after
some further manipulation, handle with an ARA'R' scheme. Still, this isn't
very satisfactory to me because I don't much like the idea of having to
randomly interchange pieces until I produce a workable situation without
any more definite strategy. Undoubtedly, most of you have been more
successful at this endeavor than I have, so I'd appreciate any available
wisdom.
Thanks,
Mark Pilloff
P.S. I'm not using my usual account. If you email a reply to me, please
send it to mdp1@uclink4.berkeley.edu and not whatever return address is
listed above or below. Or just mail the list-- I'm on that as well.
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:11:24 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03430; Mon, 2 Jun 1997 13:11:23 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 02 Jun 1997 09:50:34 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Re: A* versus IDA*
In-reply-to: <970531141525.2140f541@iccgcc.cle.ab.com>
To: cube-lovers@ai.mit.edu
Reply-to: Jerry Bryan
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us
On Sat, 31 May 1997 SCHMIDTG@iccgcc.cle.ab.com wrote:
> On the other hand, IDA* is a depth-first-search (DFS) algorithm. DFS
> algorithms require only a linear amount of storage with respect to search
> depth (i.e. it has O(d) storage requirements) since it only needs to store
> the current path it is exploring. It uses a cost threshold to determine
> when it has gone deep enough and should backtrack to the next unexplored
> node (as determined by the current path).
Like everybody else, I am still trying to grasp IDA*. The way it
backtracks reminds me a little bit of alpha-beta pruning. There are
major differences, of course, because alpha-beta works with two person
games such as chess. But the pruning idea seems very similar anyway.
This raises a question. It has been twenty years or so since I have
worked on a problem with alpha-beta, but my best recollection is that it
basically reduces the effective branching factor by the square root. For
example, chess is usually considered to have a branching factor in the
high 30's or low 40's, and alpha-beta gets the effective branching
factor down to about 6 or 7. (The efficacy of this effect is dependant
on how well the nodes are ordered at each level of the tree.)
So can we say something similar about IDA*? That is, is there an
effective branching factor which is less than the actual branching
factor? Is a little bigger than 13 for face turns effectively reduced
to some j, and is a little bigger than 9 for quarter turns effectively
reduced to some k? It would seem so to me, and your algorithm then
becomes O(j^d) or O(k^d) instead of O(b^d).
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:11:40 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03434; Mon, 2 Jun 1997 13:11:39 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 02 Jun 1997 11:23:05 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Re: Searching and Metrics in (Korf 1997)
In-reply-to: <9705312055.AA16150@sun34.aic.nrl.navy.mil>
To: cube-lovers@ai.mit.edu
Reply-to: Jerry Bryan
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us
On Sat, 31 May 1997, Dan Hoey wrote:
>
> So two questions remain. First, is there really a difference in the
> duplication of positions in the two metrics? I think Jerry Bryan's
> table shows that only about 1.74% of the 63 billion positions are
> duplicated at 11q. Do we have statistics on duplication for the
> face-turn metric? Second, is there any technical justification for
> using the face-turn metric? I'm aware that most of the published
> literature uses it, and that small numbers of moves sound more
> impressive than large ones, but these aren't very satisfying reasons.
> As far as I know, the problem of finding optimal solutions can be
> fruitfully approached in either of the metrics, or in any of several
> other metrics.
>
I do not think there is really any difference of the sort that Prof.
Korf was talking about. I have done extensive breadth-search searches
with both the quarter-turn and face-turn metrics (although I have done
more work on the quarter-turn). Dan has posted what I will call
"syllable analyses" for both metrics. Dan's "syllable analyses" (e.g.,
FB=BF, etc., where FB and BF are our syllables) provide an upper bound
on possible branching factors. The observed branching factors are
extremely close to Dan's upper bounds for both metrics out to the levels
I have searched. Hence, I see no advantage either way.
Dan's syllable analyses are essentially based on short relations.
Observed branching factors deviate from Dan's tight bounds only to the
extent that there exist longer relations which are not taken into
account by Dan's formulas. The fact that the bounds are tight simply
reflects that there are not very many longer relations, at least out to
the level that has been searched.
Far enough from Start, there will be a major break in branching factors,
and the break will occur closer to Start for the face-turn metric than
for the quarter-turn metric. This break in branching factors will be
reflective of longer relations which do not simply contain shorter
relations. And again, these longer relations will be shorter in
face-turns than in quarter-turns. But that's just the way the metrics
work.
We seem to be degenerating into one of our periodic face-turn vs.
quarter-turn arguments (I am a confirmed quarter-turner because
quarter-turns are conjugate). But this reminds me of something I ran
across in Singmaster which I found curious. Singmaster is a face-turner,
but he nevertheless defined the length of a position as the number of
quarter-turns from Start for the position. In other words, he did not
identify the number of moves to solve a position with the length of the
position. Is his definition of "length" standard in group theory? If
so, we would have only one length for each position, although we could
have several metrics for "number of moves from Start" (face-turns and
quarter-turns are by no means the only possible metrics). In the same
vein, is the term "diameter" reserved to mean the maximum length for any
position so that the diameter is unique, or do we have one diameter for
quarter-turns, another diameter for face-turns, etc.?
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:11:05 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03426; Mon, 2 Jun 1997 13:11:04 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 02 Jun 1997 09:29:19 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Size of God's Algorithm
In-reply-to: <970531141525.2140f541@iccgcc.cle.ab.com>
To: cube-lovers@ai.mit.edu
Reply-to: Jerry Bryan
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us
On Sat, 31 May 1997 SCHMIDTG@iccgcc.cle.ab.com wrote:
> On the other hand, IDA* is a depth-first-search (DFS) algorithm.
This reminds me of an note I have been meaning to post to the list for a
long time. The issue is, how big is God's algorithm? By that, I do not
mean how large is cube space, neither the size of G nor the number of
M-conjugacy classes. What I mean is, what is the size of the smallest
program which can calculate God's algorithm? In the size, we have to
include not only the executable code, but also the size of any tables.
To be more specific, suppose our task is to write a totally
self-contained function called cubelen which given a position x would
return the number of moves from Start for that position (e.g.,
L := cubelen(x); ). We are specifically not worried about running
time, which might be longer than the age of the universe. For example,
given the existence of cubelen, we could call it once for each x in G,
and thereby determine the complete frequency distribution of distances,
including the group diameter.
Under these rules, the answer is actually very silly (or it may be the
rules which are silly). With tight assembler coding, it can be done in
about 10^4 bits, certainly no more than 10^5 (about 10^3 to 10^4 bytes).
All we have to do is calculate all processes containing (in turn) 0
moves, 1 move, 2 moves, etc., and comparing each generated position with
x until it matches. We would make no attempt to eliminate sequences
such as RR', nor would we make any attempt to recognize that RL is the
same position as LR. We only have to store two positions, x and the
current product, and there is no real tree structure.
This is very roughly speaking a depth search first, except that the
bookkeeping requirements (and attendant memory requirements) are a bit
less than with a typical depth search search. That is, all you have to
keep track of is an index set from 1 to the number of moves (12 for
quarter-turns, 18 for face-turns), with one index for each level of the
search. The branching factor is a constant, equal to the size of the
index set.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:16:04 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03468; Mon, 2 Jun 1997 13:16:03 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 1997 10:10:29 -0700
From: Richard E Korf
Message-Id: <199706021710.KAA21887@denali.cs.ucla.edu>
To: cube-lovers@ai.mit.edu
Subject: miscellaneous comments
Dear Cube-Lovers,
Here's a few comments on the recent flurry of messages. I guess I owe you all
an apology for being partly responsible for filling up your mailboxes lately,
yet here I go, sinning again.
Perhaps it is no longer necessary due to the excellent messages by Haym
Hirsh, Greg Schmidt, and Dan Hoey, but I've written a 20 page survey article on
artificial intelligence search algorithms that I would be happy to send to
anyone on request. The first 10 pages cover things like breadth-first search,
depth-first search, depth-first iterative deepening, A*, and
Iterative-Deepening-A*. The rest talks about two-player game search and
constraint satisfaction. When ordering, please specify if you are interested in
the Rubik's Cube article or the search article, and allow 6 to 8 hours for
delivery.
Regarding the quarter-turn metric, as long as one is careful to eliminate the
obvious duplicate states as Dan points out, it shouldn't matter much whether you
use the quarter-turn or face-turn metric. While solutions are longer in the
quarter-turn metric, the branching factor, which is the average number of
operators that apply to a given state, is correspondingly lower. The branching
factor for the face-turn metric is about 13.34847, and the branching factor for
the quarter-turn metric should be about 9.
Jerry Bryan is right on when he talks about the memory savings from storing
an entire subgroup, and the importance of efficient indexing. For my heuristic
tables, no states are actually stored, just the number of moves to solve them.
The states are "respresented" by the indexes in the table.
Here's the indexing problem. Write out all the permutations of say 4
elements, 24 in all, in lexicographic, or any other, order. Now number the
permutations from 0 to 23. The problem then is given a permutation of N
elements, compute its sequential number in your ordering scheme. The obvious
algorithms do this in roughly N^2 time, but it would be nice to able to do it
faster.
To put all this in perspective, there are two obvious but impractical
implementations of "God's algorithm". One is brute-force depth-first
iterative-deepening search, with no heuristic functions. At a million twists per
second, this would take about 700,000 years on average, but almost no
memory. The other is a complete lookup table storing every state. This would be
very fast once the table was built but would take a few bits for each one of the
4x10^19 states. We don't have the time for the former approach, nor the storage
for the latter. But by using both a lot of time, and a lot of memory, we can
find optimal solutions. Most of the different design choices presented by these
types of approaches amount to a tradeoff between time and space. It remains to
be seen what choices lead to the best algorithms.
-rich
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:55:08 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id NAA03632; Mon, 2 Jun 1997 13:55:07 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 1997 13:39:44 -0400
Message-Id: <2Jun1997.131752.Alan@LCS.MIT.EDU>
From: Alan Bawden
Sender: Cube-Lovers-Request@ai.mit.edu
To: Cube-Lovers@ai.mit.edu
In-reply-to: SCHMIDTG@iccgcc.cle.ab.com's message of Sun, 1 Jun 1997 22:39:43 -0400 (EDT) <970601223943.2140c63e@iccgcc.cle.ab.com>
Subject: ftp://ftp.ai.mit.edu/pub/cube-lovers/contrib
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 22:39:43 -0400 (EDT)
...
At any rate, I'm willing to make this program available to interested
parties (BTW, its written in C++). I would prefer to upload it to an
FTP site if possible. Is anyone aware of an FTP site available for use
by cube-lovers?
This seems like a good time to remind everyone that there -is- a
Cube-Lovers FTP archive for situations such as this:
ftp://ftp.ai.mit.edu/pub/cube-lovers/contrib
I'm always happy to put more things into this directory, provided you don't
make it too much work for me. The ideal contribution consists of a single
file (preferable a gzipped tar file) plus a -brief- description for the
README file. You've got to figure out how to get the file to me in some
reasonable way -- letting me pick it up from some other anonymous FTP site
is easiest.
If you make me think too hard, for example by expecting me to compose the
description for the README file, or by making me pick out the Cube related
files from some larger collection, then I'm liable to never get around to
doing it.
I also reserve the right to redescribe, repackage, rename, recompress or
totally reject your contribution.
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 17:31:46 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04143; Mon, 2 Jun 1997 17:31:46 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <3393319D.774B@ibm.net>
Date: Mon, 02 Jun 1997 13:48:29 -0700
From: Jin "Time Traveler" Kim
Organization: The Fourth Dimension
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: 5x5x5 practical Q's
References: <3.0.32.19970601235733.0068d4f0@pop.radix.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hersch Pilloff wrote:
>
> Hello,
>
> I'm proud to say that after significant quantities of blood, sweat, and
> tears, I have finally solved the 5x5x5 cube. I used some techniques from
> the good old 3x3x3 cube as well as some general techniques I've found
> useful over the past (often of the form A R A' R' where A is a set of
> rotations preserving one face and R is a rotation of that face). One
> problem I faced along the way and have not been able to solve to my
> satisfaction is an issue of parity. I often put the big cube in a state
> where exactly two "equivalent" off-center edge pieces on the upper face
> were interchanged with one another. They had the correct orientation, I
> simply needed to switch the two pieces. I would like to know if anyone has
> an effective means of dealing with this situation.
>
> It was immediately apparent that the ARA'R' technique would not work
> because interchanging two pieces requires a change in parity which the
> ARA'R' won't produce. I tried interchanging "identical" pieces from the
> interior of the cube and then returning to the top face to see if any
> change had resulted. This was met with only marginal sucess-- after enough
> fiddling I was able to produce two pairs of interchanged, properly
> oriented, off-center edge pieces on the upper face which I could, after
> some further manipulation, handle with an ARA'R' scheme. Still, this isn't
> very satisfactory to me because I don't much like the idea of having to
> randomly interchange pieces until I produce a workable situation without
> any more definite strategy. Undoubtedly, most of you have been more
> successful at this endeavor than I have, so I'd appreciate any available
> wisdom.
>
> Thanks,
> Mark Pilloff
>
> P.S. I'm not using my usual account. If you email a reply to me, please
> send it to mdp1@uclink4.berkeley.edu and not whatever return address is
> listed above or below. Or just mail the list-- I'm on that as well.
I found that the solution book for the Rubik's Revenge was also a very
useful tool to solving the 5x5x5. The only pieces I had to figure out
myself through trial and error were the interior face pieces that have
edge contact with the middle piece (i.e. four pieces that including the
center piece would make a Plus "+" sign).
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 17:32:10 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04147; Mon, 2 Jun 1997 17:32:10 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <3393350F.6541@hrz1.hrz.th-darmstadt.de>
Date: Mon, 02 Jun 1997 23:03:11 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
CC: Richard E Korf
Subject: Detailed explanation of two phase algorithm
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reading the many contributions in the mailing list in the last days, I
state, that the insight im my two phase algorithm solving the cube
ranges from misunderstood to partly understood, so I will add some more
really detailed explanation here.
The memory requirements for the search algorithm are of the order
O(d*log b), where b is the branching factor and d is the solution depth,
so it definitely is not breadth-first search with O(b^d) nor is it
bidirectional search with O(b^d/2).
The "log b" is no misprint, it is due to the special situation when
dealing rotational puzzles.
The orientations of the corners, the edges and the position of the four
middleslice edges are mapped to {0,1,...,3^7-1},{0,1,...,2^11-1} and
{0,1,...,12*11*10*9/4! -1} by appropriate functions in phase1.
Every state of the cube is represented by a triple (x,y,z) in stage1,
and a face turn maps this triple to another triple (x',y',z').
Let us denote (x0,y0,z0) for the triple, when arriving in the subgroup
____. All elements of this subgroup have this same triple
(x0,y0,z0), because neither edge nor corner orientations can be changed
here and the four middleslice edges stay in their position too (only
their permutation changes, but the mapping function for z ignores the
permutation).
Before applying the search algorithm we use the inverses of the mapping
functions to create lookup-tables for each coordinate, so that a face
turn can be performed with three table lookups, which is very effective.
The three heuristic functions in phase1 also are table-based. From a
pair (x,y) we compute the index i=3^7*y + x which will be a unique
number out of {0,1,...,3^7*2^11-1}. At tableposition i we store the
minimum number of moves we need to get from (x,y) to (x0,y0), ignoring
the z coordinate. Of course this minimum number never is greater than
the number of moves to go from (x,y,z) to (x0,y0,z0), so it is accurate
for the use in an IDA* type search. The other two tables for (x,z) and
(y,z) are constructed in a corresponding way.
Because these minimum-number never exceed 9 in phase 1, 4 bits will do
per tableentry.
Now I *try* to describe the search algorithm for phase1. The
implementation in my program has slight modifications, but they would
not improve the readability of the description. For example I omit the
part how to reduce the branching factor forbidding the move sequences
RR2 or UDU etc.
During the search algorithm, we only store the current state (x,y,z).
Instead of storing the node path we store the applied move sequence,
which is equivalent but more adopted for our problem. We use 1 Byte for
every move. Let denote the list for the move sequence with A, A[i] then
is the i's element of the list. The sequence is stored in reverse order,
A[0] holds the last move of the solving sequence when a solution is
found. The iteration depth is denoted with L1.
1. On initialization set L1=1, i=0, A[0]=0.
2. Apply a face turn to (x,y,z) using the generated lookup tables, the
face turn according to the number A[i]: If A[i]==0, apply U. When we
write 0:U for that the following table shows what faceturn(s) to apply:
O:U, 1:U, 2:U, 3:UR, 4:R, 5:R, 6:RF, 7:F, 8:F, 9:FD, 10:D, 11:D, 12:DL,
13:L, 14:L, 15:LB, 16:B, 17:B, 18:B.
In the case A[i]=18 all branches had been handled and this last B move
resets the cube to the state of the node where it came from at the
current depth -1. We reset A[i] to 0, increment i and goto 3. then.
If A[i]<18 increment A[i].Then compute the indices for the heuristic
tables using the triple (x,y,z) and check, if the current depth (which
is L1-i) plus the tablevalue v (which is a heuristic for the minimum
length to solve the cube from this state) exceeds L1, which is
equivalent to v>i. If that happens for any of the three tables, we prune
that branch and goto 2., to generate the next node of the same depth.
If v<=i, we first check, if i=0. In this case the current depth is the
iteration depth L1 and we have found a solution for phase1, because v=0
only can happen for all three heuristic tables, when we are in state
(x0,y0,z0). Goto phase2 then.
But if i>0, we have to generate the node at the current length + 1. We
decrement i and goto 2.
3. If i==L1 now, we have searched the complete tree with lenght L1. In
this case we increment L1, set A[i]=0 and goto 2. to build again our
first depth-one node.
If i
X-Sender: davidb@dot.mcis.washington.edu
Reply-To: davidbarr@iname.com
To: cube-lovers@ai.mit.edu
Subject: Re: 5x5x5 practical Q's
In-Reply-To: <3.0.32.19970601235733.0068d4f0@pop.radix.net>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
On Sun, 1 Jun 1997, Hersch Pilloff wrote:
> Hello,
>
> I'm proud to say that after significant quantities of blood, sweat, and
> tears, I have finally solved the 5x5x5 cube. I used some techniques from
> the good old 3x3x3 cube as well as some general techniques I've found
> useful over the past (often of the form A R A' R' where A is a set of
> rotations preserving one face and R is a rotation of that face). One
> problem I faced along the way and have not been able to solve to my
> satisfaction is an issue of parity. I often put the big cube in a state
> where exactly two "equivalent" off-center edge pieces on the upper face
> were interchanged with one another. They had the correct orientation, I
> simply needed to switch the two pieces. I would like to know if anyone has
> an effective means of dealing with this situation.
Take a look at some of the web pages about the 4x4x4 or 5x5x5 cubes;
they have a sequence of about 20 moves for swapping two edge pieces.
I used to have it memorized.
Here's what I would do now (when I don't have the sequence memorized).
Turn either the 4th or 2nd horizontal slice one quarter turn, then use
your normal moves to put this slice's edge pieces back into place.
You will end up with a solvable number of pieces out of place on the
top.
I don't understand what ARA'R' means. When I solve the 5x5x5 cube, I
end up using mostly one type of sequence that moves three pieces. I'm
not very familiar with 5x5x5 notation, so I'll describe a notation
that can describe the sequence. I learned this notation from a book
on the 4x4x4 that I bought in the early 80s.
A number (1-5) refers to a slice move that causes a vertical column of
pieces on the front face to move to the bottom face. 1'-5' are the
inverses. L or R refers to a move that will move the bottom row of
pieces on the front face to either the left or right side. Here's a
sequence that moves three corner pieces:
1 L 5 R 1' L 5' R
The shorthand for this move is 1L5, because the rest of the moves can
be predicted from the first three moves. If you replace 1 and 5 with
any two other columns (and possible swap the L and R moves), you can
design a sequence that will move 3 pieces of any type.
1L5 and 5R1 will move three corner pieces.
1L3 and 5R3 will move three edge pieces.
1L2, 1L4, 5R2 and 5R4 will move three off-center edge pieces.
2L3 and 4R3 will move three center near-edge pieces.
2L4 and 4R2 will move three center near-corner pieces.
A lot of the time, the three pieces you want to move aren't in
locations that correspond to one of these sequences. In that case,
make a move that puts the three pieces in the right place for one of
the sequences, do the sequence, then undo your original move.
For all I know, this is just another way of describing the moves that
you are making.
David
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 17:30:49 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04135; Mon, 2 Jun 1997 17:30:48 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Sender: Haym Hirsh
Date: Mon, 2 Jun 97 16:13:55 EDT
From: Haym Hirsh
Reply-To: Haym Hirsh
To: Jerry Bryan
Cc: cube-lovers@ai.mit.edu
Subject: Re: A* versus IDA*
In-Reply-To: Your message of Mon, 02 Jun 1997 09:50:34 -0400 (Eastern
Daylight Time)
Message-ID:
> Like everybody else, I am still trying to grasp IDA*. The way it
> backtracks reminds me a little bit of alpha-beta pruning. There are
> major differences, of course, because alpha-beta works with two person
> games such as chess. But the pruning idea seems very similar anyway.
Actually, in many respects IDA* and alpha-beta pruning are opposites.
Alpha-beta pruning is a way to avoid exploring possible moves in
game-tree search that are guaranteed to have no influence on what the
final move will be. It lessens the work that traditional minimax
search would have to do by eliminating from consideration some of the
possibilities it would ordinarily consider. Alpha-beta results in a
smaller search tree than minimax would ordinarily have.
In contrast, IDA* =adds= additional work that, in theory, would not
be necessary if the search was done optimally. It basically keeps
A*'s search tree, but searches parts of it multiple times. Although
this seems wrong-headed, it winds up being a win because, although it
does some redundant work, the search method has much more realistic
space requirements.
Alpha-beta is a search-space-reduction method for the minimax search
procedure. IDA* is a search-space-maintaining method that replaces
A*'s search of this space with a new search algorithm that explores
some of A*'s possibilities multiple times, but at a tremendous savings
of internal "bookkeeping" memory requirements.
Finally, there is another analogy between alpha-beta and IDA* that is
potentially misleading: both use evaluation functions to evaluate the
merit of a given state (e.g., cube or board position), and, moreover,
the more accurate the evaluation function, the better the performance
of the search method. However, in the case of alpha-beta, you expect
a better evaluation function to yield better moves, i.e., it changes
the output of the search method, returning something that looks
better. (Indeed, this seems to be a major reason for Deep Thought's
success in its recent match against Kasparov.) In contrast, as long
as the evaluation function given to A* or IDA* never overestimates the
cost of solving a given state (i.e., number of moves to solving a
given cube), they are guaranteed to return an optimal solution. Here
the improved performance refers to run-time -- a better evaluation
function typically means A* or IDA* will explore fewer states on its
way to finding an optimal solution. In the case of A* this means it
reduces its run-time from very very unreasonable to very unreasonable,
whereas for IDA*, in at least this problem, it reduces it from
unreasonable to feasible.
At the risk of having him bombarded with lots of email requests, I
strongly encourage those who are interested in understanding this
further to take up Professor Korf's offer of his survey of search
methods in AI. He is an excellent writer and has made many major
contributions to this area. Alternatively, most introductory
textbooks on artificial intelligence cover search methods in a fairly
early chapter (although not all cover IDA* in adequate depth).
However, both options will probably assume some familiarity with basic
concepts in computer science, so may not be accessible to all.
Haym
---------------------------------------------------------------------------
Haym Hirsh office: Busch Campus, CoRE 317
Associate Professor email: hirsh@cs.rutgers.edu
Department of Computer Science phone: +1 732-445-4176
Rutgers University fax: +1 732-445-0537
New Brunswick, NJ 08903 http://www.cs.rutgers.edu/~hirsh
---------------------------------------------------------------------------
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 17:31:24 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04139; Mon, 2 Jun 1997 17:31:23 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199706022035.VAA05665@mail.iol.ie>
From: Goyra
To: cube-lovers@ai.mit.edu
Subject: Re: 5x5x5 practical Q's
Date: Mon, 2 Jun 1997 21:30:19 +0100
X-MSMail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1161
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
> From: Hersch Pilloff
> I'm proud to say that after significant quantities of blood, sweat, and
> tears, I have finally solved the 5x5x5 cube. I used some techniques from
> the good old 3x3x3 cube
Congratulations! I remember going through this about 8
years ago, when I got my 5X5. My approach for the 3X3 was to
solve the corners, then the middle edges; so those techniques carried
over without a change. The rest was simpler, as far as I recall. Trouble
was, even knowing the finished procedure, it took about an hour each
time.
David
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 22:09:15 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA04767; Mon, 2 Jun 1997 22:09:14 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 97 20:48:28 EDT
Message-Id: <9706030048.AA22542@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: cube-lovers@ai.mit.edu
Subject: Memory-Performance tradeoffs in (Korf 1997)
This is the third part of my series on Rich Korf's paper. It covers
what I think is the most interesting part of the research, but
(intentionally) also the least rigorous. Rich makes an attempt to
estimate how many positions will be examined by IDA* as a function of
the memory used by the heuristic. I have to admit I may have missed
something here, but this is my take at understanding, explaining, and
a few queries about the result.
I plan at least one other message to clarify some of the points in the
previous parts. But right now I will note the most glaring error,
which is that heuristic functions are actually guaranteed NOT TO
OVERESTIMATE the true distance to of a solution. Thanks to Clive
Dawson for letting me know I said exactly the opposite. Urk!
DEFINITIONS
Search will be undertaken on a problems in G, with |G|=N. For x in G,
Depth(x) is the length of the shortest process to solve x.
A heuristic is a function h on G satisfying h(x) <= Depth(x) for every
position x in G. The special heuristic h0(x)=0 is the "trivial
heuristic".
Work(h,Depth(x)) is roughly the total number of nodes visited in
searching for x using IDA* with heuristic h. Roughly, because we
average over all the positions at that depth.
The average number of operators/generators applicable to a position is
called the branching factor b. This is a constant over the positions
we will consider, and in the following I will write logb(x) for the
logarithm to the base b.
For most heuristics h, we partition the space G into a certain number
of parts, such that h(x) is a constant over each part; we write
Part(h,x) for the part containing x and extend h to the parts by
writing h(Part(h,x))=h(x). We can use any partition to define such a
heuristic h by defining
h(Part(h,SOLVED))=0, and for x not in Part(h,SOLVED),
h(x)=1 + max over all y in Part(h,x),
min over all neighbors z of y,
h(z).
The number of parts of a partition defining h is called Size(h). We
make a table of size Size(h) once containing the heuristic values of
the parts, and look up h(x)=h(Part(h,x)) over the course of the
search.
If each primitive operator maps parts to parts, then the "max" in the
definition of h(x) is over only one value. This occurs, for instance
if "primitive"="group generator" and Part(h,x)="Coset of a subgroup
with respect to x". Size(h) is then the order of the subgroup.
ESTIMATES
These are the rough estimates that Rich uses (as I understand them).
Most of these exponential-growth spaces have one depth
Mode(Depth) = Mode({Depth(x) : x in G})
at which most of the nodes appear, and almost all of the nodes appear
very close to that depth (so the answer doesn't change much if we take
Mean or Median instead of Mode. Rich uses Mean). If the branching
factor stays nearly constant to the end, we should find that
Mode(Depth) ~ logb(N). (#1)
When heuristics are defined on parts, and the branching factor
of the partition space is the same as the branching factor of the
whole space,
Mode(h) ~ logb(Size(h)) (#2)
since there are Size(h) partitions.
If we examine all positions up to depth d, there are about b^d of
them, so
Work(h0,d) ~ b^d. (#3)
Finally, we might hope that in searching with a consistently
underestimating heuristic, we might be doing something like examining
all the positions up to the amount of underestimation, followed by a
non-branching search to the end:
Work(h,d) ~ Work(h0,d-Mode(h)). (#4)
THE RESULT
Using these estimates we can calculate
Mode(Work(h,Depth(x))) ~ Work(h,logb(N)) by #1
~ Work(h0,logb(N)-Mode(h)) by #4
~ Work(h0,logb(N)-logb(Size(h))) by #2
~ b^(logb(N)-logb(Size(h))) by #3
= N / Size(h).
This is the really fundamental result of Rich's paper.
ERRORS
There are some ways in which this model is known to be flawed. Rich
notes that actually
#4 Work(h,d) > Work(h0,d-Mode(h)),
by over two orders of magnitude. He conjectures that a "locality of
understimation" effect causes most of the search to be concentrated in
the parts of the space for which h is worst.
He hopes this will be balanced out by
#2 Mode(h) > logb(Size(h))
because the branching is not perfect. This effect is stronger on the
branching on the parts of h than on G, because there are fewer of the
former. He finds that under the effects of these two errors, the
answer is off by a factor of 1.4 for his experiments.
I am wondering about a few other effects. For one thing, I am not at
all sure how well the heuristics model the exponential behavior of the
search space, with a strongly defined mode. I think that if
Mode!=Mean, you find the entire argument falls apart (but I may be
missing something). I would like to know something more like the
curve for the heuristics, rather than just the mean.
Second, Rich is combining heuristics based on partition search to form
a different kind of heuristic. Say we form h=max(h1,h2), where h1 and
h2 have about the same size. Estimate #2 would say
Mode(h) = logb(Size(h))
= logb(2 Size(h1))
= Mode(h1) + logb(2).
But I think the strongly modal behavior of these heuristics may not
allow the mode to be increased this easily. We might find that
Mode(h)=Mode(h1), but with a more pronounced peak.
My third quibble is on whether the branching factor b is the same for
the coset spaces as for the whole space G. I'm concerned that some
generators might lie in the subgroup used to form a heuristic, so they
would map a coset to itself, lowering the effective branching factor
for heuristics. But I'm not sure about this--mapping how close this
estimate holds is a ripe direction for research.
Dan
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 22:09:29 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA04771; Mon, 2 Jun 1997 22:09:29 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id:
In-Reply-To: <199706022035.VAA05665@mail.iol.ie>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Mon, 2 Jun 1997 18:37:48 -0400
To: cube-lovers@ai.mit.edu
From: Nichael Lynn Cramer
Subject: Re: 5x5x5 practical Q's
At 9:30 PM +0100 6/2/97, Goyra wrote:
>> From: Hersch Pilloff
>> I'm proud to say that after significant quantities of blood, sweat, and
>> tears, I have finally solved the 5x5x5 cube. I used some techniques from
>> the good old 3x3x3 cube
> Congratulations! I remember going through this about 8
>years ago, when I got my 5X5. My approach for the 3X3 was to
>solve the corners, then the middle edges; so those techniques carried
>over without a change. The rest was simpler, as far as I recall. Trouble
>was, even knowing the finished procedure, it took about an hour each
>time.
Ditto congrats.
As far as solving, I find it useful (from a "finger-exercise" point of
view) to give myself "stunt" solutions to work towards. For instance with
the 5X, I like to start with a single center face (say, blue). Then I
solve the remaining "ring" of inner blue faces in order. Then the ring of
blue edge and corner pieces (again, in circluar order). Then each
successively higher "horizontal" slice (again, in order around the cube)...
and so on until the cube is finished.
Needless to say, some backup is occassionally necessary. But this can be
a pleasant way to pass the time.
Nichael
nichael@sover.net "Did I forget, forget to mention Memphis,
http://www.sover.net/~nichael/ Home of Elvis and the ancient Greeks..."
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 22:08:35 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA04759; Mon, 2 Jun 1997 22:08:34 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 97 18:58:59 EDT
Message-Id: <9706022258.AA28762@sun13.aic.nrl.navy.mil>
From: Dan Hoey
To: cube-lovers@ai.mit.edu
Subject: Indexing (was Re: miscellaneous comments)
In-Reply-To: <199706021710.KAA21887@denali.cs.ucla.edu>
Rich Korf wrote:
> Here's the indexing problem. Write out all the permutations of
> say 4 elements, 24 in all, in lexicographic, or any other,
> order. Now number the permutations from 0 to 23. The problem then
> is given a permutation of N elements, compute its sequential number
> in your ordering scheme. The obvious algorithms do this in roughly
> N^2 time, but it would be nice to able to do it faster.
I thought everyone knew this, but it seems not. The procedure is
this: Make a fresh copy of P and its inverse Pinv, represented as
arrays on [0..N-1]. For k from N-1 down to 1, do
i = Pinv[k];
Pinv[P[k]] = i;
P[i] = P[k].
The loop invariant is that P[0..k] is a permutation on [0..k] and
Pinv[0..k] is its inverse.
Conceptually, you are exchanging P[k-1] with P[Pinv[k-1]] to turn P
into the identity permutation. But instead, you leave stuff in the
part of the P and Pinv arrays that you don't need to use because you
decrement k. That stuff you leave records what exchanges you (would
have) made, so it encodes the index in a variable base: 0<=P[k]<=k and
you take the sum (P[k] k!) to get the index. The permutation parity
is |{k : P[k]==k}| mod 2.
This requires O(N) operations on integers of size O(N log N), so the
time is O(N^2 log N). But if we don't charge extra for the integer
size, it's an O(N) algorithm. If you're using the index to lookup
something in a table that exceeds the integer size you usually need to
split the index into integer-sized subindices anyway (one tells you
which byte in the file, another tells you which file on the disk,
another tells you which disk...).
Oh, and you can run the algorithm in reverse to convert the
variable-base index back into a permutation. (This part doesn't need
Pinv). If you fill the P[k] with Random[0..k] and do this, you get a
fair shuffle. (I wish programs would randomize their cubes this way.
Somehow I never trust the 100 random turns.)
I think the only reason people don't think of this balking at the
initial overhead of making a copy of P and calculating its inverse.
But then we go and spend quadratic time searching for the bits and
pieces we need.
Dan
[ Still working on part 3...]
From cube-lovers-errors@oolong.camellia.org Mon Jun 2 22:08:57 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA04763; Mon, 2 Jun 1997 22:08:57 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 1997 16:14:47 -0700
From: Richard E Korf
Message-Id: <199706022314.QAA22320@denali.cs.ucla.edu>
To: jbryan@pstcc.cc.tn.us
CC: cube-lovers@ai.mit.edu
In-reply-to: (message from Jerry Bryan on Mon, 02 Jun 1997 09:50:34 -0400 (Eastern Daylight Time))
Subject: Re: A* versus IDA*
Dear Jerry and fellow Cube-Lovers,
Unfortunately, the analysis of IDA* and A* is much harder than the
corresponding analysis of alpha-beta minimax, and is still an open research
problem. The reason is that the running time of IDA* or A* depends on the
accuracy of the heuristic function. If we use zero for the heuristic everywhere,
which is still a lower bound, these algorithms degenerate into brute-force
searches, which take b^d time, where b is the branching factor and d is the
optimal solution length. On the other hand, if our heuristic function is
perfect, and always gives us the exact number of moves needed to solve a state,
then these algorithms run in time proportional to d, the length of the optimal
solution. This would be practically instantaneous in this case.
My experience with my program is that the ratio of the number of nodes
generated in searching from one level to the next is approximately the same as
brute-force branching factor of about 13.35. The effect of the heuristic tables
is to start this geometric progression at 8 or 9 instead of 0. This is greatly
oversimplified, but conveys the gist of what I've been able to observe.
-rich
-rich
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 01:54:34 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id BAA05361; Tue, 3 Jun 1997 01:54:33 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 97 22:20:26 EDT
Message-Id: <9706030220.AA22877@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: cube-lovers@ai.mit.edu
Subject: Re: Searching and Metrics in (Korf 1997)
My earlier remarks on searching, outside of saying "underestimate" for
"overestimate", are pretty much redundant given the availability of
Rich's survey article. Here are some remarks on what I said about the
quarter-turn metric.
I said "No one who is familiar with the cube-lovers archives (e.g. my
message of 9 January 1981) would generate both [ FF and F'F' ] any
more than they would generate [ both FB and BF]". This is both too
strong and too weak a statement.
First, there are search techniques that are unable to determine what
the last move was, so they must go ahead and generate such moves
(hopefully discarding them later). I should have replaced "any more
than they would" with "if they could avoid" or something.
But second, I seem to have given the impression this is "a cube thing"
rather than "a search thing". But counting unit turns instead of
multiple turns is easily generalized, moreso than the problem of
commutativity.
Suppose you have generators g1, g2, g3, ..., gk of a group, so that
their inverses g1', ..., gk' are also generators. The order of a
generator g, o(g), is the minimum positive integer for which g^o(g) is
the identity. (I try to avoid using the asymptotic little-o when I'm
talking about this.)
What is the appropriate rule for the set of possible next generators?
The generalization of the face-turn metric is the "power-turn" metric.
We count gi, gi^2, gi^3, ..., gi^(o(gi)-1) as generators. Then after
each gi^k we refuse to allow the next move to involve gi. We deal
with commutativity by also refusing to allow the next move to involve
gj if j__*3. We still assume gi' is the same cost as
gi, so if o(gi)=3 we have gi^2=gi'. For each gi, let the half-order
h(gi)=Floor((o(gi)-1)/2). The state variable assumes 2 h(gi) values
1,2,...,h(gi) and -1,-2,...,-h(gi). If the previous state did not
involve gi, then gi enters state 1 and gi' enters state -1.
Thereafter, positive states can accept gi and increment, and negative
states can accept gi' and decrement, to the maximum of their range.
There is one more case: if o(gi) is even, then state h(gi) can accept
one more gi and go to state -h(gi). Otherwise gi and gi' are
prohibited. This prevents backtracking (gi gi' or gi' gi),
overturning (gi^x or gi'^x where 2x>o(gi)) and halfway-duplication
(gi'^(o(gi)/2)). So the total number of states is
2(h(g1)+h(g2)+...+h(gK)). Commutative duplication is prevented by the
same prohibition as for the power-turn metric.
So for the unit-turn cube metric, we need 12 states (two per face).
The megaminx requires 48 states (12 per face) because the generators
have order 5.
This completely solves the problem about there being more duplication
in the unit-turn metric than the power-turn metric. But the problem
of commuting generators is more complicated, as I remarked with
respect to the Megaminx on 23 September 1982. We can find commuting
pairs {A,B} and {B,C} such that {A,C} do not commute. Remember that
when we are ordering generators, we require that commuting generators
appear in order. But suppose A***
Date: Sun, 01 Jun 1997 10:35:40 -0400
From: "Richard W. Pearson, Jr."
Reply-To: rwpearso@ipass.net
X-Mailer: Mozilla 3.0Gold (Win95; I)
MIME-Version: 1.0
To: Tiffp1@aol.com
CC: cube-lovers@ai.mit.edu
Subject: Re: The rest of us
References: <970531091548_-1732449048@emout01.mail.aol.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Tiffp1@aol.com wrote:
>
> DOES ANYONE KNOW ANY STORES NEAR HENDERSON,DURHAM,OR RALEIGH WHERE I CAN BUY
> A RUBIK'S CUBE AND A RUBIK' S TRIAMID
I've seen them in quite a few toy stores and children's educational
stores. Offhand, I can think of Zany Brainy in Pleasant Valley Shopping
Center in Raleigh.
Ricky Pearson
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 01:55:07 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id BAA05372; Tue, 3 Jun 1997 01:55:06 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
To: cube-lovers@ai.mit.edu
Message-ID: <19970602.222516.3174.1.shaggy34@juno.com>
X-Mailer: Juno 1.15
X-Juno-Line-Breaks: 1-3
From: Josh D Weaver
Date: Mon, 02 Jun 1997 23:26:10 EDT
How do you solve the cube? I solve it by layers. How are some other
ways to solve it? And what does "**__" this mean?
Josh
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 14:53:11 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id OAA01662; Tue, 3 Jun 1997 14:53:11 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199706031102.HAA18257@life.ai.mit.edu>
From: Pete Beck
To: cube-lovers@ai.mit.edu
Subject: orbix
Date: Tue, 3 Jun 1997 06:53:21 -0400
X-Msmail-Priority: Normal
X-Priority: 3
X-Mailer: Microsoft Internet Mail 4.70.1155
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
If anybody is looking for an ORBIX I saw them last night at my local
Kay Bee (rockaway townsquare mall, NJ) reduced from $25 to $10.
Pete
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 14:53:33 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id OAA01666; Tue, 3 Jun 1997 14:53:33 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
X-Sender: ad@talisker
Message-Id:
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 3 Jun 1997 16:52:46 +0100
To: cube-lovers@ai.mit.edu
From: Tony Davie
Subject: FreeCell
Could someone describe the FreeCell puzzle for us non-windows people?
_____
/ /\
Tony Davie Computer Science / / \
Tel: +44 1334 463257 St.Andrews University / / \
Fax: +44 1334 463278 North Haugh / / /\ \
ad@dcs.st-and.ac.uk St.Andrews / / / \ \
Scotland / / /\ \ \
KY16 9SS / / / \ \ \
/ /__/____\ \ \
/ \ \ \
http://www.dcs.st-and.ac.uk/~ad/Home.html /________________\ \ \
\ \ \
\_____________________\ /
In theory, there is no difference between theory and practice, but
in practice there is a great deal of difference.
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 14:52:20 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id OAA01654; Tue, 3 Jun 1997 14:52:19 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <3393C67E.70F8@ibm.net>
Date: Tue, 03 Jun 1997 00:23:43 -0700
From: Jin "Time Traveler" Kim
Organization: The Fourth Dimension
X-Mailer: Mozilla 3.01Gold (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re:
References: <19970602.222516.3174.1.shaggy34@juno.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Josh D Weaver wrote:
>
> How do you solve the cube? I solve it by layers. How are some other
> ways to solve it? And what does "____" this mean?
>
> Josh
Corners first, middle edges interconnecting edges, and finally centers.
____ that is read as Up turn, Down turn, Left turn twice,
Front turn twice, Back turn twice. It's standard notation referring to
the faces of a cube, assuming you're using one face as a reference
point. The notation typically uses 90 degree clockwise turns.
--
Jin "Time Traveler" Kim
chrono@ibm.net
VGL Costa Mesa
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 14:52:43 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id OAA01658; Tue, 3 Jun 1997 14:52:42 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199706031013.GAA17406@life.ai.mit.edu>
Date: Tue, 03 Jun 1997 06:13:22 EDT
From: Richard M Morton RMM - ICOMSOLS
To: cube-lovers@ai.mit.edu
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Subject: Number of States for 2x2x2 cube
-------------------------------------------------------------------------------
Reading about the number of possible states (88million) for the corners
of the 3x3x3 cube (equiv. to 2x2x2) made me try working this out for
myself. My logic was :
Cube has 8 corners, each of which can have 3 orientations. Number of
possible states is
(8*3)*(7*3)*(6*3)*(5*3)*(4*3)*(3*3)*(2*3)*(1*3) = 8!*3**8 = 264,539,520
This figure of course includes some states only possible by disassembling
the cube (or maybe by twisting it in a fourth dimension ?). Without this
the last corner can only have one orientation so the number of states
achievable by twisting only in 3d is 8!*3**7 = 88179840
I assume that this is the correct figure but what I would like to know is
whether my logic is correct ie is the assumption about the last corner
being fixed in orientation the only requirement (I am not a mathematician
so please excuse me if this is obvious).
Richard Morton "I'm Brian and so's my wife"
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 22:32:12 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA02617; Tue, 3 Jun 1997 22:32:11 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 3 Jun 1997 12:57:16 -0700 (PDT)
From: Don Woods
Message-Id: <199706031957.MAA14492@madrigal.clari.net>
To: cube-lovers@ai.mit.edu
Subject: Re: FreeCell
Cc: ad@dcs.st-and.ac.uk
> Could someone describe the FreeCell puzzle for us non-windows people?
This is perhaps getting a bit off-topic for cube-lovers, since FreeCell
is a card game, but it can also be thought of as a puzzle in which you
are to unscramble a randomised bunch of cards, so maybe it's not so far
off-topic at that. Anyway, since you asked:
Shuffle a standard 52-card deck and deal them out to form 8 columns of
cards; 4 columns of 7 and 4 columns of 6. All the cards are face up,
and you should spread the columns (while keeping the cards overlapping
within each column) so you can see all the cards.
Above the columns are 8 initially-empty spaces. 4 of these are reserved
for collecting the 4 suits in order: the object of the game is to move
Ace-deuce-3-4-...-queen-king of each suit onto these spaces. The other 4
are "free cells": each free cell can be used to hold any SINGLE card.
You move only one card at a time. The only cards you can move are the
last card of a column (i.e., cards that don't have other cards on top
of them) or a card in a free cell. A card can move to (1) an empty free
cell, (2) an empty column (i.e., a column where you've moved out all of
the cards), or (3) a column whose last card is the opposite color and
one rank higher than the card being moved (i.e., you can place a red 6
on a black 7, etc.). A card can also be moved to the suit-collecting
piles if it's the next card needed in that suit, i.e., an Ace to empty
suit spot, a deuce onto the Ace of the same suit, etc.
The Windows version of the game lets you specify a number and then
generates a deck based on that number, so you can get the same initial
layout by giving the same number again. Thus it offers only a small
fraction of the possible layouts. I wasn't part of the effort that
solved the Windows layouts, but I did write a program to solve FreeCell
layouts and fed it a million random layouts, and it solved all but 14.
So I don't find it surprising that all but 1 of the 32000 Windows
layouts is solvable.
There are several other puzzle-type solitaire card games with a similar
theme. E.g., Seahaven Towers uses 10 columns instead of 8, and two of
the free cells start with cards in them (each column has 5 cards). In
Seahaven Towers, moves onto a column must be matching suit instead of
opposite color, i.e., 6 of clubs onto 7 of clubs. Also, only a King
can be moved into an empty column. Thus the moves in Seahaven Towers
are much more restricted; my program for that game runs a lot faster.
About 90% of Seahaven Towers layouts can be solved.
-- Don.
-------------------------------------------------------------------------------
--
-- Don Woods (don@clari.net) ClariNet provides on-line news.
-- http://www.clari.net/~don I provide personal opinions.
--
From cube-lovers-errors@oolong.camellia.org Tue Jun 3 22:32:23 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA02621; Tue, 3 Jun 1997 22:32:22 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 3 Jun 97 21:06:35 EDT
Message-Id: <9706040106.AA26157@sun34.aic.nrl.navy.mil>
From: Dan Hoey
To: Herbert Kociemba ,
cube-lovers@ai.mit.edu
Subject: Re: Detailed explanation of two phase algorithm
Herbert,
Thank you very much for the description of your algorithm. This fills
many of the gaps that have been left by the fragmentary discussions on
cube-lovers over the years. Though perhaps it's all my fault--I would
not have felt so left out if I had taken the effort to subscribe to
CFF.
> The memory requirements for the search algorithm are of the order
> O(d*log b), where b is the branching factor and d is the solution
> depth, so it definitely is not breadth-first search with O(b^d) nor
> is it bidirectional search with O(b^d/2).
I like the extremely compact stack size. It might make it possible to
take advantage of very large (disk-based) heuristic tables. The idea
is that if you can collect enough positions at once, you can sort them
and look up all the heuristics in one pass through the table, so you
get sequential access instead of random access. The usual problem
with this is you need massive parallelism--or simulate it with massive
multiprogramming. I'm hoping the tiny stack size makes
multiprogramming cheap enough.
I hope this is not doing too much violence to your idea, which is
remarkably parsimonious of memory usage. I guess I'm looking for ways
that increased memory could make it faster.
I would be careful in classifying search algorithms by memory size,
though. With Shamir's modification of bidirectional search, for
instance, you can get much less than O(b^(d/2)) memory use. Still
nothing like the very low usage of your idea, though.
> The "log b" is no misprint, it is due to the special situation when
> dealing rotational puzzles.
Well, not only rotational puzzles--any grouplike puzzle could achieve
this--any puzzle where you can undo your moves. For instance, on a
fifteen puzzle, you could use an encoding like
0: R 1:LD 2:TL 3:RT 4:D
to explore the four possiblities for the direction to move the blank
square at any node. So knowing the position of the puzzle and the
current index would tell you how to modify the position for the next
index.
> ...If you analyze the preceeding phase1 algorithm you will see that
> it is indeed just an IDA* with lowerbound heuristic functions based
> on tables.
It sure is. Now here's a question. Should it be combined with phase2
in such a way that the entire search is IDA*?
The way I would see this happening is that whenever you get to phase 2
(at depth i with a cutoff of L1), instead of allowing the phase2
search to iteratitively deepen, you run a depth-first A* search with a
fixed depth cutoff of L1-i. It would take longer to get the first
answer, but when you got an answer it would be optimal, and you would
never spend time searching longer processes. I'm just hoping this
might find optimal solutions faster. Possibly it could be combined
with global heuristics like Rich used.
One final thing, which I'm not sure ever got asked, much less
answered, is that Mike Reid did an exhaustive search of the subgroup
(7 Jan 1995). Did this verify that the optimal
face-turn process for each element of the subgroup is a word on those
generators? Or are there shortcuts that use forbidden quarter-turns?
Dan
From cube-lovers-errors@oolong.camellia.org Wed Jun 4 01:26:56 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id BAA02995; Wed, 4 Jun 1997 01:26:55 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Tue, 03 Jun 1997 23:57:22 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Number of States for 2x2x2 cube
In-reply-to: <199706031013.GAA17406@life.ai.mit.edu>
To: Richard M Morton RMM - ICOMSOLS
Cc: cube-lovers@ai.mit.edu
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Tue, 3 Jun 1997, Richard M Morton RMM - ICOMSOLS wrote:
>
> Reading about the number of possible states (88million) for the corners
> of the 3x3x3 cube (equiv. to 2x2x2) made me try working this out for
> myself. My logic was :
Actually, the corners of the 3x3x3 are not usually considered to be
equivalent to the 2x2x2. There are 24 times fewer states in the 2x2x2
because any of the 24 rotations in space of the 2x2x2 are considered to be
equivalent. Another way (and the typical computer way) to model this
effect is to fix one of the corners of the 2x2x2.
>
> Cube has 8 corners, each of which can have 3 orientations. Number of
> possible states is
>
> (8*3)*(7*3)*(6*3)*(5*3)*(4*3)*(3*3)*(2*3)*(1*3) = 8!*3**8 = 264,539,520
>
> This figure of course includes some states only possible by disassembling
> the cube (or maybe by twisting it in a fourth dimension ?). Without this
> the last corner can only have one orientation so the number of states
> achievable by twisting only in 3d is 8!*3**7 = 88179840
>
> I assume that this is the correct figure but what I would like to know is
> whether my logic is correct ie is the assumption about the last corner
> being fixed in orientation the only requirement (I am not a mathematician
> so please excuse me if this is obvious).
>
Your logic is correct. The larger size of 264,539,520 is the number of
corner configurations in the so-called constructable group. The
constraint on the twist of the last corner cubie gets you down to
88179840, and is the only other constraint on the corners alone. When you
add in the edge cubies, there are two additional constraints -- one for
the edge cubies alone, and one for the corner and edge cubies combined
(they have to have the same parity).
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Wed Jun 4 17:30:05 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04580; Wed, 4 Jun 1997 17:30:05 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Wed, 04 Jun 1997 10:58:27 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Re: FreeCell
In-reply-to:
To: Tony Davie
Cc: cube-lovers@ai.mit.edu
Reply-to: Jerry Bryan
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us
On Tue, 3 Jun 1997, Tony Davie wrote:
> Could someone describe the FreeCell puzzle for us non-windows people?
>
The game has already been described, so I won't do it again. But I will
make a couple of comments.
The Windows version of the game has a certain charm that does not exist
when you play it with real cards. The rules require that you move one
card at a time. In actual practice you often move a group of cards as
if they were a single entity, knowing full well that you could move them
one at a time and still stay within the rules of the game. The Windows
version of the game understands this concept, and will move an entire
group of cards for you with one mouse click. It's almost as if the
program is defining a macro operator for you on the fly. Also, there
are totally obvious moves, such as always playing aces to their payoff
cells without further ado as soon as the aces are uncovered. The
program plays these totally obvious moves for you. At the end of the
game there may be several dozen such obvious moves in a row, and it
makes a nice visual effect that you cannot get with real cards. (By the
way, the program fails to make some moves which are totally obvious (to
me, at least), but any discussion of such things should probably be
taken off line. I am curious if our moderator is going to let through
such an off topic message, anyway.)
But by contrast, my personal experience is that graphics cube
manipulation programs have less charm than the real thing. There is
just something nice about the feel of the thing in your hands, and in
its obvious 3-D solidness.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
From cube-lovers-errors@oolong.camellia.org Wed Jun 4 17:30:26 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04584; Wed, 4 Jun 1997 17:30:25 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <33959796.3784@hrz1.hrz.th-darmstadt.de>
Date: Wed, 04 Jun 1997 18:28:06 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: Dan Hoey , cube-lovers@ai.mit.edu
Subject: Re: Detailed explanation of two phase algorithm
References: <9706040106.AA26157@sun34.aic.nrl.navy.mil>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Dan Hoey wrote:
>
> > ...If you analyze the preceeding phase1 algorithm you will see that
> > it is indeed just an IDA* with lowerbound heuristic functions based
> > on tables.
>
> It sure is. Now here's a question. Should it be combined with phase2
> in such a way that the entire search is IDA*?
>
> The way I would see this happening is that whenever you get to phase 2
> (at depth i with a cutoff of L1), instead of allowing the phase2
> search to iteratitively deepen, you run a depth-first A* search with a
> fixed depth cutoff of L1-i. It would take longer to get the first
> answer, but when you got an answer it would be optimal, and you would
> never spend time searching longer processes.
>
I try to understand but I can't grasp the idea. Maybe I did not describe
clearly enough, how phase1 and phase2 work together.Doing the entire
search in one single IDA* will result inevitably in a program, which
applys IDA* to the whole cube group in my opinion. Rich Korf did this
now. I could not do this (though I would have liked to do) due to a lack
of the appropriate hardware. So I had to apply it to the much smaller
groups G2=____ in phase2 and G1=G/G2 in phase1.
Is the "i" you use above the same "i" I used in my explanation? There we
have i=0 every time we enter phase2. Beyond that I can't see how to
guarantee optimal solutions whith a phase2 at all, because we only allow
R2,L2,F2 and B2 moves there.
Why does the algorithm work so surprisingly well? Let us assume, that
every time we enter phase2 while the algorithm is running, the state is
a random sample of G2. From the archives (7 Jan 95), where Michael Reid
computed the distances of the elements of G2 from SOLVED we compute for
example, that the chance to get a state with distance less than 9 in
phase2 is about 2.6*10^-4. But in phase1 even with a very modest
iteration depth we already produce very very many solutions for G2.
Today I applied my algorithm to Rich Korfs Random Cube Nr.10 with
minimum length 18 for example, and within a minute I had a solution with
20 moves, 12 in phase1 and 8 in phase2. The next solution took about 15
minutes and gave a 19 move solution with 14 in phase1 and 5 in phase2. I
did not try for more than an hour, in this time no 18 move solution
appeared.
> One final thing, which I'm not sure ever got asked, much less
> answered, is that Mike Reid did an exhaustive search of the subgroup
> (7 Jan 1995). Did this verify that the optimal
> face-turn process for each element of the subgroup is a word on those
> generators? Or are there shortcuts that use forbidden quarter-turns?
>
There definitely are shortcuts with quarter turns. I just tried the
first of the antipodes of phase2 Mike Reid gave (7 Jan 1995) with 18
moves. They usually are hard to solve with the algorithm, but because of
the asymmetrie of stage2, conjugation with moves, that turn the whole
cube lead to a much easier to solve state. Within less than a minute a
had the generator B R2 U2 L2 R2 B2 F' . U' R2 U F' D2 R2 B' D F' D'
(17).
It would be interesting, if it is possible to reduce all of the
antipodes of phase2 to 17 moves, which would reduce algorithms upper
bound for the maneuver length.
Herbert
From cube-lovers-errors@oolong.camellia.org Thu Jun 5 00:34:59 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA05255; Thu, 5 Jun 1997 00:34:58 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199706050430.AAA19160@life.ai.mit.edu>
Date: Thu, 5 Jun 1997 00:28:40 -0400
From: michael reid
To: Hoey@aic.nrl.navy.mil, cube-lovers@ai.mit.edu
Subject: correction of priority
dan writes
> Herbert Kociemba notes three interesting heuristics based on the
> number of moves to reach the subgroup . In fact,
> Mike Reid calculated (and Dik Winter verified) the exact distances in
> this 2.2-billion element coset space (see archives at 7 Jan 1995 and
> following).
these distances (in the face turn metric) were originally calculated
by dik winter. see his message of may 28, 1992, "Corrected calculations
are now done." i mentioned this in my message of january 7, 1995.
mike
From cube-lovers-errors@oolong.camellia.org Thu Jun 5 01:18:40 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id BAA05363; Thu, 5 Jun 1997 01:18:40 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199706050457.AAA19765@life.ai.mit.edu>
Date: Thu, 5 Jun 1997 00:55:43 -0400
From: michael reid __