De Rubiks kubus is een driedimensionale combinatiepuzzel

De Rubiks kubus is een driedimensionale combinatiepuzzel uitgevonden door Emo Rubik in 1974. De fysieke versie van de Rubiks kubus bestaat uit kleine blokjes die rond een centrale as draaien. Klassiek heeft de puzzel zes vlakken, elk met negen blokken gerangschikt in een vierkant van 3 × 3. Er bestaan ​​meer gecompliceerde versies van de Rubiks kubus met N × N vlakken. Elk blok heeft een gekleurde sticker in wit, rood, blauw, oranje, groen of geel. Om de puzzel op te lossen, moet de speler één strook blokken tegelijk roteren totdat elk van de zes vlakken van de kubus gevuld is met een enkele kleur.

Elk jaar worden er over de hele wereld tientallen Rubiks kubuscompetities gehouden waarbij het doel is om de puzzel zo snel mogelijk op te lossen. Er bestaat een aantal gemakkelijk te onthouden algoritmen waarmee spelers elke configuratie van Rubik’s kubus kunnen oplossen. Het oplossen van deze puzzels is echter niet alleen interessant voor spelers. Er is ook veel academische interesse in het ontwerpen van efficiënte algoritmen om een ​​Rubiks kubus in zo min mogelijk beurten op te lossen.

Het doel van deze case study is om een ​​mixed-integer programma te presenteren dat een N × N × N Rubiks kubus kan oplossen vanuit elke startconfiguratie.

METHODOLOGIE
Gegeven een N × N × N Rubiks kubus, bestaat er een unieke set van m zetten. Het is belangrijk op te merken dat zetten een reeks zijn die veel positie-naar-positie-toewijzingen omvat. We definiëren bewegingen als kwartomwentelingen van een blokstrook in beide richtingen; halve slagen vereisen twee zetten.

Beschouw de tweedimensionale weergave van een standaard 3 × 3 × 3 Rubiks kubus. In deze  roteert een rotatie van vlak 6 van de kubus ook een rij in de vier aangrenzende vlakken. Het is gemakkelijk om te verifiëren dat alle zetten kunnen worden uitgeput door een willekeurig vlak te nemen en alle rij- en kolomgewijze bochten te overwegen, en vervolgens een verticaal (horizontaal) aangrenzend vlak te nemen en alle rijgewijze (kolomgewijze) bochten te overwegen. Met de standaard 3 × 3 × 3 kubus levert dit 18 unieke zetten op. Meer in het algemeen levert dit 6N unieke bewegingen op voor een N × N × N-kubus.

NOTATIE
De notatie die wordt gebruikt om het model te definiëren, wordt hieronder geïntroduceerd.

N staat voor het aantal vlakken op de Rubiks kubus (voor deze case study gaan we uit van N = 3).
De vlakken van de Rubiks kubus worden geïndexeerd door f = 1,…, 6.
Laat r, c = 1,…, N de rijen en kolommen van elk vlak indexeren. Het tupel (f, r, c) is een vaste positie op de Rubiks kubus.
De functie x (f, r, c, t) definieert de kleur van het blok in positie (f, r, c) op beurt t. Omdat er zes vlakken zijn, kan x (f, r, c, t) waarden van één tot zes aannemen, die de zes kleuren van de kubus vertegenwoordigen.
Laat A (f, r, c) de reeks zetten aangeven die bij positie (f, r, c) horen; dat wil zeggen, de reeks zetten waarbij het blok in positie (f, r, c) beweegt en dientengevolge wordt vervangen door een nieuw blok. Dus als zet m∈A (f, r, c) wordt gemaakt op beurt t, x (f, r, c, t) = x (fm, rm, cm, t + 1), waarbij (fm, rm, cm ) is de nieuwe positie van het blok dat oorspronkelijk positie bezette (f, r, c) na zet m.
ALLE MOGELIJKE BEWEGINGEN BEREKENEN VOOR RUBIK’S CUBE
Gegeven ons raamwerk kan een reeks heuristieken worden bedacht die alle zetten automatisch genereert voor elke N × N × N Rubiks kubus. Figuur (2) is een momentopname van de code die de eerste 3 zetten op een 3 × 3 × 3 kubus produceert.

rubiks kubus