README
¶
gocube
gocube is a pure Go library for solving the 3x3x3 Rubik's cube.
Usage
Some general documentation of the API can be found on the GoDoc
Design considerations
I want this code to be efficient. However, I don't claim to know the best way to solve the cube computationally. Thus, I will make this project as modular as possible so that it can be improved easily (unlike some people's code).
License
gocube is licensed under the BSD 2-clause license. See LICENSE.
Copyright (c) 2015, Alex Nichol.
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Documentation
¶
Index ¶
- Variables
- type CubieCorner
- type CubieCorners
- type CubieCube
- type CubieEdge
- type CubieEdges
- type Move
- type Phase1Cube
- type Phase1Heuristic
- type Phase1Moves
- type Phase1Solution
- type Phase1Solver
- type Phase2Cube
- type Phase2Heuristic
- type Phase2Move
- type Phase2Moves
- type Rotation
- type Solver
- type SolverTables
- type StickerCube
Constants ¶
This section is empty.
Variables ¶
var CornerIndexes = []int{
51, 15, 35,
44, 17, 33,
45, 0, 29,
38, 2, 27,
53, 9, 24,
42, 11, 26,
47, 6, 18,
36, 8, 20,
}
CornerIndexes contains 8 sets of 3 values which corresponds to the x, y, and z sticker indexes for each corner piece.
var CornerPieces = []int{
6, 2, 4,
5, 2, 4,
6, 1, 4,
5, 1, 4,
6, 2, 3,
5, 2, 3,
6, 1, 3,
5, 1, 3,
}
CornerPieces contains 8 sets of 3 values which correspond to the x, y, and z stickers for each corner piece.
var EdgeIndexes = []int{
7, 19,
23, 39,
10, 25,
21, 50,
3, 46,
5, 37,
1, 28,
30, 41,
16, 34,
32, 48,
12, 52,
14, 43,
}
EdgeIndexes contains 12 pairs of values which correspond to the sticker indexes of each edge.
var EdgePieces = []int{
1, 3,
3, 5,
2, 3,
3, 6,
1, 6,
1, 5,
1, 4,
4, 5,
2, 4,
4, 6,
2, 6,
2, 5,
}
EdgePieces contains 12 pairs of values which correspond to the stickers of each edge.
var XRotationPerm = []int{
0, 1, 2, 3, 4, 5, 6, 7, 8,
35, 34, 33, 32, 31, 30, 29, 28, 27,
9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26,
36, 37, 38, 41, 44, 43, 42, 39,
47, 46, 45, 48, 51, 52, 53, 50,
}
XRotationPerm stores sticker indices for the faces involved in an "x" rotation.
The first four sets of 9 stickers are for the four faces which are not normal to the x-axis. Each set of 9 consecutive stickers corresponds to a face, such that the stickers indexed by the first face are moved to the indices of the second face, and those to the third face, etc.
The two normal faces are represented by two 8-perms at the end of the list. These 8-perms are applied twice to permutate the non-center pieces of the normal faces. The sticker at the first index of the 8-perm is moved to the next index, etc.
var YRotationPerm = []int{
18, 19, 20, 21, 22, 23, 24, 25, 26,
45, 46, 47, 48, 49, 50, 51, 52, 53,
27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44,
0, 1, 2, 5, 8, 7, 6, 3,
11, 10, 9, 12, 15, 16, 17, 14,
}
YRotationPerm is like XRotationPerm, but for "y" rotations.
var ZRotationPerm = []int{
51, 48, 45, 52, 49, 46, 53, 50, 47,
0, 1, 2, 3, 4, 5, 6, 7, 8,
38, 41, 44, 37, 40, 43, 36, 39, 42,
17, 16, 15, 14, 13, 12, 11, 10, 9,
18, 19, 20, 23, 26, 25, 24, 21,
29, 28, 27, 30, 33, 34, 35, 32,
}
ZRotationPerm is like XRotationPerm, but for "z" rotations.
Functions ¶
This section is empty.
Types ¶
type CubieCorner ¶
A CubieCorner represents a physical corner of a cube.
To understand the meaning of a CubieCorner's fields, you must first understand the coordinate system. There are there axes, x, y, and z. The x axis is 0 at the L face and 1 at the R face. The y axis is 0 at the D face and 1 at the U face. The z axis is 0 at the B face and 1 at the F face.
A corner piece's index is determined by it's original position on the cube. The index is a binary number of the form ZYX, where Z is the most significant digit. Thus, the BLD corner is 0, the BRU corner is 3, the FRU corner is 7, etc.
The orientation of a corner tells how it is twisted. It is an axis number 0, 1, or 2 for x, y, or z respectively. It indicates the direction normal to the white or yellow sticker (i.e. the sticker that is usually normal to the y axis). The corners of a solved cube all have an orientation of 1.
type CubieCorners ¶
type CubieCorners [8]CubieCorner
CubieCorners represents the corners of a cube.
func RandomLLCorners ¶
func RandomLLCorners() (CubieCorners, bool)
RandomLLCorners generates random last-layer corners and returns the corners as well as their parity.
A parity of true is even, while false is odd.
func SolvedCubieCorners ¶
func SolvedCubieCorners() CubieCorners
SolvedCubieCorners generates the corners of a solved cube.
func (*CubieCorners) HalfTurn ¶
func (c *CubieCorners) HalfTurn(face int)
HalfTurn performs a 180 degree turn on a given face.
func (*CubieCorners) Move ¶
func (c *CubieCorners) Move(m Move)
Move applies a face turn to the corners.
func (*CubieCorners) QuarterTurn ¶
func (c *CubieCorners) QuarterTurn(face, turns int)
QuarterTurn performs a 90 degree turn on a given face.
func (*CubieCorners) Solved ¶
func (c *CubieCorners) Solved() bool
Solved returns true if all the corners are properly positioned and oriented.
type CubieCube ¶
type CubieCube struct {
Corners CubieCorners
Edges CubieEdges
}
A CubieCube represents a cube's physical construction.
func RandomZBLL ¶
func RandomZBLL() CubieCube
RandomZBLL generates a cube with a random last layer in which the edges are all properly oriented.
func (*CubieCube) Phase1Cube ¶
func (c *CubieCube) Phase1Cube() Phase1Cube
Phase1Cube generates a Phase1Cube which reflects the state of a CubieCube.
func (*CubieCube) QuarterTurn ¶
QuarterTurn applies a quarter-turn to the edges and corners.
func (*CubieCube) StickerCube ¶
func (c *CubieCube) StickerCube() StickerCube
StickerCube converts a CubieCube to a StickerCube
type CubieEdge ¶
A CubieEdge represents a physical edge of a cube. Edges are indexed from 0 through 11 in the following order: UF, RF, DF, LF, UL, UR, BU, BR, BD, BL, DL, DR. The flip field is true if the edge is "bad" in the ZZ color scheme (i.e. if it requires an F or B move to fix).
type CubieEdges ¶
type CubieEdges [12]CubieEdge
CubieEdges represents the edges of a cube.
func SolvedCubieEdges ¶
func SolvedCubieEdges() CubieEdges
SolvedCubieEdges returns CubieEdges in their solved state.
func (*CubieEdges) HalfTurn ¶
func (c *CubieEdges) HalfTurn(face int)
HalfTurn performs a 180 degree turn on a given face.
func (*CubieEdges) QuarterTurn ¶
func (c *CubieEdges) QuarterTurn(face, turns int)
QuarterTurn performs a 90 degree turn on a given face.
func (*CubieEdges) Solved ¶
func (c *CubieEdges) Solved() bool
Solved returns true if all the edges are properly positioned and oriented.
type Move ¶
type Move int
A Move represents a face turn.
A move can occur on the faces U, D, F, B, R, and L. These are the first 6 values of the Move type. The next 6 values are U', D', F', B', R', L'. The final six values are U2, D2, F2, B2, R2, L2. Thus, there are a total of 18 possible moves in the range [0, 18).
func NewMove ¶
NewMove creates a new move with a face in the range [1, 6] and a number of turns 1, -1, or 2.
func ParseMoves ¶
ParseMoves parses a space-delimited list of WCA moves.
type Phase1Cube ¶
type Phase1Cube struct {
XCornerOrientation int
YCornerOrientation int
ZCornerOrientation int
FBEdgeOrientation int
UDEdgeOrientation int
MSlicePermutation int
ESlicePermutation int
SSlicePermutation int
}
A Phase1Cube is an efficient way to represent the parts of a cube which matter for the first phase of Kociemba's algorithm. The FB edge orientation can be used for both Y and X phase-1 goals, and the UD edge orientation can be used for the Z phase-1 goal. Thus, no RL edge orientations are needed.
func SolvedPhase1Cube ¶
func SolvedPhase1Cube() Phase1Cube
SolvedPhase1Cube returns a solved phase1 cube.
func (*Phase1Cube) AnySolved ¶
func (p *Phase1Cube) AnySolved() bool
AnySolved returns true if any three return values for Solved() would be true.
func (*Phase1Cube) Move ¶
func (p *Phase1Cube) Move(m Move, moves *Phase1Moves)
Move applies a move to a Phase1Cube.
func (*Phase1Cube) Solved ¶
func (p *Phase1Cube) Solved() (x bool, y bool, z bool)
Solved returns whether the phase-1 cube is solved in all three axes.
func (*Phase1Cube) XEdgeOrientation ¶
func (p *Phase1Cube) XEdgeOrientation() int
XEdgeOrientation returns the FBEdgeOrientation, translated for the X axis cube.
type Phase1Heuristic ¶
type Phase1Heuristic struct {
// This stores the number of moves needed to orient the corners and edges.
COEO [4478976]uint8
// This stores the number of moves needed orient the edges and put the slice
// edges on the slice.
EOSlice [1013760]uint8
}
Phase1Heuristic stores the data needed to effectively prune the search for a solution for phase-1.
func NewPhase1Heuristic ¶
func NewPhase1Heuristic(moves *Phase1Moves) *Phase1Heuristic
NewPhase1Heuristic generates a heuristic for the phase-1 solver.
func (*Phase1Heuristic) LowerBound ¶
func (p *Phase1Heuristic) LowerBound(c *Phase1Cube) int
LowerBound returns the minimum number of moves needed to solve at least one phase-1 axis.
type Phase1Moves ¶
Phase1Moves is a table containing the necessary data to efficiently perform moves on a Phase1Cube. Note that only one move table is needed for all 3 axes (i.e. all three phase-1 goals). Thus, the move tables apply directly to the Y-oriented phase-1 goal. Moves much be translated for the X-oriented and Z-oriented goals.
func NewPhase1Moves ¶
func NewPhase1Moves() *Phase1Moves
NewPhase1Moves generates tables for applying phase-1 moves.
type Phase1Solution ¶
type Phase1Solution struct {
Cube Phase1Cube
Moves []Move
}
A Phase1Solution stores information about a phase-1 solution.
type Phase1Solver ¶
type Phase1Solver struct {
// contains filtered or unexported fields
}
A Phase1Solver finds solutions to a specific phase-1 state.
func NewPhase1Solver ¶
func NewPhase1Solver(c Phase1Cube, h *Phase1Heuristic, m *Phase1Moves) *Phase1Solver
NewPhase1Solver creates and starts a Phase1Solver.
func (*Phase1Solver) Solutions ¶
func (p *Phase1Solver) Solutions() <-chan Phase1Solution
func (*Phase1Solver) Stop ¶
func (p *Phase1Solver) Stop()
type Phase2Cube ¶
type Phase2Cube struct {
// CornerPermutation represents the permutation of the corners.
CornerPermutation int
// EdgePermutation represents the permutation of the 8 top/bottom edges.
EdgePermutation int
// SlicePermutation represents the permutation of the
SlicePermutation int
}
A Phase2Cube represents the parts of a cube that are important for phase-2 solving.
func NewPhase2Cube ¶
func NewPhase2Cube(c CubieCube, axis int) (Phase2Cube, error)
NewPhase2Cube generates a Phase2Cube from a CubieCube. The axis argument is 0 for X axis, 1 for Y axis, or 2 for Z axis. If the cube is not reduced to phase-2 in the given axis, this may return an error, but it does not validate everything.
func SolvedPhase2Cube ¶
func SolvedPhase2Cube() Phase2Cube
SolvedPhase2Cube returns a solved Phase2Cube.
func (*Phase2Cube) Move ¶
func (p *Phase2Cube) Move(move Phase2Move, table *Phase2Moves)
Move applies a move to the Phase2Cube.
func (*Phase2Cube) Solved ¶
func (p *Phase2Cube) Solved() bool
Solved returns true if the Phase2Cube is solved.
type Phase2Heuristic ¶
type Phase2Heuristic struct {
// If an element is -1, it should be assumed to have the value 12.
CornersSlice [967680]int8
// If an element is -1, it should be assumed to have the value 9.
EdgesSlice [967680]int8
}
A Phase2Heuristic estimates a lower bound for the number of moves to solve a Phase2Cube.
func NewPhase2Heuristic ¶
func NewPhase2Heuristic(moves *Phase2Moves, complete bool) *Phase2Heuristic
NewPhase2Heuristic generates a Phase2Heuristic. If complete is true, the full index is found. Otherwise, corners will only be searched up to depth 11, and edges will only be searched up to depth 8.
func (*Phase2Heuristic) LowerBound ¶
func (p *Phase2Heuristic) LowerBound(c *Phase2Cube) int
LowerBound returns the heuristic lower bound for a given Phase2Cube.
type Phase2Move ¶
type Phase2Move int
Phase2Move represents a move which can be applied to a Phase2Cube. This is a number in the range [0, 10), corresponding to F2 B2 R2 L2 U U' U2 D D' D2 respectively.
func SolvePhase2 ¶
func SolvePhase2(cube Phase2Cube, maxLen int, heuristic *Phase2Heuristic, moves *Phase2Moves) []Phase2Move
SolvePhase2 finds the first solution to a Phase2Cube, or gives up after maxLen moves.
func (Phase2Move) Face ¶
func (p Phase2Move) Face() int
Face returns a number from [1, 6] corresponding to the face of the move if it were applied on the Y axis.
func (Phase2Move) Inverse ¶
func (p Phase2Move) Inverse() Phase2Move
Inverse returns the move's inverse.
func (Phase2Move) Move ¶
func (p Phase2Move) Move(axis int) Move
Move converts the Phase2Move into a regular Move. The axis argument indicates the axis that the move should act on (i.e. the axis of the corresponding Phase2Cube). This is a number in [0, 3).
func (Phase2Move) String ¶
func (p Phase2Move) String() string
String returns the string representation of the move on the Y axis.
type Phase2Moves ¶
type Phase2Moves struct {
CornerMoves [40320][10]int
EdgeMoves [40320][10]int
SliceMoves [24][10]int
}
Phase2Moves is a table containing the necessary data to efficiently perform moves on a Phase2Cube.
func NewPhase2Moves ¶
func NewPhase2Moves() *Phase2Moves
NewPhase2Moves generates a Phase2Moves table.
type Rotation ¶
type Rotation int
A Rotation is a way of rotating the entire cube around the x, y, or z axes. There are 9 total rotations, 0 through 8. The first three rotation values are x, y, and z. The next three are x', y', and z'. The final three are x2, y2, and z2.
func NewRotation ¶
NewRotation creates a Rotation around a given axis (0=x, 1=y, 2=z), for a given number of turns, where "x" has 1 turn, "x'" has -1 turn, and "x2" has 2 turns.
func ParseRotation ¶
ParseRotation parses a WCA rotation string.
func (Rotation) Axis ¶
Axis returns a number 0, 1, or 2, indicating the x, y, or z axis respectively.
type Solver ¶
type Solver struct {
// contains filtered or unexported fields
}
A Solver finds shorter and shorter solutions in the background.
func NewSolverTables ¶
func NewSolverTables(c CubieCube, max int, tables SolverTables) *Solver
NewSolverTables creates a new solver using a set of pre-generated tables.
type SolverTables ¶
type SolverTables struct {
P1Heuristic *Phase1Heuristic
P1Moves *Phase1Moves
P2Heuristic *Phase2Heuristic
P2Moves *Phase2Moves
}
type StickerCube ¶
type StickerCube [54]int
A StickerCube is simply a list of 54 stickers.
Each sticker is a number between 1 and 6. Here is a mapping for a standard cube: 1=white, 2=yellow, 3=green, 4=blue, 5=red, 6=orange.
The order of the stickers is well defined but slightly tricky to memorize. The stickers are grouped by face, so the first 9 correspond to the top, the next to the bottom, next to the front, then the back, the right, then the left.
The order of the stickers on a given face are well defined as well. If you do entry as I describe below, you will always type colors from left to right, top to bottom as if you were reading a book:
1. First, hold the cube so that the side you wish to be in front is in front, and the side you wish to be on top is on top. Now perform an x' so that the top side is in the front and enter the (now) front side by reading the top left color, then the one to its right, then the one to its right, then the far left sticker on the second row, etc. This is the same way you would read a book.
2. Now perform an x2 so that the original bottom side is now in the front. Enter this side the same way as above.
3. Now do an x' to reset the orientation of the cube, and type the front side the same way as you entered the other two.
4. Now do a y2 and enter the back side the same way as the other three sides.
5. Now do a y' so that the original right side is in front, and enter it in.
6. Now do a y2 and enter the original left side.
func InputStickerCube ¶
func InputStickerCube() (*StickerCube, error)
InputStickerCube reads user input for a sticker cube. The cube is not validated beyond checking that each sticker occurs 9 times.
func ParseStickerCube ¶
func ParseStickerCube(str string) (*StickerCube, error)
ParseStickerCube parses a space-delimited list of faces.
func SolvedStickerCube ¶
func SolvedStickerCube() StickerCube
SolvedStickerCube returns a solved sticker cube.
func (*StickerCube) CubieCube ¶
func (s *StickerCube) CubieCube() (*CubieCube, error)
CubieCube converts a StickerCube to a CubieCube.
func (*StickerCube) ReinterpretCenters ¶
func (s *StickerCube) ReinterpretCenters()
ReinterpretCenters changes the meaning of different stickers so that the cube is oriented with 1 on top, 3 in front. In other words, it recolors the cube to be in the standard color scheme.
func (*StickerCube) Rotate ¶
func (s *StickerCube) Rotate(r Rotation)
Rotate applies a rotation to the stickers. It moves the centers as well, so it might be necessary to call s.ReinterpretCenters() before converting s to a CubieCube.
func (*StickerCube) String ¶
func (s *StickerCube) String() string
String generates a space-delimited list of faces in human-readable form.
Source Files
Directories