The twentyseven package

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain]

Warnings:

Solve 3×3×3 Rubik's cubes in the fewest possible moves. Or, if you can't wait, get close enough with the two-phase solver.


[Skip to ReadMe]

Properties

Versions0.0.0, 0.0.0
Change logNone available
Dependenciesbase (>=4.8 && <5), containers (>=0.5), deepseq, directory, filepath, heap (>=1.0), monad-loops, MonadRandom, mtl (>=2.1), newtype (>=0.2), optparse-applicative, primitive (>=0.6), ref-fd (>=0.4), template-haskell, time (<1.6), transformers, twentyseven, vector (>=0.10) [details]
LicenseMIT
AuthorLi-yao Xia
Maintainerli-yao.xia@ens.fr
CategoryAlgorithms
Home pagehttps://github.com/lysxia/twentyseven
Executablestwentyseven
UploadedWed Mar 16 17:39:50 UTC 2016 by lyxia

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for twentyseven-0.0.0

Twentyseven

Rubik's cube solver in Haskell.

Inspired by Herbert Kociemba's Cube Explorer.

The main idea is to precompute, for every configuration, the number of moves required to put certain subsets of the 27 cubies composing the 3x3 Rubik's cube in their right place and/or in the right orientation. This gives lower bounds used for an A⋆-like search in the graph of scrambled cubes.


By default, a suboptimal "two-phase" solver is used, as it runs rather quickly. It currently solves 1000 random cubes (uniformly distributed) in about one minute. The optimal solver is quite slow however, taking between five minutes and two hours to solve a random cube (18 moves in average).

The solver must precompute a certain number of lookup tables, which can be stored in files. These tables take fifteen seconds to compute and weigh 13MB for the two-phase solver, compare that to about 8 hours and 2GB for the optimal one!

You may check the produced files with the checksums in ts-tables.sha256. A compressed archive ts-tables.zip (723MB) of all precomputed tables is available in the branch fetch-tables via git-lfs. Unzip it in $HOME/.27/, or wherever (see usage below).

Usage summary

twentyseven [-p] [--strict] [-d DIR] [--optimal]

The input is read line by line.

Input format

A line can be one of:

Example

Initialization

$ echo quit|twentyseven -p --strict

Example

examples.txt:

qwqwqwqwq erererere tytytytyt rerererer ytytytyty wqwqwqwqw
qwqwqwqwq erqrerere tytytytyt rerererer ytytytyty wqwqwqwqw
BBBBUBBBB UUUULUUUU RRRRFRRRR DDDDRDDDD LLLLBLLLL FFFFDFFFF
DDDFUDLRB FUFDLLLRR UBLBFDFUD ULBFRULLB RRRLBBRUB UBFFDFDRU
111121111 333313333 222232222 444454444 666646666 555565555
111111214 223222222 131333333 344444444 555555555 666666666
.udddlrrrbfffuddd
random

The output then looks like this:

$ twentyseven < examples.txt
U2 D2 L2 R2 F2 B2
Facelets [6,18,11] ("qtq") do not match any regular cubie.
U D F B L R U2 R2 F2 R2 U2 L2 B2 U' D' B2
U L B' L R2 D R U2 F U2 L2 B2 U B2 D' B2 U' R2 U L2 R2 U
U D L R F B U2 B2 L2 F2 D2 B2 R2 U' D' L2
L U' F2 U F2 U L U' L2 D F2 D' F2
BBBBUBBBB UUUULUUUU RRRRFRRRR DDDDRDDDD LLLLBLLLL FFFFDFFFF
BDLLUFBUD LBUBLURFL RLBFFBFRU RLFURULRR UBDRBRDDU DFBDDDFLF

Detail of current heuristics

The distance estimations are based on cosets corresponding to the following elements.

Two-phase

Phase 1

It is possible to store the actual distances to the goal set in phase 1 but the current speed seems good enough for now.

Phase 2

Optimal