V životě každého pořádného muže..

11.5.2010 15:04 | Přečteno: 1888× | GNU

V životě každého pořádného muže nastanane někdy okamžik, kdy pocítí potřebu napsat vlastní operační systém, bootloader, virus.... nebo alespoň sudoku solver.

Myslím že je jeden z těch lepších, rozhodně lepší než ty ukázkové bláboly v učebnicích programování, nebo co je na wikipedii..

#! /usr/bin/python

def hide_column(c):
    c[0][1] = c[1]
    c[1][0] = c[0]
    r = c[3]
    while not r is c:
        i = r[1]
        while not i is r:
            i[2][3] = i[3]
            i[3][2] = i[2]
            i[5][5] -= 1
            i = i[1]
        r = r[3]

def show_column(c):
    r = c[2]
    while not r is c:
        i = r[0]
        while not i is r:
            i[2][3] = i[3][2] = i
            i[5][5] += 1
            i = i[0]
        r = r[2]
    c[0][1] = c[1][0] = c

root = []
root[:] = root, root

def solve(*chain):
    c = root[1]
    if c is root:
        return solution(chain)
    i = c[1]
    while not i is root:
        if i[5] < c[5]: c = i
        i = i[1]
    hide_column(c)
    r = c[3]
    while not r is c:
        i = r[1]
        while not i is r:
            hide_column(i[5])
            i = i[1]
        solve(r, chain)
        i = r[0]
        while not i is r:
            show_column(i[5])
            i = i[0]
        r = r[3]
    show_column(c)

columns = {}

def move(row, *cols):
    r = []
    r[:] = r, r
    for col in cols:
        c = columns.setdefault(col, [])
        if not c:
            c[:] = root[0], root, c, c, col, 0
            c[0][1] = c[1][0] = c
        i = []
        i[:] = r[0], r, c[2], c, row, c
        i[0][1] = i[1][0] = i[2][3] = i[3][2] = i
        c[5] += 1
    r[0][1] = r[1]
    r[1][0] = r[0]

if __name__ == '__main__':
    from re import findall
    def solution(chain):
        m = {}
        while chain:
            i, chain = chain
            m.update(i[4])
        for row in range(9):
            for col in range(9):
                print m[row, col],
            print
    for row, col in enumerate(findall('\n(\S.+)', '''

  ultra tezky?
2 8 5 . . . . . .
. 7 . . 2 5 . . 9
. . . . . . . . 4
1 9 . . . . . . .
6 . . . 9 . . 1 .
. . . 7 . 4 . 8 .
. . . 8 . 3 . . .
. . 3 6 . . . 4 .
. . . . . . 5 . .

''')):
        for col, c in enumerate(findall('(\S+)', col)):
            for c in c == '.' and range(1, 10) or (int(c),):
                move({(row, col): c},
                    (row, col), # matrix
                    ('R', row, c), # rows
                    ('C', col, c), # columns
                    ('B', row/3, col/3, c), # blocks
                )
    solve()

       

Komentáře

[Roger]

A je to aspon mikrokernel, nebo trapne monoliticke? :)

[Lolitos]

Je to mikromonoliticke...

[Radek Podgorny]

...ukazkove okomentovano...

[Milan Lajtoš]

Správny kód je komentár sám o sebe. ;)

[ZeXx86]

Ja jsem napsal vsechno az na to sudoku :(

[dolik.rce]

Nechce se mi to studovat, takže otázka do davu: Řeší to brute-force nebo logicky?

Když jsem byl ještě mladý a hloupý, tak jsem taky jeden napsal (brute force), možná ještě funguje Rychlost bohužel dost závisí na konkrétním sudoku, od sekund do několika minut :-/

[zde]

Je to klasický backtrakovací DLX. Nejvíc se mi líbí idiom pro inicializaci root node doubly linked listu

root = []
root[:] = root, root

[JS]

Jestli dela jen backtracking, tak bude pomaly. Ja bych backtracking delal jenom tam, kde by nepomohlo oznacovani moznosti cisel v kazdem policku. To mi prijde jako rychlejsi metoda.

[zde]

DLX (aka Dancing Links) je nejefektivnější známá implementace backtracingu, resp výběr možného tahu, a následná eliminace zbývajících tahů, které jsou s tím vybraným v konfliktu. Při výběru položky pro pokrytí se vezme ta, kde je nejmenší počet variant, takže rekurze málo leze do šířky. Čelenž je to implementovat v pythonu, protože se musí pracovat s cyklickýma strukturama, a třeba jen napsat a == b místo a is b vede k zacyklení a chybě.

[JS]

Aha, OK. Jak to rikate, tak mi pripada, ze je to proste efektivni implementace systemu, ktery udrzuje hranovou konzistenci, jak jsem vlastne rikal vyse (akorat ja to delam naivne a neznam terminologii).

[zde]

No, asi to bude to co si myslíte. Udržuje si to takový 4 směry prolinkovaný toroid uzlů, kde řádky představují možné "tahy", a sloupce prostor, který je třeba pokrýt právě jednou položkou. Na Wiki je to celé krásně vysvětleno, ten algoritmus je opravdu excelentní.

http://en.wikipedia.org/wiki/Dancing_Links

[thingie]

Ach bože, proč? V životě jsem se neobtěžoval ani zjistit jaká má vlastně Sudoku pravidla. Křičí to „Nuda!“ už z deseti kilometrů. Jsou zajímavější problémy.

[zde]

Nojo.. taky pliveš na osmičku?

[thingie]

Ne, nevim co to je. (Číslo, no, čeho?)

[cynic_asshole]

To si lehneš na záda mezi koleje a vyčkáváš průjezdu vlaku. Jak se k tobě přiblíží lokomotiva, musíš plivnout na její číslo, co má na čele.

No, a z jednoho českého filmu je ta hláška "plivnout na osmičku", protože ta lokotka měla v identifikaci osmičku. Už nevím, který film to byl, ani o čem byl, ale tohle praktikoval jeden vyhozený železničář.

[nightfish]

Už nevím, který film to byl, ani o čem byl, ale tohle praktikoval jeden vyhozený železničář.

Knoflíkáři

[kotyz]

to je nahodou bozi film. neres, neprepinej a hlavne, po nicem nepatrej.

[Grunt]

Pitomci ( z Knoflikari ) 1997 - part 1

Pitomci ( z Knoflikari ) 1997 - part 2

[Mravokárce]

Každý není jako ty-znuděný, znechucený, závistivý.

[thingie]

To jistě. Blbců se všude stále najde.

[tsLnox]

Aspoň někdo, kdo má na to stejný názor jako já. A já už myslel, že jsem sám :)

[JS]

Ja jsem si napsal Sudoku v Pythonu, ktere automaticky doplnovalo do prazdnych policek, jake jsou moznosti. Tahle cast reseni Sudoku me nikdy nebavila. Timhle programem jsem dostal rovnou ty zajimave situace, ktere bylo treba resit slozitejsi heuristikou nebo backtrackem.

[Marek Bernát]

He? To jak to sudoku riešite? Nikdy som nepotreboval vypĺňať možnosti. Vždy stačilo použiť základné znalosti (axiómy) a pravidlá, aby človek mohol vyplniť ďalšie číslo (odvodiť teorém). Ešte som sa nestretol so sudoku, kde by nefungovala čistá logika (čím nechcem povedať, že to občas nedá sakra zabrať)

[JS]

Nevim, jestli to resim nejak zvlast efektivne, ale proste si do tech policek obvykle pisu moznosti cisel, jaka tam mohou byt (a pak uz je jen skrtam). Nedelam to tedy hned, nejdriv zkousim dosadit cela cisla na zaklade uz existujicich cisel (ale to je jen zrychleni te stejne metody pro cloveka; pokud si pocitac na zacatku napocita v kazdem policku moznosti cisel, ktera tam mohou byt, tak mu tato automaticky vypadnou jako policka, kde je jen jedina moznost), a snazim se explicitne nejprve najit ta mista, kde je tech moznosti malo. Pak mam tedy jeste par heuristik - napr. jsou-li v tom radku treba 2 policka kde muze byt 2 a 8, pak uz nikde v tom radku byt 2 nebo 8 byt nemuze.

Kazdopadne, jakmile mate v kazdem policku napsano, jake tam mohou byt moznosti, a upravujete ty moznosti na zaklade cisel, ktera jste objevil, pak uz je ten backtrack velmi rychly, protoze obvykle staci 1-2 pokusy na vyplneni celeho Sudoku (navic vam pocet moznosti v dane policku dost pomuze, protoze ten backtrack zacnete v policku, kde jsou jen 2 moznosti, a tim snizite mnozstvi vraceni se).

Nekdo mi take tvrdil, ze to dela jen logikou, ale me nebylo nikdy prilis jasne, jak vlastne. Tohle mi pripada subjektivne rychlejsi a pohodlnejsi.

[Marek Bernát]

Jasné, že sa to dá riešiť backtrackom, ale je to de facto podvod Určite je možný aj nasledujúci postup riešenia: náhodne vyplniť všetky políčka a potom overiť, či spĺňa pravidlá sudoku. Ale asi sa zhodneme, že okrem toho, že to nie je moc efektívne, tak to asi nie je to, o čom by riešenie sudoku malo byť Sudoku, tak ako ho chápem ja, je o tom, že čisto na základe logiky (z už vyplnených čísel + pravidiel sudoku), si budujete a prehlbujete databázu znalosti o systéme (číslach, ktoré kde majú byť) a to tak dlho, kým nemáte všetko. Neviem to vyjadriť presnejšie, každopádne, žiadny backtrack netreba. Aj keď je jasné, že vo finálnych štádiách Vám to ten backtrack môže urýchliť, lebo namiesto premýšľania len tupo skúsite všetko vyplniť a ak to sedí, vyhrali ste, ak nie, tak správne je druhá možnosť. Ale ako hovorím, toto považujem za podvod. Alebo inak, nemá zmysel to riešiť týmto spôsobom, lebo backtrack Vám nič nedá, to je len tupé prechádzanie všetkých možností. To už rovno môžete to sudoku zadať počítaču. Tiež to bude subjektívne rýchlejšie a pohodlnejšie Naopak, riešenie dedukciou trénujé úplne rovnaké schopnosti, aké sú potrebné napríklad v matematike pri dokazovaní teorémov. Sorry, že som sa trochu rozkecal

[podlesh]

Opravdu to jde zcela bez backtrackingu? Opravdu lze v každém stavu deterministicky zjistit správný další krok? To mi přijde jako docela odvážné tvrzení.

[zde]

No, vzhledem k tomu že backtracing je omezený na maximálně 91 kroků, a ty můžeš backtracing do konečné hloubky přeformulovat na jedno složité deterministické pravidlo, tak je výše uvedené tvrzení že to jde bez backtracingu pravdivé. Ovšem neříká to nic o tom jestli to bude jednodušší nebo rychlejší.

[Marek Bernát]

Podľa mňa zadania sudoku sú robené tak, aby sa toto dalo. A moje stovky vyriešených sudoku mi to zatiaľ 100% potvrdili (nie je to dôkaz samozrejme ). V opačnom prípade sa tá úloha redukuje na prachsprostý backtrack, čo je úloha pre stroje a nie pre človeka...

[zde]

Nesmysl, tvůrčí myšlení a dedukce není nic jiného, než zvažování možností, a důsledků jejich volby. Čím jsi chytřejší, tím lépe předvídáš, tím rychleji zahazuješ slepé cesty, a proto postupuješ rychleji. BTW teorémy se taky automatizovaně dokazují docela dobře...

[Marek Bernát]

Pletiete si dedukciu a indukciu. Odporúčam začať článkom na wikipédii Pri dedukcii nejde o žiadne zvažovanie možností. Keď mám axióm A a pravidlo A -> B, tak viem odvodiť B. Takto môžem vybudovať inferenčne celú databázu znalostí o systéme (ak je konečný ako v prípade sudoku). Jasné, že pri konečnom systéme môžete použiť aj backtrack a na konci skúmať konzistenciu, alebo rôzne kombinácie oboch, ale o tom sudoku podľa mňa nie je.

[Stevko]

To, čo popisuje mi príde ako hranová konzistencia. Hodne by to malo urýchliť následný backtracking (a pri sudoku v mnohých prípadoch úplne stačí na celé vyriešenie). Ale sú také, kde to bez aspoň jedného tipnutia nejde. Odporúčam nainštalovať balíček sudoku (aspoň v Debiane sa tak volá) a spustiť si "sudoku -cfiendish".

[Marek Bernát]

Ok, skúsim. Ale IMHO musí to riešenie byť vždy dosiahnuteľné logickou úvahou (aspoň ak je skutočne jednoznačné). Dokázať toto tvrdenie ale asi nie je triviálne Pozriem na wikipédiu, čo píše o sudoku

[JS]

Tak samozrejme, mluvit o backtracku je trochu zavadejici, protoze klasicke Sudoku (3x3 hodnoty) je jen omezeny problem, tedy lze postavit dostatecne slozitou konecnou mnozinu logickych pravidel, ktera vam to dovoli vyresit.

Ale obecne, pro Sudoku (NxN hodnot), protoze je takove Sudoku NP-uplne, neni mozne obejit se bez backtracku (kdyby to slo, dokazal byste P=NP).

Jinak je to tak, to co rikam je podminka hranove konzistence. Vlastne si zapisuji, kterymi vsemi barvami muzete obarvit dany vrchol.

Kazdopadne, me prijde, ze na to, abych resil Sudoku ciste logickou uvahou nema muj mozek dostatek pracovni pameti.

[Marek Bernát]

Vcelku súhlasím.

Čo sa týka hranovej konzistencie, ja len tvrdím, že okrem elementárneho prípadu, kedy Vám zostane už len jedna možnosť, to nie je príliš užitočné. Aspoň mne to teda nikdy pri zložitejších sudoku nepomohlo. Môžete si na N miest napísať, že všade už sú len dve možnosti, ale čo z toho, keď Vám žiadna elementárna úprava už nič neeliminuje? Ja si skôr budujem iný znalostný systém, založený na tom, čo všetko už kde nemôže byť, napr., čo obsahuje daný stĺpec, alebo kde presne sa môže ešte vyskytovať množina čísel v danej bunke. Pomocou kombinácie týchto znalostí už som po dlhšej úvahe (a niekedy veľmi dlhej) obvykle schopný odvodiť ďalší fakt o systéme (nie nutne presnú pozíciu čísla, ale ďalšie obmedzenie na niektorý stĺpec, atď.). A s týmto systémom je mi úplne jedno, či mám niekde napísané, čo kde môže byť (teda, skôr by mi to tam prekážalo). Ale možno som len nepochopil, ako presne postupujete, to sa nedá vylúčiť

[JS]

Tak mozna mate sakra dobrou pamet. Ja bych si tu informaci, kterou popisujete, asi nezapamatoval.

Kazdopadne, ta hranova konzistence rika vice veci. Napriklad kdyz mate ve stejnem ctverecku dve policka, v kterych muzou byt jen 2 stejne moznosti, pak uz vite, ze nikde jinde v tom ctverecku nebudou tato 2 cisla, a muzu si je tedy v ostatnich polickach skrtnout. Stejne tak to plati pro 3 policka, ale to uz se nestava tak casto. Take se stava, ze mate urcitou cifru jako moznost jen v jednom z policek v ramci ctverecku, a pak je jasne, ze tam bude. Totez zase plati i pro 2 stejne cifry. A samozrejme vsechno tohle plati i v ramci sloupcu/radku. Proste z toho, ze mam napsane, co kde muze byt, vidim dost veci a nemusim si je pamatovat. Backtrack je obvykle az posledni moznost, a ten zacinam na mistech, kde jsou 2 moznosti, protoze tam je nejvetsi sance dostat spravny vysledek.

[Marek Bernát]

To ani nie. Na niektoré tie fakty zabudnem, ale keďže sú znova odvoditeľné (vždy sa dajú úplne vybudovať z aktuálne vyplnených čísel) a raz sa mi to už podarilo, tak to zvládnem znova Ale inak je pravda, že keď sa človek snaží niečo dlhšie odvodzovať, tak si to zapamätá. Tak si napríklad dodnes už roky pamätám dôkazy, ktoré som vymýšľal na skúške z analýzy (občas sme dostali dokázať niečo, čo sa tak úplne nebralo...)

Aha, tak to ste popísali veľmi pekne. Keď tak nad tým rozmýšľam, tak moje odvodenia sa de facto tiež týkajú len zvyšovania poznatkov o tom grafe. Čiže naše postupy sú asi ekvivalentné. Aspoň teda formálne. Zvláštne ale je, že to vyplňovanie možností (párkrát som to už skúsal) mi vôbec nepomáha dostať sa ďalej. Asi mám holt mozog stavaný iným spôsobom a lepšie než s 50 políčkami a každým s niekoľkými možnými číslami, sa mi pracuje s väčšími celkami typu stĺpec. Ale skúsim niekedy nabudúce použiť znova Vašu metódu, keďže som na ňu získal teraz trochu nový uhol pohľadu.

[Marek Bernát]

Um, tak ten balíček z debianu už 2 roky nemá upstream. Tak som stiahol orig source a nefungovalo. Tá tvoja option -c je až v debian patchi

[Lojza]

Tak. A ted to postupnymi upravami preved na lambda vyraz

tady

tady

[Stevko]

Niekde som počul, že v Prologu sa to napíše jednoduchšie.

[Marek Bernát]

Jj, tomu by som veril. Sudoku je úloha ako stvorená pre nejaký automated proof system

[zde]

Jenže tohle není DLX, jen jednoduchý generátor s verifikací. Myslím že kdybys mu dal prvních pár řádků prázdných, tak to neskousne. Navíc je to 3.6k oproti mým 2.3k, takže bych netvrdil ani že je to "jednodušší"..