**Forked from https://github.com/pglass/cube, this would not be possible without his work. <3**
# Overview
This is a Python 3 implementation of a (3x3) Rubik's Cube solver.
It contains:
- A simple implementation of the cube
- A solver that follows a fixed algorithm
- An unintelligent solution sequence optimizer
- A decent set of test cases
On top of that, this CTF fork contains:
- An extension of the cube that allows each piece to contain a piece of data (like a character)
- No new tests!
- A move inverter, to move us into an arbitrary state
## Installation
The package is hosted on PyPI.
```
pip install ctf-rubik-cube
```
# Example Usage
```python
from rubik.cube import Cube
c = Cube("OOOOOOOOOYYYWWWGGGBBBYYYWWWGGGBBBYYYWWWGGGBBBRRRRRRRRR")
print(c)
```
```
OOO
OOO
OOO
YYY WWW GGG BBB
YYY WWW GGG BBB
YYY WWW GGG BBB
RRR
RRR
RRR
```
```python
from rubik import cube
from rubik.solve import Solver
def solve_with_data():
"""
cube_str looks like:
UUU 0 1 2
UUU 3 4 5
UUU 6 7 8
LLL FFF RRR BBB 9 10 11 12 13 14 15 16 17 18 19 20
LLL FFF RRR BBB 21 22 23 24 25 26 27 28 29 30 31 32
LLL FFF RRR BBB 33 34 35 36 37 38 39 40 41 42 43 44
DDD 45 46 47
DDD 48 49 50
DDD 51 52 53
"""
# Note that the middle piece can be arbitrary, not locked to ULFRBD
# Using colors here for readability, but you can use any string
start_str = "BBWOGYWGRYGGRYGYROGWRGRRWWOYORBYRBOYOWRWGOBBYGOBBBWOYW"
data_str = "{LOLS_SLWCS_A?REBLE}RAOPGNKKØGFEP__URSAAUIUO_PLLDOEXB_"
c_root = cube.Cube(start_str, data_str)
print("Initial colors:")
print(c_root, end="\n\n")
print("Initial data:")
print(c_root.str_data(), end="\n\n")
solver = Solver(c_root)
solver.solve()
print("Solved colors:")
print(c_root, end="\n\n")
print("Solved data:")
print(c_root.str_data(), end="\n\n")
print("As you can try to read out: 'PAPA{FLAGS_ARE_FUN}'")
if __name__ == '__main__':
solve_with_data()
```
```
Initial colors:
BBW
OGY
WGR
YGG RYG YRO GWR
GRR WWO YOR BYR
BOY OWR WGO BBY
GOB
BBW
OYW
Initial data:
{LO
LS_
SLW
CS_ A?R EBL E}R
AOP GNK KØG FEP
__U RSA AUI UO_
PLL
DOE
XB_
Solved colors:
RRR
RRR
RRR
BBB WWW GGG YYY
BBB WWW GGG YYY
BBB WWW GGG YYY
OOO
OOO
OOO
Solved data:
RBW
GOP
APA
{FL AGS _AR E_C
OOL }NE USL ?EB
_DU _SO ESP UK_
ILL
_ØL
XKR
As you can try to read out: 'PAPA{FLAGS_ARE_FUN}'
```
# Solve for target pattern:
**Possible bug:** The orientation of the cube faces is not normalized, to its possible that we end up with the wrong state.
Will fix this if I have time/need too :)
```python
from rubik import cube
from rubik.solve import Solver
from solve_random_cubes import random_cube
def solve_for_target():
base_str = random_cube().flat_str()
target_str = random_cube().flat_str()
print(f"Base: {base_str}")
print(f"Target: {target_str}")
c_root = cube.Cube(base_str)
c_target = cube.Cube(target_str)
print("Initial:")
print(c_root, end="\n\n")
solver = Solver(c_root)
solver.solve()
solver_t = Solver(c_target)
solver_t.solve()
# Generate new cube
c = cube.Cube(base_str)
# Solve to base state
c.sequence(" ".join(solver.moves))
print(c)
# Solve to target state, but inversing a solve to base state from the target
c.inverse_sequence(" ".join(solver_t.moves))
print("Solved:")
print(c, end="\n\n")
if __name__ == '__main__':
solve_for_target()
```
## Implementation
### Piece
The cornerstone of this implementation is the Piece class. A Piece stores three
pieces of information:
1. An integer `position` vector `(x, y, z)` where each component is in {-1, 0,
1}:
- `(0, 0, 0)` is the center of the cube
- the positive x-axis points to the right face
- the positive y-axis points to the up face
- the positive z-axis points to the front face
2. A `colors` vector `(cx, cy, cz)`, giving the color of the sticker along each
axis. Null values are place whenever that Piece has less than three sides. For
example, a Piece with `colors=('Orange', None, 'Red')` is an edge piece with an
`'Orange'` sticker facing the x-direction and a `'Red'` sticker facing the
z-direction. The Piece doesn't know or care which direction along the x-axis
the `'Orange'` sticker is facing, just that it is facing in the x-direction and
not the y- or z- directions.
3. A `data` vector `(dx, dy, dz)`, giving the data of the sticker along each axis
Using the combination of `position` and `color` vectors makes it easy to
identify any Piece by its absolute position or by its unique combination of
colors.
A Piece provides a method `Piece.rotate(matrix)`, which accepts a (90 degree)
rotation matrix. A matrix-vector multiplication is done to update the Piece's
`position` vector. Then we update the `colors` vector, by swapping exactly two
entries in the `colors` vector:
- For example, a corner Piece has three stickers of different colors. After a
90 degree rotation of the Piece, one sticker remains facing down the same
axis, while the other two stickers swap axes. This corresponds to swapping the
positions of two entries in the Piece’s `colors` vector.
- For an edge or face piece, the argument is the same as above, although we may
swap around one or more null entries.
### Cube
The Cube class is built on top of the Piece class. The Cube stores a list of
Pieces and provides nice methods for flipping slices of the cube, as well as
methods for querying the current state. (I followed standard [Rubik's Cube
notation](http://ruwix.com/the-rubiks-cube/notation/))
Because the Piece class encapsulates all of the rotation logic, implementing
rotations in the Cube class is dead simple - just apply the appropriate
rotation matrix to all Pieces involved in the rotation. An example: To
implement `Cube.L()` - a clockwise rotation of the left face - do the
following:
1. Construct the appropriate [rotation matrix](
http://en.wikipedia.org/wiki/Rotation_matrix) for a 90 degree rotation in the
`x = -1` plane.
2. Select all Pieces satisfying `position.x == -1`.
3. Apply the rotation matrix to each of these Pieces.
To implement `Cube.X()` - a clockwise rotation of the entire cube around the
positive x-axis - just apply a rotation matrix to all Pieces stored in the
Cube.
### Solver
The solver implements the algorithm described
[here](http://www.chessandpoker.com/rubiks-cube-solution.html). It is a
layer-by-layer solution. First the front-face (the `z = 1` plane) is solved,
then the middle layer (`z = 0`), and finally the back layer (`z = -1`). When
the solver is done, `Solver.moves` is a list representing the solution
sequence.
My first correct-looking implementation of the solver average 252.5 moves per
solution sequence on 135000 randomly-generated cubes (with no failures).
Implementing a dumb optimizer reduced the average number of moves to 192.7 on
67000 randomly-generated cubes. The optimizer does the following:
1. Eliminate full-cube rotations by "unrotating" the moves (Z U L D Zi becomes
L D R)
2. Eliminate moves followed by their inverse (R R Ri Ri is gone)
3. Replace moves repeated three times with a single turn in the opposite
direction (R R R becomes Ri)
The solver is not particularly fast. On my machine (a 4.0 Ghz i7), it takes
about 0.06 seconds per solve on CPython, which is roughly 16.7 solves/second.
On PyPy, this is reduced to about 0.013 seconds per solve, or about 76
solves/second.
Raw data
{
"_id": null,
"home_page": "https://github.com/pglass/cube",
"name": "ctf-rubik-cube",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "rubik cube solver - ctf edition",
"author": "Nikolas Papaioannou",
"author_email": "cube@hacky.software",
"download_url": "https://files.pythonhosted.org/packages/f5/7c/75df15fca96e14f58f8b7f320d121d37d728009b2f92cdd4e3bc4348d38e/ctf-rubik-cube-0.0.4.tar.gz",
"platform": null,
"description": "\n\n\n**Forked from https://github.com/pglass/cube, this would not be possible without his work. <3**\n\n# Overview\n\nThis is a Python 3 implementation of a (3x3) Rubik's Cube solver.\n\nIt contains:\n\n- A simple implementation of the cube\n- A solver that follows a fixed algorithm\n- An unintelligent solution sequence optimizer\n- A decent set of test cases\n\nOn top of that, this CTF fork contains:\n- An extension of the cube that allows each piece to contain a piece of data (like a character)\n- No new tests!\n- A move inverter, to move us into an arbitrary state\n\n## Installation\n\nThe package is hosted on PyPI.\n```\npip install ctf-rubik-cube\n```\n\n\n# Example Usage\n\n```python\nfrom rubik.cube import Cube\nc = Cube(\"OOOOOOOOOYYYWWWGGGBBBYYYWWWGGGBBBYYYWWWGGGBBBRRRRRRRRR\")\nprint(c)\n```\n\n```\n OOO\n OOO\n OOO\nYYY WWW GGG BBB\nYYY WWW GGG BBB\nYYY WWW GGG BBB\n RRR\n RRR\n RRR\n```\n\n```python\n\nfrom rubik import cube\nfrom rubik.solve import Solver\n\n\ndef solve_with_data():\n\n \"\"\"\n cube_str looks like:\n UUU 0 1 2\n UUU 3 4 5\n UUU 6 7 8\n LLL FFF RRR BBB 9 10 11 12 13 14 15 16 17 18 19 20\n LLL FFF RRR BBB 21 22 23 24 25 26 27 28 29 30 31 32\n LLL FFF RRR BBB 33 34 35 36 37 38 39 40 41 42 43 44\n DDD 45 46 47\n DDD 48 49 50\n DDD 51 52 53\n \"\"\"\n\n # Note that the middle piece can be arbitrary, not locked to ULFRBD\n # Using colors here for readability, but you can use any string\n start_str = \"BBWOGYWGRYGGRYGYROGWRGRRWWOYORBYRBOYOWRWGOBBYGOBBBWOYW\"\n data_str = \"{LOLS_SLWCS_A?REBLE}RAOPGNKK\u00d8GFEP__URSAAUIUO_PLLDOEXB_\"\n\n c_root = cube.Cube(start_str, data_str)\n print(\"Initial colors:\")\n print(c_root, end=\"\\n\\n\")\n print(\"Initial data:\")\n print(c_root.str_data(), end=\"\\n\\n\")\n\n solver = Solver(c_root)\n solver.solve()\n\n print(\"Solved colors:\")\n print(c_root, end=\"\\n\\n\")\n\n print(\"Solved data:\")\n print(c_root.str_data(), end=\"\\n\\n\")\n\n print(\"As you can try to read out: 'PAPA{FLAGS_ARE_FUN}'\")\n\n\nif __name__ == '__main__':\n solve_with_data()\n```\n\n```\nInitial colors:\n BBW\n OGY\n WGR\nYGG RYG YRO GWR\nGRR WWO YOR BYR\nBOY OWR WGO BBY\n GOB\n BBW\n OYW\n\nInitial data:\n {LO\n LS_\n SLW\nCS_ A?R EBL E}R\nAOP GNK K\u00d8G FEP\n__U RSA AUI UO_\n PLL\n DOE\n XB_\n\nSolved colors:\n RRR\n RRR\n RRR\nBBB WWW GGG YYY\nBBB WWW GGG YYY\nBBB WWW GGG YYY\n OOO\n OOO\n OOO\n\nSolved data:\n RBW\n GOP\n APA\n{FL AGS _AR E_C\nOOL }NE USL ?EB\n_DU _SO ESP UK_\n ILL\n _\u00d8L\n XKR\n\nAs you can try to read out: 'PAPA{FLAGS_ARE_FUN}'\n```\n\n# Solve for target pattern:\n\n**Possible bug:** The orientation of the cube faces is not normalized, to its possible that we end up with the wrong state.\nWill fix this if I have time/need too :)\n\n```python\nfrom rubik import cube\nfrom rubik.solve import Solver\nfrom solve_random_cubes import random_cube\n\ndef solve_for_target():\n base_str = random_cube().flat_str()\n target_str = random_cube().flat_str()\n\n print(f\"Base: {base_str}\")\n print(f\"Target: {target_str}\")\n\n c_root = cube.Cube(base_str)\n c_target = cube.Cube(target_str)\n\n print(\"Initial:\")\n print(c_root, end=\"\\n\\n\")\n\n solver = Solver(c_root)\n solver.solve()\n\n solver_t = Solver(c_target)\n solver_t.solve()\n\n # Generate new cube\n c = cube.Cube(base_str)\n # Solve to base state\n c.sequence(\" \".join(solver.moves))\n print(c)\n \n # Solve to target state, but inversing a solve to base state from the target\n c.inverse_sequence(\" \".join(solver_t.moves))\n\n print(\"Solved:\")\n print(c, end=\"\\n\\n\")\n\nif __name__ == '__main__':\n solve_for_target()\n\n```\n\n\n## Implementation\n\n### Piece\n\nThe cornerstone of this implementation is the Piece class. A Piece stores three\npieces of information:\n\n1. An integer `position` vector `(x, y, z)` where each component is in {-1, 0,\n1}:\n - `(0, 0, 0)` is the center of the cube\n - the positive x-axis points to the right face\n - the positive y-axis points to the up face\n - the positive z-axis points to the front face\n\n2. A `colors` vector `(cx, cy, cz)`, giving the color of the sticker along each\naxis. Null values are place whenever that Piece has less than three sides. For\nexample, a Piece with `colors=('Orange', None, 'Red')` is an edge piece with an\n`'Orange'` sticker facing the x-direction and a `'Red'` sticker facing the\nz-direction. The Piece doesn't know or care which direction along the x-axis\nthe `'Orange'` sticker is facing, just that it is facing in the x-direction and\nnot the y- or z- directions.\n\n3. A `data` vector `(dx, dy, dz)`, giving the data of the sticker along each axis\n\nUsing the combination of `position` and `color` vectors makes it easy to\nidentify any Piece by its absolute position or by its unique combination of\ncolors.\n\nA Piece provides a method `Piece.rotate(matrix)`, which accepts a (90 degree)\nrotation matrix. A matrix-vector multiplication is done to update the Piece's\n`position` vector. Then we update the `colors` vector, by swapping exactly two\nentries in the `colors` vector:\n\n- For example, a corner Piece has three stickers of different colors. After a\n 90 degree rotation of the Piece, one sticker remains facing down the same\n axis, while the other two stickers swap axes. This corresponds to swapping the\n positions of two entries in the Piece\u2019s `colors` vector.\n- For an edge or face piece, the argument is the same as above, although we may\n swap around one or more null entries.\n\n### Cube\n\nThe Cube class is built on top of the Piece class. The Cube stores a list of\nPieces and provides nice methods for flipping slices of the cube, as well as\nmethods for querying the current state. (I followed standard [Rubik's Cube\nnotation](http://ruwix.com/the-rubiks-cube/notation/))\n\nBecause the Piece class encapsulates all of the rotation logic, implementing\nrotations in the Cube class is dead simple - just apply the appropriate\nrotation matrix to all Pieces involved in the rotation. An example: To\nimplement `Cube.L()` - a clockwise rotation of the left face - do the\nfollowing:\n\n1. Construct the appropriate [rotation matrix](\nhttp://en.wikipedia.org/wiki/Rotation_matrix) for a 90 degree rotation in the\n`x = -1` plane.\n2. Select all Pieces satisfying `position.x == -1`.\n3. Apply the rotation matrix to each of these Pieces.\n\nTo implement `Cube.X()` - a clockwise rotation of the entire cube around the\npositive x-axis - just apply a rotation matrix to all Pieces stored in the\nCube.\n\n### Solver\n\nThe solver implements the algorithm described\n[here](http://www.chessandpoker.com/rubiks-cube-solution.html). It is a\nlayer-by-layer solution. First the front-face (the `z = 1` plane) is solved,\nthen the middle layer (`z = 0`), and finally the back layer (`z = -1`). When\nthe solver is done, `Solver.moves` is a list representing the solution\nsequence.\n\nMy first correct-looking implementation of the solver average 252.5 moves per\nsolution sequence on 135000 randomly-generated cubes (with no failures).\nImplementing a dumb optimizer reduced the average number of moves to 192.7 on\n67000 randomly-generated cubes. The optimizer does the following:\n\n1. Eliminate full-cube rotations by \"unrotating\" the moves (Z U L D Zi becomes\nL D R)\n2. Eliminate moves followed by their inverse (R R Ri Ri is gone)\n3. Replace moves repeated three times with a single turn in the opposite\ndirection (R R R becomes Ri)\n\nThe solver is not particularly fast. On my machine (a 4.0 Ghz i7), it takes\nabout 0.06 seconds per solve on CPython, which is roughly 16.7 solves/second.\nOn PyPy, this is reduced to about 0.013 seconds per solve, or about 76\nsolves/second.\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "A basic, pure-Python Rubik's cube solver, with support for arbitrary data on each sticker.",
"version": "0.0.4",
"project_urls": {
"Homepage": "https://github.com/pglass/cube"
},
"split_keywords": [
"rubik",
"cube",
"solver",
"-",
"ctf",
"edition"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "623958b471267f3ac46ee5d652921b08cd8ebe3f6f35f3f4c18bf4776155fecd",
"md5": "2976833a0ef4f29b90c346d2c2a77921",
"sha256": "716514877c24f56e9f2c30d5eac3122a4ae9f6d665c5c5280a14eb90f11a77f3"
},
"downloads": -1,
"filename": "ctf_rubik_cube-0.0.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "2976833a0ef4f29b90c346d2c2a77921",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 17433,
"upload_time": "2023-12-14T21:54:33",
"upload_time_iso_8601": "2023-12-14T21:54:33.151477Z",
"url": "https://files.pythonhosted.org/packages/62/39/58b471267f3ac46ee5d652921b08cd8ebe3f6f35f3f4c18bf4776155fecd/ctf_rubik_cube-0.0.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "f57c75df15fca96e14f58f8b7f320d121d37d728009b2f92cdd4e3bc4348d38e",
"md5": "85fe54ae8dc9d418b98b06cbc54b80b3",
"sha256": "cf5a0eede9f9e4d886c8fc701f64d383a7c80806f0fbd17c418fdf1ff92c6d74"
},
"downloads": -1,
"filename": "ctf-rubik-cube-0.0.4.tar.gz",
"has_sig": false,
"md5_digest": "85fe54ae8dc9d418b98b06cbc54b80b3",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 20343,
"upload_time": "2023-12-14T21:54:34",
"upload_time_iso_8601": "2023-12-14T21:54:34.485896Z",
"url": "https://files.pythonhosted.org/packages/f5/7c/75df15fca96e14f58f8b7f320d121d37d728009b2f92cdd4e3bc4348d38e/ctf-rubik-cube-0.0.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-12-14 21:54:34",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "pglass",
"github_project": "cube",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"tox": true,
"lcname": "ctf-rubik-cube"
}
JSON
