neprihlásený Piatok, 6. decembra 2024, dnes má meniny Mikuláš
Zadanie Sudoku musí mať aspoň 17 číslic, dokázali vedci počítačovým dôkazom

DSL.sk, 9.1.2012


Tím vedený írskym matematikom Gary McGuireom dokázal, že každé jednoznačne vyriešiteľné zadanie hry Sudoku musí mať aspoň 17 vyplnených číslic a neexistuje žiadne zadanie so 16 číslicami.

Informuje o tom Nature, detaily je možné nájsť v článku (PDF) McGuirea.

Vedci sa pokúšali v minulosti dokázať minimálny počet číslic v zadaní čisto matematickým dôkazom. Kkeďže takýto dôkaz zatiaľ nebol objavený, McGuire odštartoval vývoj počítačového dôkazu. Softvér realizujúci tento dôkaz v konečnom dôsledku preveril všetky jednoznačné zadania pre všetky možné výsledné vyplnené hracie polia Sudoku.

Úplne všetkých rozličných vyplnených polí Sudoku je až 6.7 * 10 ^ 21, z pohľadu zadaní a riešení je medzi nimi ale množstvo permutácií a tento počet je tak možné zredukovať na 5.5 miliardy rozličných vyriešených Sudoku. McGuire našiel a reprezentoval všetky možné výsledné polia pomocou softvéru od Glenna Fowlera z AT&T Labs, v nekomprimovanej podobe mali 418 GB a v komprimovanej pod 6 GB.

Softvér hľadávajúci 16-číslicové zadania následne pre každé možné kompletné pole našiel čo najviac skupín políčok takých, že minimálne jedno políčko z každej skupiny musí byť pre jednoznačnosť určite v zadaní. Príklad takejto skupiny je zobrazený na ilustračnom obrázku, v prípade ak by sa v zadaní nenachádzala žiadna z červených číslic, zadanie by malo minimálne dve riešenia s možnosťou vymeniť červené 5 a 9.


Ukážka skupiny číslic, z ktorých pre jednoznačnosť aspoň jedna musí byť v zadaní (obrázok: Gary McGuire)



Algoritmus následne pre nájdené skupiny riešil problém minimálneho výberu reprezentatov pre tieto skupiny, teda hľadal minimálnu množinu číslic v zadaní takú, aby sa v nej vždy nachádzala aspoň jedna číslica z každej skupiny.

Pre všetky možné výsledné polia Sudoku softvér podľa autorov potvrdil, že každé jednoznačené zadanie musí mať aspoň 17 číslic.

Dokazovací softvér vyžadoval veľké množstvo výpočtového výkonu a po jeho návrhu ho autori testovali na viacerých superpočítačoch. Nakoniec ho spustili na klasteri Stokes v Irish Centre for High-End Computing, ktorý pozostáva z 320 výpočtových uzlov s dvomi šesťjadrovými Xeon E5650 procesormi.

Dokazovací softvér bežal rozdelený na viacero úloh od januára do decembra 2011.


      Zdieľaj na Twitteri



Najnovšie články:

Linuxové jadro 6.12 označené za LTS, piatim LTS verziám skončí podpora naraz
NASA opäť posunula termín pristátia posádky na Mesiaci
Chrome na Androide za menej ako dva roky zdvojnásobil výkon
Vydaný minimalistický Alpine Linux 3.21
Microsoft nezmierni HW požiadavky pre Windows 11, bude stále vyžadovať TPM 2.0
V Španielsku navrhujú smartfóny nedávať deťom a dať na ne upozornenia na zdravotné riziká
Bitcoin dosiahol novú rekordnú cenu nad 100-tisíc dolárov
Novým šéfom NASA bude vesmírny turista cestujúci so SpaceX
Amazon predstavil nový akcelerátor AI pre trénovanie neurónových sietí
Telekom má nakoniec 100 GB balík pre všetkých zákazníkov predplatených kariet dlhšie


Diskusia:
                               
 

Takze ked bude v casaku sudoku so 16 predvyplnenymi polickami a budu tvrdit ze existuje jednoznacne riesenie, mozem ich zazalovat. Pretoze to je to iste, ako keby tvrdili, ze akukolvek mapu (t.j. s akymikolvek tvarmi a hranicami statov ) v euklidovkej rovine mozno vzdy vyfarbit 3 farbami, co nejde, kedze minimum su 4 farby (tiez dokazane na pocitacoch uz pred 30 rokmi).
Odpovedať Známka: 7.6 Hodnotiť:
 

(mysli sa tak, aby ziadne dva susedne staty nemali rovnaku farbu)
Odpovedať Známka: 6.0 Hodnotiť:
 

staty ale musia mat spojite uzemie...nezabudat! :)
Odpovedať Známka: 5.0 Hodnotiť:
 

A dokaz na farbenie grafu v euklidovksej rovine je dokazatelne aj matematickym dokazom, nie len na pocitacoch...
Odpovedať Známka: 6.7 Hodnotiť:
 

Staci si nastudovat teoriu grafov :)
Odpovedať Známka: 3.3 Hodnotiť:
 

To je dokazane pre 5 farieb (na to sme mali spievany dokaz - http://www.youtube.com/watch?v=PEBUYt8LgkY ); zatial sa to matematicky nedokazalo pre 4 farby. Vsetky moznosti sa ale zvladli prejst na pocitaci.
Odpovedať Známka: 3.3 Hodnotiť:
 

Hej, veta o 4. farbach je exaktny, vseobecny matematicky dokaz, len moznosti boli zatriedene do skupin a tie boli uz testovane na pocitaci. Naproti tomu toto tu sudoku (po vyluceni zbytocnych moznmosti) su len primitivnou hrubou silou otestovane vsetky relevantne moznosti.
Odpovedať Hodnotiť:
 

Nie minimum, ale maximum.
Odpovedať Známka: -5.0 Hodnotiť:
 

Nie je pravda. Oni len dokazali, ze ak urcis hocijakych 17 cislic, riesenie je jednoznacne. Ak urcis 16, nemozes ich urcit hala-bala, ale minimalne jedno mas fixne (z cervenej stvorice), ostatnych 15 moze byt hala-bala.
Odpovedať Hodnotiť:
 

no nemas pravdu. Sa zamysli, kludne by som ti vedel dat aj zadanie s 27 (a kludne aj viac) cislami (hala-bala) a nebude jednoznacne (napriklad ti plne vyplnim 3 horne 3x3 stvorce). Oni naozaj dokazali, ze neexistuje ziadne zadanie so 16 a menej cislami, ktore by bolo jednoznacne riesitelne. Nevadi, dostudujes, bude dobre. Teda ak uz nemas 15 rokov a viac, to uz budes mat trosku problem ;)
Odpovedať Hodnotiť:
 

Kurnik, no to je teda vyuzitie strojoveho casu. Rok pocitali sudoku aby si vytvorili sudoku rainbow tables.
Odpovedať Známka: 9.0 Hodnotiť:
 

joj ved staci ist za Jankou Hospodarovou.
Tej das hocico, emde5, ci es-ha-a (1,2,128,256, ci po novom uz aj 512!) a ona ti vrati plaintext.

Fakt! Neveris? Vyskusaj ...
Odpovedať Známka: -4.7 Hodnotiť:
 

typicka slovenska mentalita

Nie ze by vyskusali a sa presvedcili, ale radsej predbezne minuskuju.

Odpovedať Známka: -1.1 Hodnotiť:
 

Mňa by zaujímal skôr ten komprimačný algoritmus, z 418 GB na 6 GB, klobúk dolu :)
Odpovedať Známka: -2.9 Hodnotiť:
 

Je to jednoduche vysvetlit. Tych 418GB prevazne je cislica od 1-9 a vacsina algoritmu pracuje dobre s malym rozsahom dat.
Odpovedať Známka: 7.5 Hodnotiť:
 

Bol to asi obycajny textak, ten ti aj RARko dobre skomprimuje.
Odpovedať Známka: 3.3 Hodnotiť:
 

Pamatam sa ked som stiahol red alerta na psx.. Mal do 10MB, rozbalil som a mal 700MB. Vtedy som vazne nechapal, ale bolo to tak.
Odpovedať Známka: 6.7 Hodnotiť:
 

Pokial sa robi projekt takehoto rozsahu, je dost mozne, ze maju vlastny (upraveny) komprimacny algoritmus, specialne vhodny pre konkretny problem. Bezne pouzivane algoritmy su univerzalne, preto nemaju az taky dobry kompresny pomer.
Odpovedať Známka: 7.1 Hodnotiť:
 

to je pravda.. ja som osobne mal zbaleny iso z win vista a zbalene to malo 4mb bez srandy.. po rozbaleni a vypaleni bola funkcna instalacka..
Odpovedať Známka: -4.5 Hodnotiť:
 

jj, ale to si bralo dáta aj z aktuálneho systému. :D
Odpovedať Známka: 10.0 Hodnotiť:
 

Vidim ze ste mi dali minuska, hoci to je naozaj tak, je to v klasickom winrare, ma to 14MB a rozbali sa na stovky... Kto neveri nech si pozrie na nete zrarovany RA pre psx kolko zabera...
Odpovedať Známka: 7.1 Hodnotiť:
 

dal som ti +, aby si nebol smutny.
Odpovedať Známka: 8.7 Hodnotiť:
 

A co je na tom divne? Zalezi od struktury samotnych dat. Nie je problem mat take data, ktorych 100 TB sa spakuje na 1 MB.

Skor sa zamysli nad tymto, co som si v poslednom case vsimol: ako vsetci IT/matematikcy erudovani vedia, existuju velmi tazko skomprimovatelne data, ktore maju svinksy vysoku entropiu a nahodnost, t.j. nakuknutim F3 v TotalCmd binarnym ockom vidime len total chaos ACSII znakov (najcastejsie stratovo komprimovane multimedia obr, zvuk, video).
Odpovedať Známka: 4.3 Hodnotiť:
 

Súhlasím, je to o štruktúre dát. Tvoj spomínaný pomer
1 : 102.400 som nedosiahol, ale dostal som sa aspoň k hodnote
1 : 3.075.

obr: http://goo.gl/5QPJw

dáta: http://goo.gl/TZHoJ
:-)
Odpovedať Hodnotiť:
 

Pre istotu sa ale posunieme o par kB dole ze ano, lebo hlavicka moze mat dost pravidelnu strukturu, resp. o par MB pred koncom, nakolko frame index AVI kontajnera je tiez nevhodne pravidelny a teda neslusne dobre skomprimovatelny. Taketo data su napr. JPG, MP3, AVI ... a vzdy som vedel ze aj pri tej najkvalitnejsej/najnarocnejsej kompresii sa taketo data komprimuju na 99-100% povodnej velkosti, niekedy az na 101% povodnej velkosti (staci dat zaznam pre opravu dat, resp. SFX archiv, kde SFX kod pre Win32 exac ma asi 20-30 kB) ... jednoducho spoakovane to mohlo byt aj vascie ako povodne.
Odpovedať Známka: 6.0 Hodnotiť:
 

A co nevidim v najnovsom WINRARe 4.01 ci 4.10? AVIcko (DivX ci XviD kodek a audiostopa MP3 ... t.j. nie WAV a teda defacto pred casom uuuuuuplne neskomprimovatelne) spakovava na 80% povodnej velkosti!!!!!!!!! Bol som z toho asi den uplne mimo jak ku**vsky dobry algoritmus sa vyvinul na pakovanie takehoto typu dat. Nepakujem totiz kazdy den a posledne intenzivnesjie vyuzivane WinRARy boli u mna verzie 3.5x ci 3.6x spred min. 5 rokov ked nie viac ...
Odpovedať Známka: 0.0 Hodnotiť:
 

Ser na WinRAR... chod na opensource 7zip...
Odpovedať Známka: 0.0 Hodnotiť:
 

si z toho slova open source vlhky
Odpovedať Známka: 0.0 Hodnotiť:
 

Chlapce, tak tomu ver ze som z open-sourcu vlhky. Ukaz mi aspon jeden priklady z realnej praxe, kde sa ti zoberu ludia, ktori vo svojom volnom case pracuju zadarmo, a ich praca je vyuzivana ludmi po celom svete.. tomu hovorim kurevsky dobra cesta k utopii :)
Odpovedať Hodnotiť:
 

Rodney McKey
Odpovedať Hodnotiť:
 

Neviem, nechcem byť za debila ale mne tá úloha nepríde tak zložitá aby musely obetovať tolko počítačového času. Ja si viem predstaviť pekný algoritmus čo by to bez problému zvládol za deň na normálnom počítači.

Uniká mi niečo?
Odpovedať Známka: -5.0 Hodnotiť:
 

Opis ten algoritmus.
Odpovedať Známka: 6.0 Hodnotiť:
 

Najskôr by som našiel spôsob ako zoradím všetky možnosti lubovolných usporiadaní 16 čísel na sudoku poly, a potom by som ich optimálne preveril.
Odpovedať Hodnotiť:
 

Takych moznosti je radovo 6,9e30, ak by si ich len prechadzal (pocitam 1 operaciu na priechod, comu sa zdaleka nepriblizis), tak to zoberie cez 285 miliard rokov.
Pritom pocitam, ze mas to najlepsie od NVidie - S2050 1U GPU Computing System, ktory zvlada pri 575MHz spracuvat 1792 paralelnych vlaken, tj. 1.03e12 operacii za sekundu.
Odpovedať Známka: 3.3 Hodnotiť:
 

Pardon, shader clock na tom systeme bezi 2x tak rychlo, takze si zober nieco cez 142 miliard rokov (stale pocitam 1 operaciu na vybavenie 1 sudoku).
Aj tak by ma zaujimalo, kolko ludi si kupi taku "hracku" za 15 700 $.
Odpovedať Známka: 3.3 Hodnotiť:
 

O algoritmoch a zlozitosti exituje cela veda, cela cast matematiky (niekedy sa jej nadava aj teoreticka informatika). A ked sa nahodou o nejakom probleme dokaze, ze na vyriesenie efektivnejsi algoritmus neexistuje, tak jednoducho neexistuje! Samozrejme nenarazam na tento konkretny sudoku priklad. Pre krasti cas vypoctu ostava moznost uz len zrychlit vypocet (resp. ina koncepcia vypoctu, napr. nie deterministicki von Neumanovi-Boolovi kremikovi pablbi, ale nedeterministicke kvantove pocitace), avsak z pohladu matematiky pouzitim toho isteho algoritmu.

Vzdy ma fascinuje, ked pri nejakom "objave" ci skor objaviku, pri hocijakej matematickej prkotine ci hracke sa najde niekto, kto naraza na primitivnost pouziteho algoritmu a teda na jeho neslesne velku neefektivnost a ze on/ona (aby tu nebol sexiszmus) by to vedel/vedela ovelaaaaaa rychlejsie.
Odpovedať Hodnotiť:
 

"Nakoniec ho spustili na klasteri Stokes v Irish Centre for High-End Computing"

Na klasteri, na bicykeli...

Chudak Slovencin.
Odpovedať Známka: 10.0 Hodnotiť:

Pridať komentár