Bylo nebylo, roku 1997 vznikl malý program v Basicu.

Mnoho let předtím jsem si všimnul, že Sinclair ZX Spectrum běhá rychleji, než československé SAPI-1, a nemnoho let předtím, že dostatečně taktované PC předčí rychlostí zas ZX Spectrum.

A to o tolik, že doba řešení problémů hrubou silou se z řádů tisíciletí či staletí blíží řádům dnů až měsíců.

A když přišly počítače ještě o něco rychlejší, zdálo se, že by se to mohlo změnit na hodiny až dny.

Vedle luštění hesel by se to přeci dalo použít ke skládání Rubikovy kostky.

Jako se k hashi hledá platné heslo, tak se k rozházené kostce hledá posloupnost pohybů, která ji složí.

A takový prográmek jsem si na jednom ze zástupců těch tehdy rychlejších počítačů (Am386DX-40) hezky v microsoftím QuickBasicu napsal.

Ten samotný QuickBasic stojí za zmínku.

Běžně se tehdy šířil interpret, ale my měli k dispozici i kompilátor, čehož jsem rád využíval.

Problém byl, že programy spuštěné ve vývojovém prostředí (tedy zřejmě interpretované) běhaly jinak rychle, než po skompilování – což tehdy zastavilo tvorbu trackeru pro beeper, protože se to nedalo rozumně ladit, když to po skompilování hrál jinak než během vývoje.

Stejně tak se komplexní programy mohly chovat v obou prostředích jinak – táta poměrně využívaný program pro synchronizaci souborů mezi diskem v práci a doma musel spouštět z IDE, kde běžel bezchybně, zatímco po kompilaci padal s chybou.

Naopak můj komplexní program pro kontrolu skladových zásob a export do Excelu fungoval dobře i zkompilovaný.

Naopak tátův program pro výpočty efemeridů měl trochu problém – a já zjistil, že Microsoft Quick Basic trpí stejnou zaokrouhlovací chybou, jako Sinclair Basic na ZX Spectru (a která byla na Spectru odstraněna mimo jiné v BS-ROM 140).

Teď po letech jsem na starém notebooku ten program na skládání Rubikovky našel.

Stačí nadefinovat rozhoz kostky a spustit výpočet.

Po spuštění se může nebo nemusí zobrazovat právě zkoušená poloha barev na kostce, vykreslování sice postup značně zpomaluje, ale dalo se vypnout jen před zahájením hledání, ne v jeho průběhu (ale to se dá dodělat, zdroják máme).

Jako buffer se používal soubor na disku (file1.idz a file2.idz).

Optimalizace byla jediná – program nezkoušel pohyb opačný k předchozímu (stejně by se tím jen dostal do stavu, ve kterém už byl).

V plánu ovšem bylo, že si projde, zda aktuální rozložení už v minulosti nedosáhl méně tahy – v takovém případě by aktuální větev jako neefektivní zahodil.
Ten plán se ale nerealizoval.

Dlouho jsem si myslel, že v tom programu byla chyba, ale když jsem ho teď zkoušel, nenašel jsem ji (že bych ji odstranil už tehdy?) a program mi opravdu i složil kostku.

Mám ještě kostku rozházenou od dětí, tak jsem její konfiguraci do počítače zadal, ale po šesti hodinách běhu (na 486, 50 MHz), kdy program zkoušel sedmý tah, jsem musel počítač předčasně vypnout.

Internet byl tehdy u nás v počátcích, 1996/1997 byl vlastně první rok, kdy jsme k něčemu takovému získal přístup, a abych tak řekl, „nic na něm nebylo“, rozhodně jsem na něm při svých tehdejších (ne)schopnostech hledat nenašel vhodný algoritmus pro skládání, proto byl můj program čistě jen force brutale.

Dnes by stačilo vzít Kociembův původní nebo novější postup.

Pokud je pravda, že náhodně rozházená kostka by se měla nechat složit zhruba dvaceti tahy, jak dlouho by to trvalo?

Program by šlo urychlit
1) kompilací
2) vypnutím zobrazování
3) použitím modernějšího počítače (možná s DOS Boxem).
O možnosti rozložení mezi více počítačů nebo více procesorů ani nemluvě.

Pokud se budu ale držet původní rychlosti nekompilovaného programu na 486/50 MHz, s vykreslováním, kde prozkoumat hloubku pěti tahů trvalo zhruba půl hodiny, pak by zkoušel:
6 tahů (hrubý odhad) 5 a půl hodiny,
7 tahů 60 a půl hodiny,
8 tahů 665 a půl hodiny – to už je 27 dní.
10 tahů je na 3355 dní, tedy 9 a půl roku.
(Ale 20 tahů je na 238 a půl miliardy let.)

Pokud by se tedy podařilo na moderním stroji spustit program třeba 100x rychleji, trvalo by prohledání 10 tahů jen něco přes měsíc (a 20 tahů „jen“ něco přes 2 miliardy let).

A teď si vzpomeňme, že původní úvahy o použití SAPI-1 končily i v těch jednodušších případech údajem o ticíciletích a závěrem „nerealizovatelné“.

To se opravdu nedalo odolat a program už jen z čirého bezbřehého optimismu musel prostě vzniknout!

O tom, že existuje, se můžete přesvědčit ve videu.
ZDE.

S mou kostkou, rozházenou od dětí, mi pak musela pomoci moderní technika s dvěma RISC procesory a moderní optimalizovaný algoritmus.
I u nejrozházenějších kostek lze najít řešení ve 20 tazích, a protože nejkratší řešení mé kostky bylo v 19 tazích, je vidět, že byla opravdu řácky rozházená.

Teď už je složená a já jsem rád, že jsem na řešení nemusel čekat 238 miliard let, ale jen 10 let (ano, kostka byla rozházena už někdy před 10 lety), a to přitom Kociemba pubikoval svou metodu, kterou moderní software používá, už roku 1992, tedy 5 let před vznikem mého programu!