13 min to read

Cube with python

How to solve cubic with python?

Featured image

Ah, the Rubik’s Cube – a childhood favorite that’s both simple and oh-so-tricky. I’ve spent countless hours fiddling with those colorful squares, attempting to crack the code. But here’s the thing: while I could easily get one side all nice and uniform, as soon as I tried to sort out the rest, it was like a whirlwind of chaos, and my perfect side was a jumble once more.

The Rubik’s Cube, with its myriad variations, comes in all sorts of shapes and sizes. But for this blog post, I’m focusing on the classic 3x3 cube. I’ll be diving into the world of Python, exploring the potential moves using nodes and edges, and using that knowledge to conquer the cube. It’s kind of mind-blowing to think that through programming, we can crack the puzzle that’s left many of us stumped. I mean, if I couldn’t quite solve it manually, the fact that code might hold the key is pretty mind-boggling!

Let us first assume there are 6 Faces in cube.

The MOVES with the cube are annotated as follows:

A SCRAMBLE is a suite of moves, such as "RURLDU".

I represent a face by a 4-letter code (for faces with 4 tiles: FRONT, BACK) or a 2-letter code (for faces with 2 tiles).

I represent a cube as a dictionary:

This dictionary can be turned into a single string:

The moves are represented as position permutations of this string.

There are 2 additional dictionaries:

TODO

Implement the following algorithm for the generation of the graph:

Given an empty directed graph G
Given a Stack S that contains the solved state

As long as the stack is not empty:
  get the state on top of the stack: start
  For each possible move:
    get the state after executing the move from start
    if there are already edges (start, after) and (after, start) in the graph:
      go to the next move
    else:
      add the edges (start, after), (after, start) with the proper edge attributes
      add the new state to the stack S

  Return G



R = [0,6,2,4,3,5,1,7,8,10,9,11,12,13,15,14]
U = [4,5,2,3,0,1,6,7,9,8,10,11,14,13,12,15]
L = [7,1,5,3,4,2,6,0,11,9,10,8,13,12,14,15]
D = [0,1,6,7,4,5,2,3,8,9,11,10,12,15,14,13]

MOVE_2_PERMUTATION: dict[str, list[int]] = {
    "R": R,
    "U": U,
    "L": L,
    "D": D,
}

POSSIBLE_MOVES = list(MOVE_2_PERMUTATION.keys())

MOVE_2_TIME: dict[str, int] = {
    "R": 1,
    "U": 2,
    "L": 2,
    "D": 3
}

def apply(x: str, move: str) -> str:
    return "".join(x[i] for i in MOVE_2_PERMUTATION[move])

KEY_ORDER = "FBUDLR"

# Version II

from dataclasses import dataclass
from dataclasses import field
from typing import Optional
from collections import defaultdict


def solved_cube():
  solved_cube={
      'F':'WWWW',
      'U':'BB',
      'R':'RR',
      'L':'OO',
      'D':'GG',
      'B':'YYYY'
  }
  return solved_cube



@dataclass
class CubeState:
  faces:dict[str,str]=field(default_factory=solved_cube)

  def __repr__(self)->str:
    result = self.faces['F'] + self.faces['B'] + self.faces['U'] + self.faces['D'] + self.faces['L'] + self.faces['R']
    return str(result)

  def __hash__(self)->int:
    return hash(repr(self))

  def move(self,moving:str):
    my_new=apply(repr(self),moving)
    my_new2=from_repr(my_new).faces
    return CubeState(faces=my_new2)

def from_repr(code:str)->CubeState:
  F=str(code[0:4])
  B=str(code[4:8])
  U=str(code[8:10])
  D=str(code[10:12])
  L=str(code[12:14])
  R=str(code[14:16])
  faces = {
        'F': F,
        'U': U,
        'R': R,
        'L': L,
        'D': D,
        'B': B
    }
  return CubeState(faces=faces)

@dataclass
class Cube:
  state: CubeState = field(default_factory=CubeState)

  def move(self,moving:str):
    my_new=apply(repr(self.state),moving)
    self.state.faces=from_repr(my_new).faces
    return self

  def scramble(self,scramble_move:str):
    scramble_each = [char for char in scramble_move]
    for scrambles in scramble_each:
      self.move(scrambles)
    return self

import networkx as nx
from collections import deque



def generate_graph():
    G = nx.DiGraph()
    S = deque([CubeState()])

    while S:
        start = S.pop()

        for move in POSSIBLE_MOVES:
            after = start.move(move)

            if not G.has_edge(start, after) and not G.has_edge(after, start):
                G.add_edge(start, after, move=move, time=MOVE_2_TIME[move], turn=1)
                G.add_edge(after, start, move=move, time=MOVE_2_TIME[move], turn=1)
                S.append(after)
    return G



@dataclass
class Solution:
  moves:str
  time:int

@dataclass
class CubeSolver:
    _G: nx.DiGraph = field(init=False,default_factory=generate_graph)

    def __call__(self, cube: Cube, minimize: str) -> 'Solution':
        start_state = cube.state
        end_state = CubeState()
        my_shortest=nx.shortest_path(self._G, source=start_state, target=end_state, weight=minimize)
        moves_before_combine = [self._G[u][v]["move"] for u, v in zip(my_shortest, my_shortest[1:])]
        moves = ''.join(moves_before_combine)
        total_time = nx.path_weight(self._G, path=my_shortest, weight="time")
        return Solution(moves=moves, time=total_time)

    def max_moves(self) -> int:
        return nx.diameter(self._G)