Božské číslo Rubikovy kostky potvrzeno: Všechny kombinace lze vyřešit v 20 tazích

Vědci prokázali, že nejvyšší počet tahů nutných pro složení libovolné kombinace Rubikovy kostky je 20 (tzv. Božské číslo Rubikovy kostky). Strojový čas poskytl Google (přibližně 35 CPU-roků, Google však neprozradil, jaké počítače použil). Všech kombinací je mírně přes 43 miliard miliard. Výpočet byl založen na rozdělení možných počátečních pozic na 2,2 miliard skupin, z nichž každá čítala 20 miliard pozic.

Číslo bylo dále sníženo vyřazením duplicitních a symetricky stejných pozic, až se dostalo na 56 milionů skupin o 20 miliardách. Spočítání jedné kombinace by na běžném desktopovém počítači trvalo 20-30 sekund. Vedoucí výzkumného týmu prof. Davidson řekl, že si lidé mohou výpočet ověřit: "Stačil by na to malý superpočítač". Odkazovaná stránka cube20.org mimo jiné ukazuje, jak kostku "zamíchat", aby se docílilo počáteční kombinace, o které se jako první prokázalo, že vyžaduje k vyřešení 20 tahů. Nejvíce kombinací lze složit s minimálně 18 tahy. Informuje také BBC. Další na řadě je 4vrstvá varianta kostky...

11.8.2010 16:48 | Robert Krátký | IT novinky

Komentáře

[thingie]

„Vědci prokázali“ je příšerná fráze.

[Bedňa]

Ešte lepšie je slovo analýza.

[Robert Krátký]

„Vědci prokázali“ je příšerná fráze.

Proč?

[thingie]

Je to už zoufale zprofanovaný blábol.

[kavol]

taky jsem myslel, že v matematice se dělá "důkaz" a ne "průkaz" ...

[Robert Krátký]

Měl by to být průkazný důkaz, ne? :P

[nooneanymore]

With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves.

Takže nikoliv

Vědci prokázali, že nejvyšší počet tahů nutných pro složení libovolné kombinace Rubikovy kostky je 20 (tzv. Božské číslo Rubikovy kostky).

Onen nejvyšší počet tahů nutných pro složení libovolné kombinace Rubikovy kostky vám řeknu bez počítání na 35 CPU: ∞.

[Marek Bernát]

He? Pre každú pozíciu stačí maximálne 20 ťahov. Čiže je to najvyšší nutný počet ťahov. Čokoľvek vyššie než 20 už nie je nutnosť, ale skladateľova blbosť

[Dalibor Smolík]

No, takže jsem blbej Na 20 tahů jsem to nezvládl ..

[Marek Bernát]

V tomto prípade blbosť znamená, že nie ste Boh, alebo aspoň Google

[Jendа]

Použij na řešení počítač…

[Max]

Pravda, ve zprávičce je chyba. Mělo tam být nejméně 20 tahů. Nejvýše skutečně nekonečno :).
Zdar Max

[Max]

Ač kombinace "nejvyšší nutný" je také zajímavá. Děda to vždy říkal : Ty jsi dostal trojku? To neumíš česky? :)
Zdar Max

[Marek Bernát]

Nie, je to minimax problém (presnejšie maximin ), takže slovíčko najvyšší tam vystupovať môže. Konkrétne, cheme spočítať max (min (dist (g, e)) cez všetky prvky g Rubikovej grupy, kde e je identita a dist je nejaká vhodná metrika. Slovíčko nutný potom špecifikuje, že sa jedná o minimálnu vzdialenosť pre každý daný prípad.

[Marek Bernát]

Malá drobnosť. To min je tam zbytočne a realizuje ho už tá metrika dist, takže tam stačí max(dist(g,e)). Alternatívne (aby bolo vidieť, že je to skutočne minimax) by sa to dalo zapísať max ( min (|P|)), kde to maximum je opäť cez prvky g Rubikovej grupy, minimum je cez všetky cesty P medzi g a e (v grafe, kde vrcholy sú prvky grupy a hrany budú elementárne operácie) a |.| je počet hrán cesty. Z toho dostaneme tú metriku dist(g, e) = min(|P|).

[thingie]

Myslím, že nejvyšší nutný počet tahů (kde to nutný právě přesně znamená, že jdeme po nejkratší cestě k cíli a nekroutíme si tím jako vzteklí) je celkem jasné, a znamená to přesně to, co znamená. Co na tom prosímvás chcete překroutit?

[Max]

Je jasné, že jsem se unáhlil a proto jsem se i opravil, tudíž nechápu váš komentík ...
Zdar Max

[nooneanymore]

Jasně. Ale co pak znamená nejnižší nutný počet? Já bych napsal, že k řešení je nutných přesně 20 tahů, protože s 19 už to nejde a 21 jich není nutných. Takže s tím nekonečnem jsem neměl pravdu, ale zprávička je přece jenom chybná.

[Marek Bernát]

Najnižší nutný počet je 0 a realizuje sa v pozícii, kde je už kocka poskladaná Takže 20 ťahov zjavne vždy nutných nie je. Je to len _maximálny_ počet nutných ťahov, tj. počet nutných ťahov v najhorších možných pozíciách.

[nooneanymore]

Nebo ještě jinak? Ještě tam je napsáno "libovolné", takže je to číslo, které platí pro všechny kombinace, nikoliv pro některé. Je nutné disponovat minimálně 20 tahy (20 je nutno míti), abych mohl vytvořit jakoukoliv kombinaci. To, že mi občas stačí 1 tah není obecné pravidlo.

Já bych řekl, že zacházím spíš do jazykových problémů, než matematických... Já bych jednoduše napsal, že jakékoliv kombinace lze dosáhnout ne více než 20 tahy, jak je tomu v originálním textu. Vyhnul bych se tak slovu "nutné".

[Marek Bernát]

Ježiš, čo sa tu furt snažíš prekrucovať? Tá veta je jazykovo aj matematicky absolútne v poriadku. Že je 20 ťahov maximálnych nutných pre ľubovoľnú pozíciu znamená, že pre ľubovoľnú pozíciu je počet nutných ťahov menší rovný 20. Je ti aspoň toto zrejmé? Ak áno, tak skús pochopiť, že tvrdenie v správičke je tomuto ekvivalentné.

[nooneanymore]

Omlouvám se, že mi nedošlo hned, co chtěl básník říci. Navíc to, jak já uvažoval, asi je pro leckoho nepochopitelné. Já uvažoval tímto stylem:

Mám množinu výchozích kombinací a množinu konečných kombinací. Jediným zobrazením, kterým lze jednu množinu převést v druhou (iso- nebo homomorfně, toť záleží na tom, co je množina konečných kombinací), je to, které se skládá z 20 a více tahů, přičemž tahy, které jsou navíc, jsou zbytečné. Už si rozumíme?

Takže pro příště, až někdo bude přepisovat zprávičku z podobného oboru, ať se drží originálu, nebo ať vysvětlí dostatečně, co tím myslel, aby to pochopil kdekdo, třeba i ti, kteří netrpí předsudky nebo selským rozumem.

Jinak samozřejmě souhlasím, že tak, jak vy to vysvětlujete, to asi autor asi doopravdy myslel.

[Marek Bernát]

Tak to si nerozumieme. Jednak nechápem ako s čímkoľvek súvisí pojem "množina konečných kombinácií", lebo tá množina je zjavne vždycky jednoprvková (konečná kombinácia je poskladaná kocka) a teda nezaujímavá. Ďalej nechápem, kde by sa tu vzal nejaký homomorfizmus (jediné grupy široko ďaleko sú tu podgrupy Rubikovej kocky a homomorfizmy medzi nimi s riešením nesúvisia. Aspoň nie takto naivne).

Tá správička je napísaná dostatočne jasne a pochopil ju každý okrem teba (s výnimkou Maxa, ale aj ten potom uznal svoju chybu).

Ale toto predsa nie je o interpretácii. Súhlasím, že nie vždy je ľudský jazyk exaktný, ale v tomto prípade je tá veta jedna k jednej mapovateľná na matematické tvrdenie. Inak sa to proste pochopiť nedá. Ak si to pochopil inak, tak je problém v tebe a radšej sa skús nad problémom aspoň chvíľu zamyslieť, než niekoľkokrát písať, že v správičke je chyba (pritom pokaždé z iného dôvodu, takže zjavne ani sám nevieš o čom hovoríš...).

[nooneanymore]

Připouštím, že mi dlouho trvalo, než jsem svoji námitku zformuloval dostatečně přesně, abych nemusel pokaždé její části obměňovat a měl jsem publikovat až svoji závěrečnou myšlenku, ale věřte, že svoji argumentaci nepřizpůsobuji okolnostem.

Mimo jiné, když se bavíme o homomorfizmu, nemusíme mluvit jenom o grupách. Dále pak, je otázka, co znamená řešení. Můžeme říci, že řešením nemusí být jenom "každá stěna jednobarevná", nýbrž rovněž např. "na diagonále stejné barvy a všude jinde jiná jednotná barva". Pak máme řešení více.

Samozřejmě tohle všechno nebylo možné ve zprávě zodpovědět, ale to nic nemění na faktu, že ji pak lze vykládat různě. Mě šlo o to, že tak, jak je informace podána, je možné ji interpretovat více způsoby. Asi tedy jak kým. A že originál je přesnější a nedává mi prostor k jiným úvahám. Zprávička je srozumitelná pro každého kromě mě a jiné, kdo by se rádi šťourali v podrobnostech. Toť vše.

[Marek Bernát]

Mne ale stále nie je jasné, v čom tá záverečná myšlienka spočíva a či vôbec nejaká je.

No, to pochopiteľne, ale keď nepovieš, o ktorom homomorfizme sa bavíš, tak tvoje tvrdenie nemá žiadny zmysel. Ja som vybral tú najrozumnejšiu interpretáciu, lebo s grupami táto téma bezprostredne súvisí. Ešte si mohol mať na mysli homomorfizmy grafov, ale ani v tom prípade mi nie je jasné, o čom hovoríš.

Pochopiteľne, že niektoré veci boli v tom článku implicitne. To platí dokonca aj o extrémne formálnych matematických článkoch (inak by boli 10x dlhšie...). Čo je "riešením Rubikovej kocky" je jasné každému obyvateľovi tejto planéty a že sa to snažíš prekrútiť na úplne iný problém vypovedá niečo o tebe, nie o správičke

No, v správičke nie je ani formáľna definícia Rubikovej kocky, dokonca ani len počet jej stien. Je kvôli tomu chybná a necháva priestor na interpretáciu? Človeku so zdravým rozumom opäť nie. Tebe neviem

[Jendа]

k řešení je nutných přesně 20 tahů

Ne, špatně. Existují i rozestavení, kde stačí 19, 18, 17… tahů.

[nooneanymore]

Ano, to, že můj první i druhý výrok jsou špatně, připouštím. Protože jsem původní zprávu chápal blbě. Viz jiný můj příspěvek o úroveň výše.

[Jendа]

Ano, nechtěl jsem duplikovat příspěvek Marka Bernáta, ale otevřel jsem si hodně tabů a dostal jsem se k tomu až později, takže jsem neviděl, že už to napsal.

[thingie]

Takže máš protipříklad rozestavení kostky u kterého lze jasně ukázat, že ho nelze vyřešit 20 tahy? Přesněji, máš protipříklad rozestavení rubikovy kostky, který se nedá řešit vůbec, jak se tím nekonečnem snažíš ukázat?

[phr]

Jo, stačí odlepit a přehodit polep na 2 sousedících různobarevných polích u složené kostky. Pak to nesloží ani Gúúúúúgl "-)

[Heron]

To ale není validní rozestavení kostky .

[phr]

To je pravda.

[Valerius]

To je dobrý, to bych mohl někomu provést

[radek]

já to tak vždy skládal, občas se našli nějaký 4 mrchy, které byli, tam kde neměli být... :D

[Tomáš]

Ale pak je to většinou vidět, ta polepka nebude držet jako nová. U trochu vyviklaných kostek se dá otočit jeden roh a výsledek je stejný.

[Robert Krátký]

Onen nejvyšší počet tahů nutných pro složení libovolné kombinace Rubikovy kostky vám řeknu bez počítání na 35 CPU: ∞.

To by nebyl počet nutných, ale možných tahů.

[Rivon]

Nemohl byste někdo sepsat tu pozici do algoritmu? Jaksi mi nefunguje Java v žádným prohlížeči. :)

[jehovista]

Kterou pozici? Tech resitelnych nejmene dvaceti tahy je hromada. Jestli ti jde jen o jednu z nich, tak dej do youtube "rubik superflip"

[Leinad]

Zajímavé. Tak to vypadá, že Hlubina myšlení se sekl o 22...

[Dan Ohnesorg]

Palec nahoru tomuto komentari

[xxxs]

mozno mal inu kocku.

[Xerces]

Jako macku?

[Robert Krátký]

Co si dáte?
Whisky.
Skotskou?
Nie, bez kocky.

[Bedňa]

[Filip Jirsák]

Ještě nevíte, kolik to vyjde pro tu čtyřvrstvou.

[tsLnox]

+∞ :-P

[tsLnox]

Ach proč já jsem tak blbej. Samozřejmě +42

[Sten]

V tom případě se použila špatná kostka :)

[Brokarna]

Všech kombinací je mírně přes 43 miliard miliard.

To mi připomnělo tohle

[Marek Bernát]

To je asi moja najobľúbenejšia scéna v sitcomoch vôbec.

[jehovista]

Jestli je tohle nejlepsi vtip z IT Crowd, tak uz vubec nelituju, ze ten serial ignoruju.

[frEon]

coz vypada jako min prace, nez ji rozlozit a pak z malych kousku znovu poskladat tak, jak patri (to je asi jediny reseni, na ktery mam trpelivost)

[pc2005]

Doufám, že si ty pozice s 20 někam uložili. Až je budou chtít optimalizovat třeba na 19, tak ať nemusej počítat znova .

[thingie]

Obávám se, že tohle je definitivní výsledek.

[pc2005]

We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate.

Jo ale nevěděj kolik je přesně kterejch.

[Marek Bernát]

Že existujú pozície, na ktoré je treba aspoň 20 ťahov sa už vie 15 rokov. Ale že 20 skutočne stačí vždy, to je podstata tejto správičky

[EFi Yunah]

tu funguje teoria relativity krasne: "Uz 15 rokov sa vie, ze existuju pozicie na ktore treba aspon 20 tahov" ... Po 35 rokoch vypoctoveho casu sa ukazalo, ze 20 tahov staci vzdy... ;)

[Marek Bernát]