solve the rubik's cube fast!

[williamstein]

Hi:

Two Rubik's cube programs have just been posted to http://sage.math.washington.edu/home/wdj/rubik/ Both one is GPL's (Michael Reid's) and the other is under the MIT license (Dik Winter's). These programs have been around for some time but have never been licensed until recently (and I thank both the authors for kindly replying to my emails and agreeing to an open source license). The tarballs you will find there are identical to the author's version except that I have added a license.txt following their email directions. Now that the semester has started, I lack the time to do anything but am emailing the list in case anyone is interested and has the time to create Python wrappers for one (or both) of them. SAGE currently has a Rubik's cube solver which uses GAP and is quite slow and far from optimal. Maybe one of these could be used instead one day? --- David Joyner

Component: combinatorics

Issue created by migration from https://trac.sagemath.org/ticket/444

[robertwb]

comment:2

Here's an spkg of solvers, needs to be tested on lots of different computers.

http://sage.math.washington.edu/home/robertwb/spkgs/

[robertwb]

Attachment: cube-solver.hg.gz

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:4

Is this in or not? What should we do with this patch?

Cheers,

Michael

[ba94b9bb-195b-4422-a5e2-176920eaa163]

comment:8

I tried the spkg and the associated patch; they worked fine (on 32-bit x86 Linux; Debian testing). However, I don't think the solvers belong as a standard spkg (adding a third of a megabyte to every Sage download); I think they should be optional. And if the spkg is optional, then the patch has some problems: it turns a working-by-default (if slow) method into a method which raises an exception when the spkg is not installed.

I think the patch should be modified to either leave the original GAP algorithm as the default, or to change the default but automatically fall back to GAP if the solvers are not installed.

Also, there should be at least one doctest for each solver.

I'm removing "[with patch]" from the summary for now; anybody who supplies a revised patch should reinstate it (or, I guess, you could reinstate it if you want to argue that the solvers should be a standard Sage package).

[robertwb]

Attachment: rubiks-doctest.patch.gz

[robertwb]

comment:9

In light of David Joyner's re-release of his book on Solving the Rubiks cube (using Sage) I think a fast solver is important to include even if just for marketing purposes. The GAP implementation isn't just a little bit slow, it's almost unusable (especially compared to nearly instantaneous solutions provided by the other packages).

Also I think 370K is really a quite small, 0.2% of the size of Sage itself, compared to the provided functionality.

I did, however, add doctests for the solvers.

[robertwb]

Attachment: cubegroup-cleanup1.patch.gz

[robertwb]

Attachment: cubegroup-cleanup2.patch.gz

[ba94b9bb-195b-4422-a5e2-176920eaa163]

comment:11

OK, assuming the rubik solvers are to become a standard part of Sage, then this patch set looks good to me.

To install: add http://sage.math.washington.edu/home/robertwb/spkgs/rubiks-20070912.spkg as a standard spkg, then apply all 4 attachments to this bug (one bundle, and 3 patches) in order.

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:12

Merged in 2.9.rc0.