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.




Najnovšie články:



Diskusia:

super Od reg.: Pjetro de | Pridané: 9.1.2012 10:06 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ť:

Re: super Od reg.: Pjetro de | Pridané: 9.1.2012 10:08 (mysli sa tak, aby ziadne dva susedne staty nemali rovnaku farbu) Odpovedať Známka: 6.0 Hodnotiť:

Re: super Od: peter7987 | Pridané: 9.1.2012 11:41 staty ale musia mat spojite uzemie...nezabudat! :) Odpovedať Známka: 5.0 Hodnotiť:

Re: super Od: nepodstatne | Pridané: 9.1.2012 10:27 A dokaz na farbenie grafu v euklidovksej rovine je dokazatelne aj matematickym dokazom, nie len na pocitacoch... Odpovedať Známka: 6.7 Hodnotiť:

Re: super Od: FIIT | Pridané: 9.1.2012 12:23 Staci si nastudovat teoriu grafov :) Odpovedať Známka: 3.3 Hodnotiť:

Re: super Od: branchman | Pridané: 9.1.2012 13:17 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ť:

Re: super Od reg.: Pjetro de | Pridané: 9.1.2012 17:53 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ť:

Re: super Od reg.: weiss | Pridané: 9.1.2012 13:18 Nie minimum, ale maximum. Odpovedať Známka: -5.0 Hodnotiť:

Re: super Od: adf | Pridané: 9.1.2012 18:18 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ť:

Re: super Od: mato_fmfi | Pridané: 10.1.2012 9:50 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ť:

strojovy cas Od: trololoman | Pridané: 9.1.2012 10:07 Kurnik, no to je teda vyuzitie strojoveho casu. Rok pocitali sudoku aby si vytvorili sudoku rainbow tables. Odpovedať Známka: 9.0 Hodnotiť:

Re: strojovy cas Od reg.: DeMenthol | Pridané: 9.1.2012 14:35 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ť:

Re: strojovy cas Od reg.: DeMenthol | Pridané: 9.1.2012 22:30 typicka slovenska mentalita Nie ze by vyskusali a sa presvedcili, ale radsej predbezne minuskuju. Odpovedať Známka: -1.1 Hodnotiť:

Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: felix1 | Pridané: 9.1.2012 12:53 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: sadasda | Pridané: 9.1.2012 13:05 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: weiss | Pridané: 9.1.2012 13:17 Bol to asi obycajny textak, ten ti aj RARko dobre skomprimuje. Odpovedať Známka: 3.3 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: djrachot | Pridané: 9.1.2012 13:47 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: qqqqqqqqqq | Pridané: 9.1.2012 14:04 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: ujo tomas | Pridané: 9.1.2012 14:50 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: xxxmisko | Pridané: 9.1.2012 16:05 jj, ale to si bralo dáta aj z aktuálneho systému. :D Odpovedať Známka: 10.0 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: djrachot | Pridané: 9.1.2012 16:31 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: leporelo | Pridané: 9.1.2012 16:50 dal som ti +, aby si nebol smutny. Odpovedať Známka: 8.7 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: Pjetro de | Pridané: 9.1.2012 18:02 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ť:

kompresný pomer 1: 3.075 Od: mironad | Pridané: 13.1.2012 21:29 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: Pjetro de | Pridané: 9.1.2012 18:03 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: Pjetro de | Pridané: 9.1.2012 18:04 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: Peterkal | Pridané: 9.1.2012 18:12 Ser na WinRAR... chod na opensource 7zip... Odpovedať Známka: 0.0 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: fergrt | Pridané: 9.1.2012 23:11 si z toho slova open source vlhky Odpovedať Známka: 0.0 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: Bleh | Pridané: 10.1.2012 17:07 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ť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: HKJ | Pridané: 9.1.2012 23:36 Rodney McKey Odpovedať Hodnotiť:

Nejak neoptimálne Od: Burlak | Pridané: 9.1.2012 20:24 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ť:

Re: Nejak neoptimálne Od: aaaaaaaaaaaaaaaaaaaa | Pridané: 9.1.2012 20:54 Opis ten algoritmus. Odpovedať Známka: 6.0 Hodnotiť:

Re: Nejak neoptimálne Od: v skratke | Pridané: 9.1.2012 21:00 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ť:

Re: Nejak neoptimálne Od: branchman | Pridané: 9.1.2012 21:39 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ť:

Re: Nejak neoptimálne Od: branchman | Pridané: 9.1.2012 21:54 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ť:

Re: Nejak neoptimálne Od reg.: Pjetro de | Pridané: 10.1.2012 7:43 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ť:

Titulok Od: MenoX | Pridané: 10.1.2012 3:56 "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