Rubik-kocka matematika

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 15-én felülvizsgált verziótól ; az ellenőrzések 17 szerkesztést igényelnek .
Rubik-kocka matematika
 Médiafájlok a Wikimedia Commons oldalon

A Rubik-kocka matematikája a Rubik-kocka tulajdonságainak absztrakt matematikai nézőpontból történő tanulmányozására szolgáló matematikai módszerek összessége . A matematikának ez az ága a kocka összeállítási algoritmusokat tanulmányozza és értékeli. Gráfelmélet , csoportelmélet , kiszámíthatóságelmélet és kombinatorika alapján .

Számos algoritmus létezik arra, hogy a Rubik-kockát egy tetszőleges konfigurációból a végső konfigurációba (az összeállított kockába) vigye át. 2010-ben szigorúan bebizonyosodott, hogy legfeljebb 20 lapfordulat elegendő a Rubik-kocka tetszőleges konfigurációból összeszerelt konfigurációba való átviteléhez (amelyet gyakran "összeállításnak" vagy "megoldásnak" neveznek) [1] . Ez a szám a Rubik-kockacsoport Cayley-gráfjának átmérője [2] . 2014-ben bebizonyosodott, hogy 26 mozdulat mindig elegendő a Rubik-kocka megoldásához, a lapok mindössze 90°-os elforgatásával [3] .

Azt az algoritmust, amely a lehető legkevesebb mozdulattal old meg egy rejtvényt, Isten algoritmusnak nevezzük .

Jelölés

Ez a cikk a David Singmaster által kifejlesztett és 1981-ben általa publikált "Singmaster jelölést" [4] [5] használ a 3 × 3 × 3 méretű Rubik-kocka lapjainak forgási sorrendjének jelölésére .

A betűk a bal ( bal ), jobb ( jobb ), első ( elülső ), hátsó ( hátul ), felső ( fel ) és alsó ( lefelé ) oldalak óramutató járásával megegyező 90°-os elforgatását jelzik. A 180°-os fordulatokat egy 2-es hozzáadásával jelzi a betű jobb oldalán, vagy egy 2-es felső index hozzáadásával a betű jobb oldalán. Az óramutató járásával ellentétes 90°-os elforgatást egy kötőjel ( ′ ) vagy a -1 felső index hozzáadásával jelezzük a betű jobb oldalán. Így például a és bejegyzések egyenértékűek, valamint a és a bejegyzések .

Konfigurációs grafikon metrikák

A megoldás hosszának ( metrika ) mérésének két leggyakoribb módja van . Az első mód - a megoldás egy fordulata az arc 90°-os elfordulásának minősül ( negyedfordulat metrika , QTM ). A második módszer szerint az arc félfordulatát is figyelembe veszik 1 mozdulatnál ( face turn metrika , FTM , néha HTM - félfordulat metrika jelöli ). Így az F2-t (az elülső oldal 180°-os elfordítása) két lépésnek kell számítani a QTM metrikában, vagy 1 lépésnek az FTM metrikában [6] [7] .

A használt metrika sorozat hosszának szövegben történő jelzésére a [8] [9] [10] jelölést használjuk , amely a lépések számából és a metrika megjelölésének kis kezdőbetűjéből áll. A 14f a "14 lépést az FTM-metrikában", a 10q pedig a "10 lépést a QTM-metrikában" jelenti. Annak jelzésére, hogy a lépések száma a minimális egy adott metrikában, egy csillagot használunk : a 10f* a megoldás optimálisságát jelöli 10 FTM lépésben.

Rubik-kocka csoport

A Rubik-kocka egy matematikai csoport példájának tekinthető .

A Rubik-kocka lapjainak mind a hat elforgatása a 48 Rubik-kocka címkék halmazának szimmetrikus csoportjának elemének tekinthető , amelyek nem a lapok középpontjai. Pontosabban, mind a 48 címkét megjelölhetjük 1-től 48-ig terjedő számokkal, és mindegyik lépéshez hozzárendelhetjük a szimmetrikus csoport egy-egy elemét .

Ekkor a Rubik-kocka csoportot hat lapelforgatással generált alcsoportként határozzuk meg :

A csoport sorrendje : [11] [12]

A konfigurációk mindegyike legfeljebb 20 mozdulattal oldható meg (ha az arc bármely fordulatát mozdulatnak számítjuk) [1] .

Egy elem legmagasabb sorrendje 1260. Például a lépések sorozatát 1260 -szor kell megismételni, mielőtt a Rubik-kocka visszatér eredeti állapotába [13] .

Isten algoritmusa

Az Isten algoritmusának keresése legkésőbb 1980-ban kezdődött, amikor is megnyitottak egy levelezőlistát a Rubik-kocka rajongói számára [6] . Azóta matematikusok, programozók és amatőrök igyekeznek megtalálni Isten algoritmusát, hogy a gyakorlatban a minimális számú mozdulattal megoldják a Rubik-kockát. Ehhez a problémához kapcsolódott az Isten számának meghatározása – a mozdulatok száma, amely mindig elegendő a rejtvény befejezéséhez.

2010-ben Thomas Rokiki Palo Alto programozója, Herbert Kotsemba darmstadti matematikatanár, Morley Davidson, a Kenti Egyetem matematikusa és a Google Inc. mérnöke. John Dethridge bebizonyította, hogy a Rubik-kocka bármilyen szétszerelt állapotból 20 mozdulattal összeállítható. Ebben az esetben az arc bármely fordulatát egy mozdulatnak tekintették. A számítás mennyisége 35 év CPU-idő volt , amelyet a Google adományozott [1] [14] [15] . A teljesítményre és a számítógépek számára vonatkozó műszaki adatokat nem hozták nyilvánosságra. A számítások időtartama több hét volt [16] [17] [18] .

2014-ben Thomas Rockicki és Morley Davidson bebizonyította, hogy a Rubik-kocka legfeljebb 26 mozdulattal megoldható 180°-os fordulatok használata nélkül. A számítások mennyisége 29 év processzoridő volt az ohiói szuperszámítási központban [3] .

Isten számának alsó határai

Könnyen kimutatható, hogy vannak olyan megoldható konfigurációk [19] , amelyek nem oldhatók meg kevesebb mint 17 lépéssel az FTM metrikában vagy 19 lépésnél a QTM metrikában.

Ez a becslés javítható további azonosságok figyelembevételével: két ellentétes lap forgásának kommutativitása (LR = RL, L2 R = R L2 stb.) Ez a megközelítés lehetővé teszi, hogy Isten számának alsó korlátját kapjuk 18f-ben. vagy 21q [20] [21 ] .

Ez a becslés régóta a legismertebb. Ez egy nem építő jellegű bizonyításból következik, mivel nem jelez konkrét példát olyan konfigurációra, amelyhez 18f vagy 21q szükséges.

Az egyik olyan konfiguráció, amelyre nem sikerült rövid megoldást találni, az úgynevezett " superflip " vagy "12-flip". A "Superflip"-ben minden sarok- és élkocka a helyén van, de minden élkocka ellentétes irányban [22] . A Rubik-kocka gráfban a szuperflipnek megfelelő csúcs egy lokális maximum: ebből a konfigurációból minden elmozdulás csökkenti a távolságot a kezdeti konfigurációtól. Ez arra utalt, hogy a szuperflip a legnagyobb távolságban van a kezdeti konfigurációtól. Vagyis a szuperflip egy globális maximum [23] [24] [25] .

1992-ben Dick T. Winter 20f-ben talált megoldást a szuperflipre [26] . 1995-ben Michael Reed bebizonyította ennek a megoldásnak az optimálisságát [27] , aminek következtében az Isten számának alsó korlátja 20 FTM lett. 1995-ben Michael Reid felfedezte a "szuperflip" megoldását a 24q-ban [28] . Ennek a megoldásnak az optimálisságát Jerry Bryan bizonyította [29] . 1998-ban Michael Reed talált egy konfigurációt, amelynek optimális megoldása 26q* volt [30] .

Isten számának felső határa

Ahhoz, hogy Isten számának felső korlátját megkapjuk, elegendő bármely, véges számú lépésből álló rejtvény-összeállítási algoritmust megadni.

Az Isten számának első felső határa több szakaszból álló „emberi” algoritmusokon alapult. Az egyes szakaszokhoz tartozó felülről származó becslések összeadása lehetővé tette, hogy több tíz vagy száz lépés nagyságrendű végső becslést kapjunk.

Valószínűleg az első konkrét becslést felülről David Singmaster adta 1979-ben. Összeszerelő algoritmusa lehetővé tette a puzzle összeállítását legfeljebb 277 mozdulattal [16] [31] . A Singmaster később beszámolt arról, hogy Alvin Berlekamp , ​​John Conway és Richard Guy olyan összeállítási algoritmust fejlesztettek ki, amely legfeljebb 160 mozdulatot igényel. Hamarosan "Conway cambridge-i kubistáinak" egy csoportja, akik egy arc kombinációinak listáját állították össze, találtak egy 94 irányú algoritmust [16] [32] . 1982-ben a Kvant magazin közzétett egy listát azokról a kombinációkról, amelyek lehetővé teszik a Rubik-kocka 79 mozdulattal történő megoldását [33] .

Thistlethwaite algoritmusa

Az 1980-as évek elején Morvin Thistlethwaite angol matematikus kifejlesztett egy algoritmust, amely jelentősen javította a felső határt. Az algoritmus részleteit Douglas Hofstadter tette közzé 1981-ben a Scientific Americanban . Az algoritmus csoportelméleten alapult, és négy szakaszból állt.

Leírás

Thistlethwaite számos 4-es hosszúságú alcsoportot használt

ahol

Ez a csoport ugyanaz, mint a Rubik-kocka csoport . A sorrend : [34] [35]
Ez az alcsoport tartalmazza az összes olyan konfigurációt, amely megoldható a bal vagy jobb oldal ±90°-os elforgatása nélkül. A sorrendje az
Ez az alcsoport tartalmazza az összes megoldható konfigurációt, feltéve, hogy a négy függőleges oldal ±90°-os elforgatása tilos. A sorrendje az
Ez az alcsoport tartalmazza az összes olyan konfigurációt, amely csak 180°-os fordulatokkal (félfordulatokkal) megoldható. Ezt nevezték "négyzetcsoportnak" (négyzetcsoport). A sorrendje az
Ez az alcsoport egyetlen kezdeti konfigurációt tartalmaz.

Az első szakaszban a csoport egy tetszőlegesen megadott konfigurációja az alcsoportban található konfigurációvá redukálódik . A második szakasz célja, hogy a kockát az alcsoport konfigurációjába hozza anélkül, hogy a bal és jobb oldalt ±90°-kal elforgatná. A harmadik szakaszban a Rubik-kocka a csoportba tartozó konfigurációra redukálódik , míg a függőleges lapok ±90°-os elforgatása tilos. Az utolsó, negyedik szakaszban a Rubik-kockát a lapok 180°-os elfordításával teljesen összeállítják.

Az alcsoport indexei 2048 , 1082565, 29400 és 663552.

Mind a négy jobb coset családhoz létrejön egy keresőtábla , amelynek mérete megegyezik a csoport alcsoportjának indexével . Az egyes alcsoportok szomszédsági osztályaihoz a keresési táblázat egy olyan lépéssorozatot tartalmaz, amely az adott szomszédsági osztály bármely konfigurációját olyan konfigurációvá alakítja, amely magában az alcsoportban található .

A keresési táblákban lévő bejegyzések számának csökkentése érdekében Thistlethwaite egyszerűsített előzetes lépéseket alkalmazott. Eredetileg 85 lépést kapott. 1980 folyamán ez a pontszám 80 lépésre, majd 63-ra és 52-re csökkent [16] [36] . Thistlethwaite tanítványai teljes elemzést készítettek az egyes szakaszokról. A táblázatokban a maximális értékek 7, 10, 13 és 15 FTM ütés. Mivel 7 + 10 + 13 + 15 = 45, a Rubik-kocka mindig 45 FTM [25] [37] [38] mozdulattal megoldható .

Schreier gróf

A Schreier-gráf egy gráf, amely egy csoporthoz, egy generáló halmazhoz és egy alcsoporthoz. A Schreier-gráf minden csúcsa egy jobb cosetnéhány. Schreier gróf élei párok.

Thistlethwaite algoritmusának mind a négy szakasza a Schreier-gráf szélességi bejárása , ahol a csoport generáló halmaza .

Így a 45 lépés felső becslése az

ahol

az egység cosetnek megfelelő csúcs excentricitása .

A Schreier-gráf fogalmát Radu [39] , Kunkle és Cooperman [40] munkáiban használták .

Thistlethwaite algoritmusának módosításai

1990 decemberében Hans Kloosterman Thistlethwaite módszerének módosított változatával igazolta a 42 lépés elegendőségét [1] [20] [41] .

1992 májusában Michael Reid kimutatta, hogy a 39f vagy az 56q elegendő [42] . Módosításában a következő alcsoportok láncát használtuk:

Néhány nappal később Dick T. Winter 37 lépésre csökkentette FTM-pontszámát [43] .

2002 decemberében Ryan Hayes kifejlesztette Thistlethwaite algoritmusának a Rubik -kocka gyors megoldására tervezett változatát [44] .

Kétfázisú Kotsemba algoritmus

Thistlethwaite algoritmusát 1992-ben Herbert Kotsemba, darmstadti matematikatanár fejlesztette tovább.

Leírás

Kotsemba kettőre csökkentette az algoritmus lépéseinek számát [20] [45] [46] :

A csoport vizuális leírását a következő jelölésekkel kaphatjuk meg [20] [47] :

  • Jelölje meg az összes U és D címkét "+" jellel.
  • Az FR , FL , BL és BR élelemeken található F és B címkéket "-" jelöli.
  • Az összes többi címkét hagyja jelöletlenül.

Ekkor a csoport minden konfigurációja ugyanazzal a jelöléssel rendelkezik (egybeesik az összeállított kockán lévő jelöléssel).

A megoldás két szakaszból áll. Az első szakaszban az adott konfigurációt egy mozdulatsorral lefordítják valamilyen konfigurációba . Vagyis az első szakasz feladata a kezdeti konfigurációnak megfelelő jelölés visszaállítása, figyelmen kívül hagyva a címkék színeit.

A második szakaszban a konfigurációt egy mozdulatsorral továbbítják a kezdeti konfigurációhoz. Ebben az esetben az oldallapok ±90°-os elforgatása nem kerül felhasználásra, ami miatt a jelölés automatikusan mentésre kerül.

A mozdulatsorok ragasztása szuboptimális megoldás az eredeti konfigurációhoz képest [20] [46] [48] .

Alternatív szuboptimális megoldások

A Kotsemba algoritmusa az első megoldás megtalálása után sem áll le. Az első szakasz alternatív optimális megoldásai a második szakaszban rövidebb megoldásokhoz vezethetnek, ami csökkenti a megoldás teljes hosszát. Az algoritmus az első szakaszban folytatja a nem optimális megoldások keresését is a hosszuk növelésének sorrendjében [20] [46] [48] .

Megvalósítási jellemzők

A megoldások kereséséhez mind a két szakaszban az IDA* algoritmust használjuk a megfelelő részfeladatok megoldási költségein alapuló heurisztikus függvényekkel [48] .

Az első szakasz feladata három koordinátájú térbeli út megtalálása az ( x 1 , y 1 , z 1 ) koordinátákkal való jelöléstől a (0, 0, 0) címkézésig [49] :

  1. Nyolc sarokelem x 1 tájolása (2187 érték)
  2. Tizenkét élelem y 1 orientációja (2048 érték)
  3. Négy FR , FL , BL és BR élelem z 1 elrendezése (495 érték)

Tekintsünk három részproblémát a jelöléstől ( x 1 , y 1 , z 1 ) a jelölésig ( x 1 ', y 1 ', 0 ), ( x 1 ', 0, z 1 '), (0, y 1 ', z 1 '). Az első szakaszban használt h 1 heurisztikus függvény értéke megegyezik ezen részfeladatok megoldásának maximális költségével. A részfeladatok megoldásának költségeit előre kalkulálják és adatbázisok formájában tárolják sablonokkal [50] [51] .

A második szakasz feladata a ( x 2 , y 2 , z 2 ) konfigurációtól a (0, 0, 0) konfigurációig terjedő három koordinátával a térben való út megtalálására korlátozódik [52] :

  1. Permutáció x 2 nyolc sarokelem (40320 érték)
  2. A felső és alsó oldal nyolc élelemének y 2 permutációja (40320 érték)
  3. A középső réteg négy élelemének z 2 permutációja (24 érték)

Tekintsünk három részproblémát az ( x 2 , y 2 , z 2 ) konfigurációtól az ( x 2 ', y 2 ', 0 ), ( x 2 ', 0, z 2 '), (0, y 2 ) konfigurációhoz vezető út megtalálásához ', z2 ') . A második szakaszban használt h 2 heurisztikus függvény értéke megegyezik ezen részfeladatok megoldásának maximális költségével.

Az algoritmus további optimalizációkat használ, amelyek célja a teljesítmény növelése és a [20] [45] [46] [53] táblázatok által elfoglalt memória csökkentése .

Szoftver implementációk

A Cube Explorer az algoritmus szoftveres megvalósítása a Windows operációs rendszerhez. A letöltési linkek Herbert Kotsemba honlapján találhatók [54] . 1992-ben egy 1 MB memóriával és 8 MHz-es frekvenciájú Atari ST PC -n az algoritmus 1-2 percen belül 22 lépésnél hosszabb megoldást tett lehetővé [20] [45] . Egy modern számítógépen a Cube Explorer segítségével néhány másodperc alatt 20 mozdulatnál hosszabb megoldást találhatunk egy tetszőleges konfigurációra [45] .

Az algoritmusnak létezik online változata [55] .

Elemzés

1995-ben Michael Reed kimutatta, hogy a Kotsemba algoritmusának első és második fázisa legfeljebb 12, illetve 18 mozdulatot (FTM) igényelhet. Ebből az következik, hogy a Rubik-kocka mindig 30 mozdulattal megoldható. További elemzések azt mutatták, hogy a 29f vagy a 42q [25] [56] mindig elegendő .

Korff algoritmusa

A Kotsemba algoritmusa lehetővé teszi, hogy gyorsan találjon rövid, szuboptimális megoldásokat. A megtalált megoldás optimálisságának bizonyítása azonban jelentős időt vehet igénybe. Az optimális megoldások megtalálásához speciális algoritmusra volt szükség.

1997-ben kiadott egy algoritmust, amely lehetővé tette számára a Rubik-kocka tetszőleges konfigurációinak optimális megoldását. Tíz véletlenszerűen kiválasztott konfigurációt legfeljebb 18 FTM-mozgásban oldottak meg [57] [58] .

Maga a Korff-algoritmus a következőképpen működik. Mindenekelőtt olyan részproblémákat határoznak meg, amelyek elég egyszerűek a teljes felsoroláshoz. A következő három részfeladatot [25] használtuk :

  1. A rejtvény állapotát csak a nyolc sarokkocka határozza meg, az élek helyzetét és tájolását figyelmen kívül hagyja.
  2. A feladvány állapotát a 12 élkockából hat határozza meg, a többi kockát figyelmen kívül hagyjuk.
  3. A feladvány állapotát a másik hat élkocka határozza meg.

Az egyes részproblémák megoldásához szükséges lépések száma a megoldás befejezéséhez szükséges lépések számának alsó határa. A Rubik-kocka egy tetszőlegesen megadott konfigurációját az IDA* algoritmussal oldjuk meg , amely ezt a becslést használja heurisztikaként. A részfeladatok megoldásának költségeit adatbázisok formájában tároljuk sablonokkal [50] [57] .

Bár ez az algoritmus mindig megtalálja az optimális megoldást, nem határozza meg közvetlenül, hogy a legrosszabb esetben hány lépésre lehet szükség.

Az algoritmus C-beli implementációja megtalálható az [59]-ben .

További fejlesztések

2005-ben Michael Reid QTM-pontszáma 40q-ra javította Silviu Radut [60] . 2006-ban Silviu Radu bebizonyította, hogy a Rubik-kocka 27f-ben [39] vagy 35q-ban [61] megoldható .

2007-ben Daniel Kunkle és Gene Cooperman egy szuperszámítógép segítségével bebizonyították, hogy az összes megoldatlan konfiguráció legfeljebb 26 FTM-mozdulattal megoldható. Az ötlet az volt, hogy a Rubik-kockát a 15 752 négyzet -konfiguráció egyikébe hozzuk , amelyek mindegyike néhány extra mozdulattal végül megoldható. A legtöbb konfigurációt így sikerült megoldani legfeljebb 26 mozdulattal. A fennmaradó konfigurációkat további elemzésnek vetették alá, ami azt mutatta, hogy 26 lépésben is megoldhatók [40] [62] .

Thomas Rokicki 2008-ban publikált egy számítási bizonyítékot az FTM 25 lépéses rejtvény megoldhatóságára [63] . 2008 augusztusában Rokiki bejelentette a megoldhatóság igazolását a 23f-ben [64] . Később ez a becslés 22f-re javult [65] . 2009-ben 29 QTM lépésben is sikerült megmutatnia a megoldhatóságot [66] .

2010-ben Thomas Rokicki, Herbert Kotsemba, Morley Davidson és John Dethridge bebizonyította, hogy bármely Rubik-kocka konfiguráció legfeljebb 20 mozdulattal megoldható az FTM-metrikában [1] [14] . A korábban ismert alsó 20f* becsléssel együtt ez bebizonyította, hogy a Rubik-kocka istenszáma az FTM-mutatóban 20.

2014 augusztusában Rockiki és Davidson bejelentette, hogy a Rubik-kocka istenszáma a QTM-metrikában 26 [3] [67] .

Antipódok keresése

A Rubik-kocka konfigurációját, amely a kezdeti konfigurációtól a legnagyobb távolságra található, antipódnak nevezzük. Az FTM-metrika bármely antipódjának optimális megoldása van 20f*-ban, a QTM-metrika bármely antipódjában pedig 26q*-ban [3] [68] .

Ismeretes, hogy az FTM-metrikában több millió antipód található [69] . Az egyik ilyen konfiguráció a "superflip". Ellenkezőleg, a QTM-metrikában jelenleg csak egy antipodális konfiguráció ismert (nem számítva a belőle forgással kapott konfigurációkat) - az ún. négy folttal összeállított szuperflip [30] [67] [68] [70] . A kezdeti konfigurációtól 25q* távolságra csak két konfiguráció ismert, 24q* távolságban pedig körülbelül 80 ezer konfiguráció [3] [69] .

Aszimptotikus becslések

2011-ben az n  ×  n  ×  n kocka Isten-szám Θ ( n 2  / log( n )) volt [71] [72] .

Egyéb rejtvények

Void Cube

Az üres kocka egy 3x3x3-as Rubik-kocka, központi darabok nélkül.

Az FTM-metrikában a "void - szuperflip " optimális megoldásának hossza 20 [73] [74] , ami azt bizonyítja, hogy 20 lépés szükséges. Mivel az üres kocka a Rubik-kocka gyengített problémája [50], a Rubik-kocka 20 lépésének elégséges bizonyítéka [1] az üres kockára vonatkozik. Ezért az üres kocka istenszáma az FTM-mutatóban 20.

Kocka 4×4×4

A 4×4×4-es kirakó ( Eng.  Rubik's Revenge ) konfigurációinak száma [75]

Metrikák 4×4×4

A 4x4x4-es kocka metrikáját többféleképpen is meghatározhatja. Ez a szakasz a következő mutatókat használja:

  • qs (negyed szelet): egy fordulat a 12 puzzle-réteg bármelyikének ±90°-kal történő elforgatásának minősül;
  • qw (negyedcsavar): egy fordulat bármely külső blokk (vagyis csak olyan felületek vagy lapok, amelyek mellett több szomszédos réteg van egymás után ) ±90°-kal elforgatásának tekintendő;
  • qb (negyed blokk): egy fordulat úgy tekintendő, hogy bármely külső vagy belső blokkot (azaz az egymást követő párhuzamos rétegek sorozatát) ±90°-kal elforgatja a puzzle többi részéhez képest;
  • hs , hw , hb : Ugyanaz, mint az előző 3 mérőszámnál, kivéve, hogy a 180°-os elforgatások is megengedettek.

Egy tetszőleges konfiguráció optimális megoldásának hossza a qb metrikában nem nagyobb, mint a qw vagy qs metrikákban , mivel a másik két q-metrika minden mozgása megengedett a qb metrikában. Ugyanez vonatkozik a h-metrikákra is.

A 4×4×4 istenkocka számának becslései

2006-2007-ben Bruce Norskog elvégezte a 4x4x4-es kocka 5-lépéses elemzését, hasonlóan a Thistlethwaite által a 3x3x3-as Rubik-kocka 4-lépéses elemzéséhez. Az elemzés a hw metrikában 82 elmozdulást [76] , a hs metrikában 77 elmozdulást [77] [78] , a hb metrikában pedig 67 lépést [76] eredményezett .

2011-ben Thomas Rokiki számos létező elképzelés alapján meghatározta az Isten számának alsó határát hat metrikában a 2 × 2 × 2 és 20 × 20 × 20 méretű kockarejtvények esetében [79] .

2013-ban Shuang Chen (陈霜) 82-ről 57 kanyarra csökkentette a teljesítményét [80] .

2015-ben Thomas Rokicki megerősítette az 57 hw -os csúcspontszámot, és új csúcspontokat kapott: 56 hs és 53 hb [81] . Néhány nappal később Shuang Chennek (陈霜) a bizonyítás lépéseinek újradefiniálásával sikerült elérnie az 55 hw és 53 hs felső határát [82] [83] .

A 4×4×4-es vágószerszám jelenlegi ismert felső és alsó pontszáma különböző mérőszámokban a táblázatban látható:

4x4x4 kocka istenszám becslések
mérőszámok hs hw hb qs qw qb
alacsonyabb becslés 32 35 29 37 41 33
felső becslés 53 55 53 ? ? ?

Megaminx

A Megaminx a Rubik-kocka legegyszerűbb analógja dodekaéder formájában. A 12 színből álló Megaminx konfigurációinak száma 1,01·10 68 .

2012-ben Herbert Kotsemba Megaminx istenszámának alsó korlátját 45 tetszőleges szögben vagy ±72°-os szögben 55 elforgatásban határozta meg [84] [85] .
2016-ban Herbert Kotsemba javította a Megaminx istenszámának alsó becslését, és tetszőleges szögben 48 lapelfordulásra növelte [86] .

Lásd még

Jegyzetek

  1. 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; és Dethridge, J. Isten száma 20  . Letöltve: 2013. július 19. Az eredetiből archiválva : 2013. július 21..
  2. A generátorok rendszere szerint, amely a lapok ±90°-os és 180°-os elforgatásából áll.
  3. 1 2 3 4 5 Rokicki, T. és Davidson, M. Isten száma 26 a  negyedforduló metrikájában . Letöltve: 2015. július 4. Az eredetiből archiválva : 2015. július 7..
  4. Joyner, 2002 , p. 7.
  5. Morális és matematikai leckék egy Rubik -kockából  //  Új tudós. – 1982.
  6. 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. A kocka: Végső útmutató a világ legkeresettebb rejtvényéhez – Titkok, történetek, megoldások . - 2009. - S. 26. - 142 p.
  7. Jaap Scherphuis. Hasznos matematika . Metrics  (angol)  (downlink) . Letöltve: 2013. július 17. Az eredetiből archiválva : 2012. november 24..
  8. Jerry Bryan. Jelölési egyezmény (2006. május 27.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  9. David Singmaster. Köbös körlevél  . - 1982. - Iss. 5 és 6 . — 26. o .
  10. Jaap Scherphuis. Rejtvénystatisztika  . _ Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. június 21.
  11. Schönert, Martin Rubik - kocka elemzése GAP segítségével  . Hozzáférés dátuma: 2013. július 19. Az eredetiből archiválva : 2013. január 20.
  12. Jaap Scherphuis. Rubik-kocka 3x3x3  (angol)  (nem elérhető link) . Letöltve: 2013. július 19. Az eredetiből archiválva : 2013. július 28..
  13. Joyner, 2008 , pp. 93 , 108.
  14. 1 2 Herbert Kociemba. Kétfázisú algoritmus és Isten algoritmusa: Isten száma 20  (angolul)  (a hivatkozás nem elérhető) . Hozzáférés dátuma: 2013. július 23. Az eredetiből archiválva : 2013. május 2.
  15. Tomas Rokicki, Herbert Kociemba, Morley Davidson és John Dethridge. A Rubik-kocka csoport átmérője húsz // SIAM J. Discrete Math.. - 2013. - Vol. 27. sz. 2. - P. 1082-1105. - doi : 10.1137/120867366 .
  16. 1 2 3 4 Rik van Grol. Isten  számának keresése . Math Horizons (2010. november). Letöltve: 2013. július 26. Az eredetiből archiválva : 2014. november 9..
  17. Stefan Edelkamp, ​​​​Stefan Schrōdl. Heurisztikus keresés: elmélet és alkalmazások. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
  18. SIAM J. Discrete Math., 27(2), 1082–1105 . Letöltve: 2013. november 19. Az eredetiből archiválva : 2019. december 3.
  19. A "feloldható" konfiguráció olyan konfiguráció, amely lefordítható. Mivel a Rubik-kocka gráfja irányítatlan, ebből következik, hogy az eredeti tetszőleges lépéssorozatból kapott bármely konfiguráció eldönthető. De vannak megoldhatatlan konfigurációk. Például, ha a kocka egyik csúcsát összeszerelt állapotban 120°-kal elforgatjuk, akkor egy megoldhatatlan konfigurációt kapunk.
  20. 1 2 3 4 5 6 7 8 V. Dubrovsky, A. Kalinin. A kubológia hírei  // Kvant . - 1992. - 11. sz . - S. 52-56 .
  21. Jaap Scherphuis. Hasznos matematika . God's Algorithm  (angol)  (nem elérhető link) . Letöltve: 2013. július 17. Az eredetiből archiválva : 2012. november 24..
  22. Michael Reid. Michael Reid Rubik-kocka oldala . M-szimmetrikus pozíciók  (angolul) (2005. május 24.) . Letöltve: 2013. július 17. Az eredetiből archiválva : 2015. július 6..
  23. David Singmaster. Köbös körlevél  . - 1982. - Iss. 5 és 6 . — 24. o .
  24. Joyner, 2002 , p. 149.
  25. 1 2 3 4 Stefan Pochmann. Rubik-kocka és hasonló rejtvények emberi megoldási módszereinek elemzése (Diplomadolgozat  ) . Az eredetiből archiválva : 2014. november 9.
  26. Dik T. Tél. Kociemba algoritmusa  (angol) (1992. május 18.). Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. július 15.
  27. Michael Reid. A szuperflip 20 arcfordítást igényel  ( 1995. január 18.). Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. július 8..
  28. Michael Reid. superflip  (angol) (1995. január 10.). Letöltve: 2013. július 17. Az eredetiből archiválva : 2014. június 19.
  29. Jerry Bryan. M-szimmetrikus pozíciók Qturn hossza  ( 1995. február 19.). Letöltve: 2013. július 17. Az eredetiből archiválva : 2014. június 20.
  30. 12 Michael Reid . négy folttal komponált szuperflip (angolul) (1998. augusztus 2.). Letöltve: 2015. július 4. Az eredetiből archiválva : 2015. október 4..  
  31. L. A. Kaluzsnyin, V. I. Suschansky. Transzformációk és permutációk. - M. , 1985. - S. 143. - 160 p.
  32. David Singmaster. Jegyzetek a Rubik  varázskockához (neopr.) . — Enslow Kiadó, 1981. - S.  30 .
  33. V. Dubrovszkij. The Magic Cube Algorithm  // Kvant . - 1982. - 7. sz . - S. 22-25 .
  34. Ennek és a következő három csoportnak a sorrendjét három tényező szorzataként számítjuk ki, amelyek rendre jelzik a feloldható sarokkonfigurációk számát, a feloldható élkonfigurációk számát, valamint a feloldható konfigurációra vonatkozó általános "paritási" megkötést.
  35. Jaap Scherphuis. Kocka alcsoportok . Az arcmozgatások által generált alcsoportok  (eng.)  (nem elérhető link) . Hozzáférés dátuma: 2013. július 19. Az eredetiből archiválva : 2013. január 20.
  36. Mark Longridge. Progresszív fejlesztések az  algoritmusok megoldásában . Letöltve: 2013. július 28. Az eredetiből archiválva : 2013. október 9..
  37. V. Dubrovszkij. A varázskocka matematikája  // Kvant . - 1982. - 8. sz . - S. 22-27, 48 .
  38. Jaap Scherphuis. Thistlethwaite 52  lépéses algoritmusa . Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. július 28..
  39. 12 silviu . Rubik 27f-ben megoldható . A Cube Forum domain (2006. április 1.). Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. augusztus 27..
  40. 1 2 Kunkle, D.; Cooperman, C. (2007). „Huszonhat mozdulat elég a Rubik-kockához” (PDF) . A szimbolikus és algebrai számításokkal foglalkozó nemzetközi szimpózium (ISSAC '07) anyaga . ACM Press. Archiválva (PDF) az eredetiből, ekkor: 2019-02-18 . Letöltve: 2013-07-17 . Elavult használt paraméter |deadlink=( súgó )
  41. Michael Reid. isten számának felső korlátja  (angol) (1992. április 29.). Hozzáférés dátuma: 2013. július 17. Az eredetiből archiválva : 2013. augusztus 24.
  42. Michael Reid. új felső határ  (angol) (1992. május 22.). Letöltve: 2013. július 19. Az eredetiből archiválva : 2013. augusztus 24..
  43. Dik T. Tél. A helyesbített számítások most megtörténtek.  (angol) (1992. május 28.). Letöltve: 2013. július 19. Az eredetiből archiválva : 2014. június 20.
  44. Ryan Heise. Az emberi Thistlethwaite algoritmus  . Hozzáférés dátuma: 2013. július 19. Az eredetiből archiválva : 2016. augusztus 2..
  45. 1 2 3 4 Herbert Kociemba. Kétfázisú algoritmus  részletei . Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. május 2..
  46. 1 2 3 4 Jaap Scherphuis. Számítógépes rejtélyes . Kociemba  algoritmusa . Letöltve: 2013. július 23. Az eredetiből archiválva : 2013. június 25.
  47. Herbert Kociemba. A H alcsoport és kosetjei  . Letöltve: 2013. július 23. Az eredetiből archiválva : 2013. május 22.
  48. 1 2 3 Herbert Kociemba. A kétfázisú algoritmus  . Hozzáférés dátuma: 2013. július 23. Az eredetiből archiválva : 2013. május 2.
  49. Bijekció a konfigurációk és a koordináták hármasai között A 2013. május 2-i archivált példány a Wayback Machine -n úgy van beállítva, hogy az első szakasz célelrendezése (vagyis a G 1 csoport bármely konfigurációja ) megfeleljen a hármasnak (0 , 0, 0).
  50. 1 2 3 Stuart Russell, Peter Norvig. Megengedhető heurisztikus függvények összeállítása // Artificial Intelligence: a modern approach = Artificial Intelligence: A Modern Approach. - 2. kiadás - M . : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .
  51. angol. minta adatbázisok . Az algoritmus szerzőjének előadásában Archív másolat 2013. május 2-án a Wayback Machine - „metszőtáblák”-on.
  52. Az elemek permutációjának paritáskorlátozása miatt a koordináták hármasainak csak a fele fordul elő.
  53. Herbert Kociemba. Metszőtáblák  . _ Hozzáférés dátuma: 2013. július 23. Az eredetiből archiválva : 2013. május 2.
  54. Herbert Kociemba. Letöltés  (angolul) . Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. május 2..
  55. Eric Dietz. Oldja meg a kockáját kevesebb, mint 25  mozdulattal . Letöltve: 2013. július 20. Az eredetiből archiválva : 2022. január 9..
  56. Michael Reid. új felső határok  (angolul) (1995. január 7.). Letöltve: 2013. július 19. Az eredetiből archiválva : 2013. augusztus 24..
  57. 1 2 Richard E. Korf. Optimális megoldások keresése a Rubik-kockára mintaadatbázisok segítségével . – 1997.
  58. Arthur Fisher . Rubik's Reduced  (angol) , Popular Science  (1997. október), 58. o.
  59. Michael Reid. Rubik-kocka oldal . Optimális Rubik-kocka megoldó (2006. október 28.) . Letöltve: 2013. július 20. Az eredetiből archiválva : 2015. július 5..
  60. Silviu Radu, A Rubik-kocka csoport új felső határa, arΧiv : math/0512485 . 
  61. silviu. Rubik 35q-ban megoldható . A Cube Forum domain (2006. március 22.). Letöltve: 2013. július 20. Az eredetiből archiválva : 2014. november 9..
  62. Az északkeleti egyetem kutatói 26 mozdulattal oldják meg a Rubik-kockát . Letöltve: 2013. július 20. Az eredetiből archiválva : 2019. október 23.
  63. Tom Rokicki, Huszonöt mozdulat elég a Rubik-kockához, arΧiv : 0803.3435 .  
  64. sziklás. Huszonhárom mozdulat elég . A Cube Fórum domainje (2008. április 29.). Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. augusztus 27..
  65. sziklás. Huszonkét mozdulat elég (nem elérhető link) . A Kocka Fórum domainje (2008. augusztus 12.). Letöltve: 2013. július 20. Az eredetiből archiválva : 2011. december 5.. 
  66. sziklás. Huszonkilenc QTM lépés elegendő . A Cube Fórum domainje (2009. június 15.). Hozzáférés időpontja: 2013. július 20. Az eredetiből archiválva : 2011. július 26.
  67. 1 2 Adam P. Goucher. Négyponttal komponált szuperflip . Complex Projective 4-Space (2015. szeptember 25.). Letöltve: 2015. október 23. Az eredetiből archiválva : 2016. február 1..
  68. 1 2 Jaap Scherphuis. Cayley Graphs . Távolságok  (angolul) . Letöltve: 2015. július 4. Az eredetiből archiválva : 2015. július 6..
  69. 1 2 Ismert távolság – 20 pozíció a félfordulat metrikában. Ismert távolság-24 vagy nagyobb pozíciók a negyedfordulós metrikában . Letöltve: 2015. július 4. Az eredetiből archiválva : 2015. június 29.
  70. Szép minták Rubik-kocka | Edge Flip, Dot | Superflip, 4 ponttal . Letöltve: 2015. július 4. Az eredetiből archiválva : 2015. július 5..
  71. Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna & Winslow, Andrew (2011), Algorithms for Solving Rubik's Cubes, arΧiv : 1106.5736v1 [cs.DS]. 
  72. Larry Hardesty. A Rubik-kocka matematikája . Egy új kutatás megállapítja az összefüggést a Rubik-kocka típusú rejtvény négyzeteinek száma és a megoldáshoz szükséges lépések maximális száma  között . MIT News Office (2011. június 29.) . Letöltve: 2013. július 23. Az eredetiből archiválva : 2013. szeptember 19..
  73. sziklás. Az üres kocka átmérője legalább 20 (lapfordulat metrika) . A Kocka Fórum domainje (2010. január 19.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  74. sziklás. Az üres kocka átmérője legalább 20 (valószínűleg 20) . Speedsolving.com (2010. január 19.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  75. Jaap Scherphuis. Rubik bosszúja  . Letöltve: 2013. július 28. Az eredetiből archiválva : 2013. július 27..
  76. 1 2 Bruce Norskog. Új felső határok: 82 csavaros fordulat, 67 blokkfordulat . A Kocka Fórum domainje (2007. augusztus 13.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. május 29.
  77. Bruce Norskog. A 4x4x4 77 egyszeletes fordulattal megoldható . A Kocka Fórum domainje (2007. július 26.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. május 29.
  78. Nagyobb rubik-kocka kötve (lefelé irányuló kapcsolat) . Euler projekt. Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. május 29. 
  79. sziklás. Alsó határok nxnxn Rubik-kockákhoz (n=20-ig) hat metrikában . A Kocka Fórum domainje (2011. július 18.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  80. CS. A 4x4x4 megoldása 57 mozdulattal (OBTM) . A Kocka Fórum domainje (2013. szeptember 30.). Letöltve: 2013. november 19. Az eredetiből archiválva : 2013. november 26..
  81. sziklás. 4x4x4 felső határok: 57 OBTM megerősítve; 56 SST és 53 BT számított. . A Kocka Fórum domainje (2015. március 3.). Letöltve: 2015. július 1. Az eredetiből archiválva : 2015. május 29.
  82. CS. 4x4x4 új felső korlát: 55 OBTM . A Kocka Fórum domainje (2015. július 3.). Letöltve: 2015. július 1. Az eredetiből archiválva : 2015. május 29.
  83. CS. 4x4x4 új felső korlát: 53 SSTM . A Kocka Fórum domainje (2015. szeptember 3.). Letöltve: 2015. július 1. Az eredetiből archiválva : 2015. május 29.
  84. Herbert Kociemba. Megaminxnak legalább 45 mozdulat kell . A Kocka Fórum domainje (2012. február 28.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  85. Herbert Kociemba. A Megaminx alsó határa htm-ben és qtm-ben . Speedsolving.com (2012. január 3.). Letöltve: 2013. július 28. Az eredetiből archiválva : 2014. november 9..
  86. Megaminx alsó határa htm-ben és qtm-ben . Letöltve: 2016. szeptember 2. Archiválva az eredetiből: 2016. szeptember 17.

Javasolt olvasmány

Linkek