neprihlásený Streda, 22. septembra 2021, dnes má meniny Móric
Rubikova kocka vždy vyriešiteľná na 20 ťahov, dokázali výpočtom na serveroch Google

DSL.sk, 12.8.2010


Známy hlavolam Rubikova kocka je vždy možné vyriešiť na maximálne dvadsať ťahov. Dokázala to štvorica Morley Davidson, John Dethridge, Herbert Kociemba a Tomas Rokicki počítačovým preverením všetkých možností.

Že je Rubikovu kocku možné vyriešiť na najviac dvadsať ťahov sa doteraz predpokladalo, nebolo to ale dokázané. Od roku 1995 zároveň bolo dokázané, že niektoré pozície je možné vyriešiť práve na dvadsať ťahov a nie je ich možné vyriešiť na menej ťahov.

Keďže celkový počet rozličných počiatočných pozícií Rubikovej kocky je až viac ako 4.3 x 10 ^ 19, dôkaz štvorice Davidson, Dethridge, Kociemba a Rokicki využíva náročný matematický aparát a rozdeľuje všetky možné začiatočné pozície na veľké skupiny pozícií preverovateľné naraz.

Tím najskôr redukoval všetky pozície do 2.2 miliardy rozličných skupín pozícií, v každej sa nachádzalo 19.5 miliardy rozličných jednotlivých pozícií. Eliminovaním skupín pre symetriu bol znížený počet skupín, ktoré bolo potrebné riešiť, na 55.9 milióna.

Vyvinutý algoritmus následne hľadal pre všetky pozície z jednej skupiny riešenie na maximálne dvadsať ťahov spoločne, na 2.8 GHz štvorjadrovom procesore od Intelu s jadrom Nehalem to pre jednu skupinu trvalo približne 20 sekúnd. Celkovo na overenie všetkých skupín a teda všetkých začiatočných pozícií bolo potrebných 35 rokov výpočtov na jednom takomto procesore.

Výpočty ale uskutočnila na svojich serveroch spoločnosť Google, trvalo jej to niekoľko týždňov. Koľko serverov a v akej konfigurácii použila autori dôkazu neuviedli.

Od augusta 2008 bolo známe, že Rubikovu kocku je možné vždy vyriešiť určite na maximálne 22 ťahov. Počítačový dôkaz vtedy uskutočnili Tomas Rokicki spolu s Johnom Welbornom.

Tím autorov informuje o novom dôkaze vyriešenia vždy na maximálne dvadsať ťahov na cube20.org.


      Zdieľaj na Twitteri



Najnovšie články:

FBI týždne obetiam ransomvéru neposkytla dešifrovací kľúč
Operátor avizuje pokrytie celej Trnavy gigabitovou optikou
Litovské ministerstvo odporúča občanom nekupovať čínske telefóny
Smartfóny v EÚ majú mať rovnaký nabíjací port, legislatíva príde tento týždeň
Google si kupuje za 2.1 miliardy budovu na Manhattane
Ubuntu predlžuje podporu LTS verzií na 10 rokov
Vydaná nová verzia univerzálnej znakovej sady Unicode
USA zvažujú sankcie aj pre Honor
Linux oslávil 30 rokov
Intel uvedie aj 16-jadrový 35-Wattový hybridný CPU pre desktopy


Diskusia:
                               
 

myslim ze mi to nezlahsi zivot. Niektori ludia sa asi dost nudia ked riesia taketo kraviny...
Odpovedať Známka: -3.7 Hodnotiť:
 

asi tiez nemas co robit ked to citas a komentujes ze? keby si napisal nieco k veci....
Odpovedať Známka: 7.0 Hodnotiť:
 

==> jugi
--------
x86 procesor bol povodne zamerany ako hrackarsky
(toy processor)

a dneska tu mame desiatky GIGAFLOPS (!) na socket..
napr kalkulacka ma cca 5-10 FLOPS...
Odpovedať Hodnotiť:
 

* 8086 cpu

Odpovedať Hodnotiť:
 

radsej by si bol, keby ti niekto zakazoval riesit veci, ktore ta zaujimaju?

je lepsie, ked je system (spolocnost) funkcny s najmensim moznym riadenim. a nikdy nevies, co sa moze hodit.

preto sa nikdy nepytaj, naco niekto stavia domy z karat. mozno ich stavia pre teba.

Odpovedať Známka: 6.8 Hodnotiť:
 

Nj a vdaka takymto "kravinam" sme dnes tam kde sme... Pretoze sa skupinka vedcov zapodieva matematikou, hlbsiou kombinatorikou a podobne nie? Mali by sme zrusit aj fyziku, chemiu, ved naco nam je nieco ako dokazovanie Higginsa? Kaslat na to a podme pestovat zemaky... Cim viac ich bude tym viac ludi sa naje..
Odpovedať Známka: 6.9 Hodnotiť:
 

Co sa tyka rubikovej kocky, tak skupinka vedcou sa zaobera konkretnym problemom. Dovolim si povedat, ze uzitok z jeho vyriesenia nie je ziadny. Narozdiel od spominaneho LHC a objavovania Higgsovho bozonu. A aj pre mna je tento pokus uplne zbytocny a financie, cas a vedecke kapacity sa mohli investovat uplne inde..
Odpovedať Známka: 0.3 Hodnotiť:
 

Myslím si, že CERN bude celkom dosť zbytočná investícia...
Odpovedať Známka: -7.3 Hodnotiť:
 

Asi ti nic nehovori slovo "optimalizacia"
Odpovedať Známka: 7.3 Hodnotiť:
 

Kombinatorika na 3x3x3 obale kocky podla mna bude mat aj ine vyuzite ako len vesledok maximalneho riesenia r. kocky... Mozno nie konkretne ale vdaka procesu ako grupovali rozdne rozlozenia a analyzovali dany problem - sa v buducnost dany proces pouzije, mozno trochu upraveny, zas. Chapes? To je ako teoria grafov, v istom zmysle.. Je mi nahovno vediet ci ma 5 uzlovy hraf eulerovu liniu .. ale pokial to viem zisit, tak to mozem aplikovat aj na realny zivot..
Odpovedať Známka: 7.8 Hodnotiť:
 

Dobre a to, ze sa da kocka vyriesit na 20 tahov a dokonca vies ako to spravit chces aplikovat na realny zivot ako?
Odpovedať Známka: -3.3 Hodnotiť:
 

ty si pelo...nejde o konkretny vysledok...IDE O POSTUP... cize to ze sa rubikovak da zloit na 20 je ti nahovno, ale ze sa vyvinul postup ktori sa da aplikovat aj inde ti uz na daco moze byt... napr by sa podla toho dali optimalizovat nejake vyrobne postupy....
Odpovedať Známka: 5.7 Hodnotiť:
 

Pre boha ani o postup nejde, takych postupov tu uz bolo a tento urcite nebude nejaky novy a revolucny. Ale schvalne toto by som sa autorov na to spytal..
Odpovedať Známka: -1.4 Hodnotiť:
 

Prečo by mal byť úžitok len z vyriešenia? Optimalizovať tak zložitý výpočet má určite zmysel a taktiež ako otestovanie systému záťažou je to celkom dobré.
Odpovedať Známka: 7.3 Hodnotiť:
 

higgins bol tusim magnumov partak.

higgsa?


Odpovedať Známka: 10.0 Hodnotiť:
 

No jo, a ten pokrok ide stale dopredu a mame stale veci ktore nas pomaly viac a viac nicia. Kvalita zivota existovala mozno tak v jaskyni.
Odpovedať Známka: -3.3 Hodnotiť:
 

Keď si taký múdry tak skús vymyslieť alebo vynájsť niečo ty...."mudrlant"...A zrušiť matematiku? Veď s matematikou sa v živote stretávaš každý deň ani si to možno neuvedomuješ. Taktiež chémiu a fyziku! Ale ty si choď radšej pestovať tie zemiaky, aby si mal čo dať na tanier svojím deťom a možno tým zachrániš aj celý svet.
Odpovedať Hodnotiť:
 

Nie kazdy moze riesit skutocne problemy, treba riesit aj hluposti, ved za daco titul ziskat treba. Keby kazdy robil iba uzitocn veci tak tu nieje ani stvrtina profesorov a doncentov a teda by nemal kto ucit na vysokej ;-)
Odpovedať Známka: -7.4 Hodnotiť:
 

A Teba by tiez nemal kto naucit pisat a citat.
Odpovedať Známka: 6.9 Hodnotiť:
 

Mal by si vediet, ze pohlad BFU ako si ty na 99,9% niektorej dnesnej prirodnej vedy u laickeho neznaleho BFU priamo evekuje myslienky: blbosti, sprostosti, zbytocnosti, naco to je, ziadny prinos pre prax, hracky ...

A ludia ktori su len nepartne nad rovinou poznania a preto ze su troska vyssie nad rovinou, vidia trocha viac do dialky a sirku celej vedy. Kedze su aj vyssie, vidla trocha viac do hlôbky, ale iba nad svojim miestom. Tak tito ludia tazko prehltaju, ked maju citat komentare typu naco to je.
Odpovedať Známka: 8.3 Hodnotiť:
 

Bud laskyplny a pochop: 99,999 999 % populacie to nie je na nic. Je extremne velka pravdepodobnost ze nahodne vybranemu jednotlivcovi druhu homo sapiens to na nieco bude. Ale druhu homo sapiens ako celku to na nieco je. Tak je to so vsetkymi znalostami a vedomostami vo vsetkych vedach. Tebe je na hovno Boolova algebra, komplexne cila, infinitezimalny pocet, tenzorovy pocet, algebra cili napr. teoria grup, uzasna tolopogicka disciplina ako teoria grafov, teoria optimalizacie ... a tucty dalsich oblasti napr. matiky ci dalsich interdisciplinarnych oblasti. Pochop, ze tebe su na velke H. Ale ludstvu v priebehu jeho historie a vyvoja na nieco su/budu, pretoze bez vsetkych vedeckych znalosti by neexistoval dnesny svet.
Odpovedať Známka: 6.9 Hodnotiť:
 

"pretoze bez vsetkych vedeckych znalosti by neexistoval dnesny svet. "

...a mohol ten svet byt sto krat lepsi ...

Odpovedať Hodnotiť:
 

Dost urychlilo sj to ze nehladali najmensi pocet tahov ale stacilo im 20
Odpovedať Známka: -6.4 Hodnotiť:
 

Oni hľadali pre každé možné rozloženie kociek najmenší počet ťahov (keby si si pozrel tú odkazovanú stránku, tak by si na to určite prišiel, pretože tam je pekná tabuľka).
Odpovedať Známka: 8.2 Hodnotiť:
 

najmensi pocet tahov zavysi od vychodzej pozicie..neviem co by si chcel hladat
Odpovedať Známka: -5.0 Hodnotiť:
 

"Rubikovu kocku je vždy možné vyriešiť na maximálne dvadsať ťahov" .. podla mna je rubikovu kocku mozne riesit maximalne na nekonecne vela tahov .. skor je ju mozne riesit MINIMALNE na 20 tahov .. bud nefunguje translator alebo ja
Odpovedať Známka: -6.9 Hodnotiť:
 

Nie, zle to chápeš. Oni dokázali, že každé rozloženie rubikovej kocky možno vyriešiť na 20 ťahov, alebo menej. Teda na maximálne 20 ťahov.
Odpovedať Známka: 9.3 Hodnotiť:
 

teda :
MAX 20, NIEKTORE tahy aj menej
Odpovedať Hodnotiť:
 

to sa niekomu spustaju applikacie na takej architekture ako ma google, predpokladam ze do hodiny to bolo hotove.
Odpovedať Známka: -10.0 Hodnotiť:
 

ale ved tieto moznosti ma kazdy ak ma dost penazi. GWT, EC2 a ine cloudove riesenia. kupit na ec2 20x 33CPU instance a do mesiaca to mas.
Odpovedať Známka: 2.0 Hodnotiť:
 

Alebo si za par centov kupit rubikovu kocku a pisat kombinacie na papier :-p to mas este lacnejsie.
Odpovedať Známka: 8.6 Hodnotiť:
 

lacnejsie? nemyslim ked si to preratas do man-hours (ved ucty platit treba). tak zas az o tolko lacnejsie to nebude. pri 20 instances mas dokopy 760 jadier (/4 167.5 "strojov" ktorym to osamote trva 35 rokov). doba sa pak skrati na 76.25 dna. hodina behu vsetkych instances dokopy je 32 dolarov. takze by ta to stalo cca 60000 eur ;).
Odpovedať Známka: -7.8 Hodnotiť:
 

keby si nepredpokladal, ale cital tak: "Výpočty ale uskutočnila na svojich serveroch spoločnosť Google, trvalo jej to niekoľko týždňov."
Odpovedať Hodnotiť:
 

Ja smo postavil a naprogramoval robota, ktorý používa algoritmus od jedného z autorov :)
Po naskenovaní kocky sa za niekoľko stotín nájde riešenie na menej ako 23ťahov :)

http://www.youtube.com/watch?v=kMg7vnmOARI
Odpovedať Známka: 8.9 Hodnotiť:
 

uau to je super
Odpovedať Známka: 8.9 Hodnotiť:
 

Pekné. Kontaktujte nás prosím na redakcia at dsl.sk.
Odpovedať Známka: 8.6 Hodnotiť:
 

zeby nadejny novy spolupracovnik?
Odpovedať Známka: 10.0 Hodnotiť:
 

Možno s ním spravia intervjú :-]
Odpovedať Známka: 10.0 Hodnotiť:
 

Tak to klobúk dole.
Odpovedať Známka: 8.8 Hodnotiť:
 

ja som si stavial z legadomceky, ale toto je tiez dobre
Odpovedať Známka: 6.5 Hodnotiť:
 

"smekám obdivem, klobouk dolů", pouvazuj ale nad iny miestom, kde budes svojho robota spominat, lebo...
Odpovedať Známka: 6.7 Hodnotiť:
 

Ak si to naozaj ty, tak respect !!

A naozaj sprav s DSL rozhovor/reportaz ako navrh a stavba prebiehala, atd... Pripadne ake ine riesenia na NXT uz si realizoval/budes realizovat...

S uctou,
Muvo
Odpovedať Známka: 6.0 Hodnotiť:
 

Tak toto je haluz, ako jednoducho vyzerajuca hracka nejakeho sikovneho vynalecu zatazi tak brotalne vela serverov :)
Odpovedať Známka: 10.0 Hodnotiť:
 

... klobuk dole sefe ... u mna si big boss ...
Odpovedať Známka: 6.7 Hodnotiť:
 

Ta moja žena sa poteší, keď jej to zvestujem
Odpovedať Známka: 8.3 Hodnotiť:
 

juchu, budu rozky lacnejsie
Odpovedať Známka: -5.7 Hodnotiť:
 

nebudu ide hore cena obilia
Odpovedať Známka: 9.2 Hodnotiť:
 

Co na jednom 4-core PC trva 35-rokov, tak google cluster spravi za par tyzdnov... To uz je dost velky rozdiel zaujimavy aj pre sifrovanie ci lamanie hesiel...
Odpovedať Hodnotiť:
 

to co googlu trva tyzdna, inym bude trvat roky :)
Odpovedať Známka: 6.0 Hodnotiť:
 

Tak ak mas 50+ miestne heslo :)
Tak to ani samotny Google nezvladne, ak nema stastie..
Odpovedať Hodnotiť:
 

35rokov to je pre absolutne vsetky kombinacie...tuto to borci nejak zostihlili...ale ja tak klobuk dolu
Odpovedať Hodnotiť:
 

How We Did It
How did we solve all 43,252,003,274,489,856,000 positions of the Cube?

* We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
* We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
* We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
* We wrote a program that solved a single set in about 20 seconds.
* We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

Odpovedať Známka: 3.3 Hodnotiť:
 

Ja by som sa asi zasekol, keby som to hádzal do kalkulačky.
Odpovedať Hodnotiť:
 

tak mne trvalo mesiac, kym som dokazal poskladat kocku a odvtedy ju poskladam do minuty, ale este nikdy mi nenapadlo ratat kolko tahov, ale tych 20 sa da zvladnut...
Odpovedať Známka: 2.0 Hodnotiť:
 

U rubika sme asi dokoncili badanie, nakolko boli overene vsetky kombinacie a u vsetkych bolo preskumane, kolko tahov je min. potrebnych na poskladanie istych konfuguracii kocky. Max. je 20, kedze existuje cca 300 tisic konfiguracii kocky, ktore sa nedaju poskladat 19timi tahmi, treba 20 tahov (a to bolo dokazane davnejsie), ako hovori tabulecka na konci spominaneho clanku.
Odpovedať Známka: 6.0 Hodnotiť:
 

aha, 300 milionov, ruka pise skor jak mozog premysli
Odpovedať Známka: 10.0 Hodnotiť:
 

Trocha ma zaujal typ dokazu. Ziadna highest matika typu ako v dokaze P <> NP ci Velkej Fermatovaj vete, to by na PC slo asi tazko. Jednoducho brutal force skumanie vsetkych moznosti. Technika samozrejme pomohla a skumanie vsetkych moznosti nebolo nahodne ci nesystematicke, ale vysoko organizovane a roztriedene do skupin kombinacii podla istych znakov. Podone bezal aj dokaz vety o styroch farbach z teorie grafov v 70tych rokoch 20. storocia.

Zaujimalo by ma ci raz bude vseobecny dokaz na baze high-math, bez preskumania jedinej moznosti, najvyssia abstrakcia vyuzivajuca topologiu ci teoriu grup.
Odpovedať Známka: 5.0 Hodnotiť:
 

ziadna vysoka kombinatorika.
obycajny brute force.

lajdaci.
Odpovedať Známka: 5.0 Hodnotiť:
 

mojenko keby si si precital clanok zdroja (aj ja keby som si ho precital podrobne), tak by si zitil:

- na roztriedenie vsetkych moznosti do cca 2,2 miliardy zakladnych tried a v kazdej 19,5 miliardy jednotlivych konkretnych moznosti, je treba skur**** pardon, neslusne vela kombinatoriky
- co som si aj ja mohol svimnut skor, na analyzu kazdej tejto triedy moznosti sa uz pouzivala algebra (konktretne teoria grup)
Odpovedať Známka: 3.3 Hodnotiť:
 

teoria grup mozno, ale ziadna tazsia kombinatorika.
chapes. nie? :)
Odpovedať Hodnotiť:
 

Spomina sa tu 20 ťahov, ale čo to je jeden ťah? Ľubovoľné otočenie v jednom smere alebo o 90 stupňov alebo inak?
Odpovedať Hodnotiť:
 

Lubovolne otocenie v jednom istom smere oznacme ho "+", jednou stenou (pozostavajucou z 9tich vrchnych kociek) o 90 ci 180 stupnov. 270 stupnov nema zmysel uvazovat, nakolko otocenie o 270 stupnov v smere "+" je to iste ako otocenie o 90 stupnov v smere "-".
Odpovedať Hodnotiť:
 

No a samozrejme otocenie o 360 st. v ktoromkolvek z dvoch smerov je zobrazenie zvane "identita".
Odpovedať Hodnotiť:
 

No ide len o to, či to nemal len tak na jedno jediné, prípadne niekoľko rozložení naprogramované. Vtedy netreba ani procesor, stačí malá pameť, napr. EEPROM a binárny čítač adries a prakticky je to v hrubých rysoch. Neuvažujme o snímaní a PCčku, takýmito čačkami-mačkami dokážu študenti stredných škôl bežne ohlupovať a oblbovať poroty na SOČkách každý rok...
Odpovedať Hodnotiť:
 

Nech mi dajú adresu, pošlem im fotky svojej ktorú som asi pred 8 rokmi tak domotal že to každý pri pohľade na ňu vzdá :-P Nech mi potom pošlú návod jak ju dať dokopy na 20 ťahov, budem im strašne vďačný :-P
Odpovedať Hodnotiť:
 

postavit jednu farbu na rubikovej kocke dokaze aj male decko.
tazsie je postavit ju tak aby bolo cele prve poschodie kocky bolo zlozene ( to znamena aby aj farby na bokoch poschodia sedeli s farbou prostredneho policka na danej stene ), ale tiez sa to da logicky.
na druhe a tretie poschodie su potom algoritmy - pomocou nich sa da prehadzovat policka bez toho aby si si to prve poschodie rozdrbal
Odpovedať Hodnotiť:
 

Asi ju pošlem tebe :-D
Odpovedať Hodnotiť:
 

od 2008 existuje na iPhone applikacia ktora, tiez vyriesi rubikovu kocku do 20 tahov.. tak neviem aky "novy" algoritmus v google teda vymysleli.

iphonom si pekne vyfotim vsetky strany kocky... a obratom mi do tych 20 ukazuje na displeji ako mam s kockou tocit....

http://www.youtube.com/watch?v=HNwx0nbgm7M
Odpovedať Známka: 0.0 Hodnotiť:
 

ach jaj, inteligent, oni asi že vyskúšali všetky kombinácie, aké môžu existovať a vyskúšať toľko možností by ti nezvládol ani počítač za niekoľko rokov, algoritmus vymysleli na to, aby skúšalo viac možností rýchlejšie po skupinách
Odpovedať Hodnotiť:
 

ano na 20 tahov ale zabudli sa pochvalit ze su to vzdy ine tahy hihi a keby ich mal mat clovek vsetky tie tahy v hlave tak skolabuje pri prevej desatine (skor miliontinke)tych tahov...Overene vzorce pomocou kocku skladaju experti to je uz ine....no a ja mam takzvane kroky a kocku vyriesim vzdy pomocou 7 krokov.
Odpovedať Hodnotiť:
 

sory malo byt:
Overene vzorce pomocou ktorych kocku....
Odpovedať Hodnotiť:

Pridať komentár