Jak luštit sudoku pomocí balíčkovacího systému

Daniel Burrows ve svém blogu popisuje, jak využít balíčkovací systém Debianu pro luštění hlavolamů sudoku (prostřednictvím řešení závislostí mezi balíčky).

24.8.2008 10:58 | Robert Krátký | Zajímavý článek

Komentáře

[saly]

rofl

[Drom]

lol

Ted teprv mi ty krizovky pro hloupy prijdou necim zajmavy :)

[Robert Krátký]

Tak se ukažte, umí tohle urpmi/zypper?

[Ilfirin]

Určitě. Otázka je, proč by to někdo dělal?

[Honza]

Protoze to jde! :)

[pht]

RTFA a odpovis si sam

[Robert Krátký]

Jestli narážíš na "a package management system that can solve Sudoku based on package dependency rules is not something that I think would be useful or worth having", tak to jsou poraženecké řeči, které bych si, být vývojářem rpm-based balíčkovacího systému, nenechal jen tak líbit...

[thingie]

Spíš na to, že ta věc má v sobě SAT solver (zypper), takže by bylo asi dost divné, kdyby to nezvládla. Výjádřit v ní zadání by (minimálně z toho čtyřbodového popisu v tom článku, sudoku jinak vůbec neznam) neměl být problém.

[thingie]

Otázka je spíš který ten systém to zvládne rychleji, asi.

[fakenickname]

slackware

[skywaker]

licencia GNU hovori ze akykolvek program uvolneny pod GNU licenciou mozete pouzit na akekolvek ucely.. takze balickovaci system mozete pouzivat skludom aj na riesenie hlavolamov sudoku..

[thingie]

Tam se to vyjádřit nedá. To je jistý případ balíčkovače neschopného řešit sudoku (přesněji řečeno neschopného řešit cokoliv, protože se s ním fakt nic spočítat nedá).

[Viliam Púčik]

přesněji řečeno neschopného řešit cokoliv

Ale pan kolega Je sice pravda, ze balickovaci system Slackwaru este dlho nebude vediet riesit Sudoku, ale za to prekvapivo dokaze instalovat, upgradovat a odinstalovat baliky.

A neriesenie zavislosti? No, zalezi na uhle pohladu. Slackware riesi zavislosti tak, ze ich neriesi (podobne ako prazdna mnozina je tiez mnozinou, hoci prazdnou).

[thingie]

Ale já teď absolutně neřeším, jestli to instaluje balíky nebo ne. To je mi úplně jedno. Řeším tu jenom jaké výpočetní problémy dokáže nějakým způsobem ta věc vyřešit, a Slackware se svým balíčkováním, které je ve skutečnosti jen sadou jednoduchých skriptů, toho prostě moc nevyřeší. Jestli je to dobré na instalování balíčků, to tu fakt není předmětem diskuse.

(Jestli je pro koho zrovna tato otázka zajímavá, to si zodpovězte sami.)

[Viliam Púčik]

Calm down man Ved ja s tebou suhlasim. Moj predosli prispevok bola len snaha zastat sa trosku balickovasieho systemu Slacka, s ktorym som co to preskakal. Malo ist skor o par jemne satiricky ladenych viet na zlepsie nalady. Podobne, ako sa to podarilo Burrowsovi s jeho Sukodu solverom

[thingie]

No, ty věty k tomu… já ani po stránce balíčkování nemám z balíčkovacího „systému“ ve slackwaru nějak dobrej pocit. Vůbec nelituju toho, že jsem to kdysi vyhodil. Balíčkovač, kde nemůžu mít pořádně netcat, protože binárku nc přepisuje nějakej jinej balík, furt (a oba z těch, co byly s distribucí), to neni nic moc. Stejně tak nefungující půlka Gnome, protože cdparanoia není tak zbytečnej balík jak se zdá (a z dokumentace neplyne). Ta věc neni pěkná, prostě. Všechno tohle je teda dávno a možná už i tam se běžně používá nějaká nadvěc, co aspoň něco automatizuje.

[Limoto]

Pacman

[Profesor Hrbolek]

portage/paludis na tebe!

[Viliam Púčik]

Pacman 3 (from Frugalware) Strikes Back

[zoul]

SAT solver? Svině chytrá, to bych si domů nepustil :)

[asdf]

Je mi ho ľúto chlapíka asi nemá čo s časom.

[default]

Aspoň nedělá z lidí hlupáky

[Roger]

A ted si predstav, ze pro nektere z nas je to docela zajimava informace :)

Nejde vubec o nejakou hru - ostatne, aptitude ma pro tyhle ucely uz roky vestaveny tetris :) Pokud bychom totiz predpokladali, ze Sudoku je NP-uplne (cemuz bych celkem veril, i kdyz se mi to nechce dokazovat - ale je to zminene i na WP), znamena to, ze aptitude umi (spocitat) vsechno. A to uz je dost zajimave ohodnoceni schopnosti :)

[Jirka P]

aptitude ma pro tyhle ucely uz roky vestaveny tetris

Nejsou to náhodou miny?

Pokud bychom totiz predpokladali, ze Sudoku je NP-uplne, znamena to, ze aptitude umi (spocitat) vsechno

1. ne všechno, ale jen to, co je ve třídě NP.
2. nemusíme předpokládat nic o Sudoku, o SATu to víme a převést SAT na závislosti balíčků je triviální.

[Roger]

Aano, jsou to miny - priznam se, ze jsem aptitude v interaktivnim rezimu nepustil uz dlouho :) Mel jsem si to overit predtim, ne az ted...

1. OK, uznavam, s tim "vsechno" jsem to lehce prehnal -- co takhle "vsechno rozumne"? :) NP je docela velka mnozina a NTS/CRF docela "kanon", nic lepsiho na ulici nenajdes.

2. Resilo se tu Sudoku, ne baliky (aspon predpokladam, ze prave reseni Sudoku spravcem baliku ho tak pohorsilo). A ano, je mi jasne, ze zavislosti baliku si primo rikaji o SAT, nicmene jak uz jsem rekl, nehodlam to tu dokazovat.

[Jirka P]

NP je docela velka mnozina a NTS/CRF docela "kanon"

Tohle je trochu nedorozumění, NTS a ČRF jsou svou výpočetní silou daleko, daleko dál za NP (dá se to vidět tak, že problémy z NP jdou vyřešit deterministicky v exp. čase, a tedy na ně stačí PRF).

MMCH, technicky vzato je NP jen o něco míň než 2krát větší než P. Pro každý predikát P(z, x) z P obsahuje totiž právě dva predikáty - ExP(z, x) a EyP(z, x) [E je existuje, Ex -- existuje x...], přičemž ty predikáty nemusí být různé.

Ze zajímavých problémů, které nejsou v NP - minimalizační variace na problémy v NP (SAT na nejmenší počet pravdivých proměnných, minimalizace booleovských formulí...), vyhrávající strategie některých her.

nic lepsiho na ulici nenajdes.

Teda nevim, ale pokud vy na ulici najdete NTS, tak já najdu NTS s orákulem, které řeší halting problem

Resilo se tu Sudoku, ne baliky

Jistě, ale pokud mělo být cílem ukázat, že závislosti jsou mocný nástroj, je Sudoku zbytečný mezičlánek. Sudoku se zde řeší primárně proto, že to nějakej týpek napsal žertem do blogu.

[Roger]

Tohle je trochu nedorozumění, NTS a ČRF jsou svou výpočetní silou daleko, daleko dál za NP (dá se to vidět tak, že problémy z NP jdou vyřešit deterministicky v exp. čase, a tedy na ně stačí PRF).

Teda, nejsem zrovna odbornik pres tridy slozitosti, ale doted jsem zil v presvedceni, ze DTS je silou ekvivalentni NTS (az na tu nepeknou exponencialu). A pak taky neco o ekvivalenci CRF a TS...

MMCH, technicky vzato je NP jen o něco míň než 2krát větší než P

Technicky vzato bych byl s porovnavanim NP a P opatrny, kdyz nikdo jiste nevi, jak to s nimi je :) A co se mohutnosti tyka, skoro bych si tipl, ze jsou obe nekonecne a spocetne, tj. budou na tom asi dost nastejno...

Ze zajímavých problémů, které nejsou v NP

Coz o to, vim o pocetnich ulohach apod. Ale priznavam, ze jsem se touhle casti uz nejakou dobu nezabyval, takze si tam nejsem tak moc jisty a radeji se tomu vyhnu, abych moc neplacal :) Obzvlast v tuhle hodinu a rozpolozeni.

Teda nevim, ale pokud vy na ulici najdete NTS, tak já najdu NTS s orákulem, které řeší halting problem

Viz nahore, pro me je NTS jen trochu rychlejsi DTS. A orakula bych do toho netahal, je to zly, osklivy podvod :) S nim umim halting problem vyresit taky...

Resilo se tu Sudoku, ne baliky

Jistě, ale pokud mělo být cílem ukázat, že závislosti jsou mocný nástroj, je Sudoku zbytečný mezičlánek. Sudoku se zde řeší primárně proto, že to nějakej týpek napsal žertem do blogu.

Ja cetl (a celkem zbezne) jen ty dva posty daneho cloveka, takze jsem moc nezkoumal, proc zrovna Sudoku, ale tady jsem to bral jako "lidsky zajimavejsi" problem. Kdyz normalnimu cloveku reknete, ze vas program resi SAT, asi se na vas bude jen divne divat, ale u Sudoku se chyti spis :)

[MJ]

Tohle je trochu nedorozumění, NTS a ČRF jsou svou výpočetní silou daleko, daleko dál za NP (dá se to vidět tak, že problémy z NP jdou vyřešit deterministicky v exp. čase, a tedy na ně stačí PRF).

Silnější než NP je i obyčejný DTS (který je ostatně svou silou ekvivalentní NTS). Každá třída s omezenou složitostí musí být nutně slabší než třída se složitostí neomezenou (to plyne z vět o časové/prostorové hierarchii).

MMCH, technicky vzato je NP jen o něco míň než 2krát větší než P.

Ehm? Dvakrát větší? Když mluvíme o nekonečných množinách?

Ze zajímavých problémů, které nejsou v NP - minimalizační variace na problémy v NP (SAT na nejmenší počet pravdivých proměnných, minimalizace booleovských formulí...), vyhrávající strategie některých her.

Nebo třeba úplně obyčejná ekvivalence regulárních výrazů.

[Jirka P.]

Ehm? Dvakrát větší? Když mluvíme o nekonečných množinách?

Nezáleží na tom, o jakých množinách mluvíme. 2*omega=omega (v kardinálové eritmetice)

Ze zajímavých problémů, které nejsou v NP ...

Nebo třeba úplně obyčejná ekvivalence regulárních výrazů.

To bude nějaký renonc, ekvivalence jazyků rozpoznávaných dvěma reguárními jazyky by měla být v P. Nemyslel jste nějakou jinou ekvivalenci, nebo nějaké jiné regulární výrazy (než ty, které rozpoznávají regulární jazyky)?

[MJ]

Nezáleží na tom, o jakých množinách mluvíme. 2*omega=omega (v kardinálové eritmetice)

No jo, ale to můžu říci, že je 42-krát větší, a bude to také pravda

To bude nějaký renonc, ekvivalence jazyků rozpoznávaných dvěma reguárními jazyky by měla být v P. Nemyslel jste nějakou jinou ekvivalenci, nebo nějaké jiné regulární výrazy (než ty, které rozpoznávají regulární jazyky)?

Nemyslel a opravdu to není tak lehký problém, jak se na první pohled tváří. (O některých variantách se dokonce ví, že v P určitě nejsou: třeba když do regulárních výrazů přidáme operátor zdvojení, popisují stále jenom regulární jazyky, ale ekvivalence je rázem daleko obtížnější.)

[thingie]

No, za předpokladu, že to třeba není rozbité a pro nějaké sudoku by to vrátilo špatný výsledek. Což se klidně může stát, ten článek nedokazuje, že to umí uřešit každé sudoku a správně. I když to předpokládáme.

[Roger]

Ukazuje tam, jak prevest (libovolne) sudoku na zavislosti baliku, ktere to resit umi (a ma). Neni mi jasne, co se vam na tom nezda...

Samozrejme, kazdy program ma chybu, ale o to tu ted nejde -- jde o princip. To je jako hadat se o vypocetni sile Ccka kvuli bugum v gcc.

[thingie]

Ono by to celkem oprávněně všechny závislosti být schopné řešit nemuselo. Nikdo to po tom ani moc nechce. Může to být schopné řešit jen některé případy.

Ale nezdá se mi na tom právě to usuzování, že když spočítám pár nějakých náhodných sudoku, že nezbytně spočítám všechny, i s předpokladem, že program je bezchybný. U řešení závislostí sudoku je to celkem sranda, tam to nejspíš platí, ale u kompilátoru by bylo absurdní zkusit si zkompilovat pár programů a v případě úspěchu se těšit z toho, že ta věc umí zkompilovat všechny, žejo.

[disorder]

mozte sa prestat dohadovat a precitat si co o tom uz pred casom napisal autor

http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku-2/

[JS]

Ukazuje tam, jak prevest (libovolne) sudoku na zavislosti baliku, ktere to resit umi (a ma). Neni mi jasne, co se vam na tom nezda...

Mozna by bylo zajimavejsi, jak prevest vypocet zavislosti na reseni Sudoku. Pak by se nemusel instalovat program na reseni zavislosti, ale stacilo by kazdemu uzivateli nainstalovat Sudoku.

Ne vazne, trochu mi to vrta hlavou. Podle jisteho clanku na Wikipedii bylo dokazano, ze Sudoku je NP-uplne (na desce NxN). Ale me neni zcela jasne, jak si tam zahraje ta jednoznacnost reseni - pokud ma mit Sudoku jednoznacne reseni, jak je mozne, ze ho lze ucinit ekvivalentnim s jinym NP-uplnym problemem, kde ta jednoznacnost zarucena neni?

[Roger]

Pro poradek, vy nepotrebujete "ekvivalenci", vy potrebujete "polynomialni prevoditelnost" :) Tj. potrebujete, aby to bylo "aspon tak tezke".

Co se jednoznacnosti Sudoku tyka (priznavam, ze o tehle hre moc prehled nemam, pakrat jsem to hral na telefonu a nechal vyhledat na WP "NP-Compl" :) ), mam pocit, ze jednoznacna je herni situace az od nejakych 17-18 zaplnenych policek -- je to zminene na WP, zkuste to tam dohledat (mne se jen vybavuje, ze to snad jeste uplne presne nedokazali, ale jen jsem to tehdy preletl). Vam jde ale v zasade jen o to, ze kdyz vyresite (nejak) dane Sudoku, umite pomoci toho pak (nejak) vyresit i tu svou ("jednodussi") ulohu.

Snad jsem to vic vyjasnil, nez zamlzil. Pokud to jeste neni uplne jasne, ptejte se (a klidne budte konkretni) -- v diskusi jsou zjevne i vetsi odbornici pres slozitost, takze vam kdyztak pomohou oni :)

[JS]

No, takhle, asi to bude otazka definice. Pokud se tim "Sudoku je NP-uplne" mysli Sudoku, ktere muze mit vic reseni, pak si tu ekvivalenci (pod kterou samozrejme myslim polynomialni prevoditelnost, to je jasne) predstavit dokazu. Ale kdyz by to Sudoku muselo mit jen jedno reseni, tak mi to tedy zrejme neni.

Co kdyz by totiz existoval resic Sudoku v P, ktery by vyuzival toho, ze existuje jen jedno reseni? Takovou moznost prece nelze uplne vyloucit. A to jsem se dival i do toho dukazu NP-uplnosti, ale nejak jsem tam tuto moznost nepostrehl.

S temi 17ti policky - to je nejmensi nalezeny pocet vyplnenych policek, ktere musi to Sudoku mit, aby melo jednoznacne reseni - tedy to s tim problemem moc nesouvisi.

[Roger]

Jen tak zbezne: Kdo rika, ze Sudoku musi mit jedine reseni? Minimalne bych cekal, ze bude mit ctyri stejna (rotace cele mrizky).

Ja tu vidim paralelu se SATem -- tam se mi taky muze obcas stat, ze splnujici ohodnoceni nejake zadane formule je jen jedine. A zpochybnuje nekdo kvuli tomu NP-uplnost toho problemu?

[JS]

Sudoku by melo mit, aspon podle definice te hry, jedine reseni (tedy ta Sudoku, co najdete v knizkach a tak maji vzdy jen jedno). Rotace ani permutace se nepocitaji za jine reseni, protoze ty uz zpusobi jine pocatecni usporadani cislic. Ale samozrejme lze uvazovat i o Sudoku, ktere ma vic reseni.

[Filip Jirsák]

Ne vazne, trochu mi to vrta hlavou. Podle jisteho clanku na Wikipedii bylo dokazano, ze Sudoku je NP-uplne (na desce NxN). Ale me neni zcela jasne, jak si tam zahraje ta jednoznacnost reseni - pokud ma mit Sudoku jednoznacne reseni, jak je mozne, ze ho lze ucinit ekvivalentnim s jinym NP-uplnym problemem, kde ta jednoznacnost zarucena neni?

Pak ale dostáváte jiný problém, a to jak o nějaké matici N × N čísel s některými políčky vyplněnými zjistit, zda je to Sudoku (tedy jestli vede právě k jednomu řešení).

[JS]

Jo, to je v tride #P, ale o to mi nejde. Moje otazka zni, zda problem v NP, kde je zaruceno jen jedno reseni, muze byt v principu NP-uplny - viz moje odpoved vyse.

[Jirka P.]

Jo, to je v tride #P ... - nač chodit tak vysoko, zjistit, zda dané Sudoku obsahuje nejvýš jedno řešení, je v coNP, aspoň jedno - NP, takže právě jedno řešení je v Delta-2-P

zda problem v NP, kde je zaruceno nejvýš jedno reseni, muze byt v principu NP-uplny

V principu tomu nic nebrání (např. pokud P=NP, pak to platí)

Nejste první člověk co se na tohle ptá, viz: http://weblog.fortnow.com/2005/08/sudoku-revisited.html

[MJ]

To se zatím neví – z toho by plynulo, že NP=UP, což je známý otevřený problém. Viz popis třídy UP v Complexity Zoo.

P.S.: Ověření jednoznačnosti Sudoku v třídě #P určitě není, protože to není třída rozhodovacích problémů. Určitě ale leží v P s orákulem z #P, případně také v Σ^P₂ (nedeterminismem uhodnu jedno řešení a pak zkontroluji, že každá jiná permutace řešením není).

[JS]

Diky, tobe i Jirkovi P. za vycerpavajici odpoved.