abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 09:00 | Nová verze

Vývojáři KDE oznámili vydání KDE Gear 21.04. Ne, nejedná se o novou aplikaci. Bylo rozhodnuto, že KDE Gear bude nový název pro KDE Applications, tedy pro aplikace, související knihovny a pluginy. Na počátku bylo KDE aneb K(ool) Desktop Environment, následně jenom K Desktop Environment. Později se mluvilo o KDE SC neboli KDE Software Compilation. To byl společný název pro grafické prostředí Plasma, platformu a aplikace. Dále proběhlo

… více »
Ladislav Hagara | Komentářů: 6
dnes 08:00 | Zajímavý článek

Moxie Marlinspike, vývojář komunikační aplikace Signal, se dostal ke kitu firmy Cellebrite pro forenzní analýzu smartphonů, dodávanému represivním složkám různých států včetně autoritářských režimů. V zápisku ho popisuje včetně zranitelností a možných porušení licencí. Jedna z chyb v Cellebrite vede při načtení zvláštního souboru k narušení integrity veškerých reportů. Budoucí verze Signalu mají obsahovat zvláštní soubory.

… více »
Fluttershy, yay! | Komentářů: 0
včera 23:55 | Komunita

Ubuntu 21.10 bude Impish Indri (rošťácký lemur).

Ladislav Hagara | Komentářů: 2
včera 18:22 | Nová verze

Bylo vydáno Ubuntu 21.04 s kódovým názvem Hirsute Hippo. Přehled novinek v poznámkách k vydání. Zdůrazněna je možnost integrace s Microsoft Active Directory, Wayland ve výchozím stavu a vývoj aplikací pomocí Flutteru.

Ladislav Hagara | Komentářů: 13
včera 12:22 | Komunita

Prohlášení (Twitter) Minnesotské univerzity k výzkumu proveditelnosti nenápadného začlenění bezpečnostních chyb do Linuxu: Situaci bereme vážně. Výzkum jsme pozastavili. Prozkoumáme výzkumnou metodu a její schválení. Stanovíme opatření…

Ladislav Hagara | Komentářů: 59
včera 11:22 | Nová verze

OpenJS Foundation, oficiální projekt konsorcia Linux Foundation, oznámila vydání verze 16.0.0 (Current) otevřeného multiplatformního prostředí pro vývoj a běh síťových aplikací napsaných v JavaScriptu Node.js (Wikipedie). Přehled novinek v článku na Medium.

Ladislav Hagara | Komentářů: 4
včera 09:44 | Pozvánky

Na MFF UK pokračuje série on-line přednášek o architektuře a implementaci operačních systémů. Dnes je na programu Live kernel patching, příští týden ladění kernelu a kdump, další přednášky jsou naplánovány až do 3. června.

… více »
Vojtěch Horký | Komentářů: 0
včera 09:00 | Nová verze

Byla vydána nová verze 3.3 multiplatformního open source herního enginu Godot (Wikipedie, GitHub). Přehled novinek i s náhledy a videi v oficiálním oznámení.

Ladislav Hagara | Komentářů: 0
21.4. 21:22 | Komunita

Mozilla.cz informuje, že Mozilla z Firefoxu pro Android i iOS odstraní integraci „sledovacího“ systému Leanplum. Leanplum sbírá informace, jak moc uživatelé používají záložky, panely, integraci Pocketu apod. Českých uživatelů se to prý příliš netýká.

Ladislav Hagara | Komentářů: 4
21.4. 20:44 | IT novinky

Microsoft v příspěvku na svém blogu představil WSLg (Windows Subsystem for Linux GUI) aneb rozšíření WSL přinášející možnost spouštění grafických linuxových aplikací. V dalším příspěvku je rozebrána architekturu WSLg. Videoukázka práce s WSLg na YouTube.

Ladislav Hagara | Komentářů: 4
Kolik času v průměru denně trávíte videohovory/-konferencemi? (ať už v práci, škole nebo soukromě)
 (50%)
 (12%)
 (16%)
 (12%)
 (7%)
 (1%)
 (2%)
Celkem 408 hlasů
 Komentářů: 7, poslední 8.4. 12:14
Rozcestník

Automatický Slitherlink solver

30.8.2010 11:33 | Přečteno: 1696× | GNU | poslední úprava: 30.8.2010 11:43

Přemýšlel jsem jak co nejlépe implementovat řešení tohoto hlavolamu. Použil jsem opět starý dobrý DLX solver, který výborně funguje pro Sudoku, a který docela dobře šel použít i pro Kakuro. Zatím jsem skončil zhruba u tohoto postupu, který dobře (tj do desítek sekund) řeší 7x7 puzzle, a většinu 10x10 puzzlí:

1) Pro střed každého čtverce vygeneruj "tahy", které pokryjí 4 strany tohoto čtverce správným počtem čar. Tj pro "0" bude možnost jen jedna, pro "1" budou 4, pro "2" jich bude 6 apod. Tohle je jednoduché, prostě smyčka 0-15, a počítá se hammingova váha.

2) Je třeba zajistit, aby tahy které pokryjí sousední čtverce, nastavovaly společnou hranu stejně. Tohle řeším pomocí optional constraints, podobně jako v 8-queens. Každý tah na každém čtverci jednak pokryje tento čtverec, a dál pokryje optional constraint pro svou "jižní" a "východní" stranu. "Severní" a "západní" hrana je ale 1) přesunuta do sousedícího čtverce, 2) negována. Díky tomu by v případě že by sousední čtverce nastavovaly společnou hranu na opačnou hodnotu, díky této negaci sdílely stejný optional constraint, a tím jsou tyto tahy eliminovány.

3) Správné řešení má mít jen jednu smyčku. Proto jsem ještě zavedl omezení na počet hran, které se mohou potkat ve vrcholech čtverců. Aby se zamezilo větvení a křížení, každý vrchol může mít právě 2 nebo právě 0 hran.

Tohle jsem zatím trochu odbyl, a řeším to až po výběru tahu jeho validací, a zahozením v případě že by a) zvýšil počet hran vedoucích do některého z 4 vrcholů na 3, nebo b) pokrývá poslední hranu do některého vrcholu, a nastavuje ji na jedničku. Tohle je složitější, musí se kvůli tomu ještě testovat na okraj hracího pole.

Přemýšlím že bych ten kód místo do verifikace tahu změnil na udržování invariantu, že všechny dostupné tahy jsou OK, a když některý čtverec pokryju, tak prořežu volné tahy pro ostatní čtverce (a samozřejmě strčím je na stack, a při backtracku je zase obnovím). Tohle se pro Kakuro velice osvědčilo, a urychlilo to řešení fakt dost.

4) První 3 možnosti řeší lokální vlastnosti řešení, ale správné řešení má být jedna uzavřená smyčka. Tahle verifikace není úplně triviální na naprogramování, a zatím jsem ji ani nenapsal. Místo jednoho správného řešení se mi proto vygeneruje i cca 2-5 dalších, které ale taky vypadjí zajímavě, a to správné pořád snadno vyberu.

Otevřené otázky:

* Má smysl přepisovat test na spojitost (bod 3)? na prožezávání? Má smysl testovat řešení že obsahuje pouze jednu smyčku (bod 4)?

* Nejsem si jistý jestli ten test na spojitost nečistí stavový prostor víc, než samotné omezení na počet hran u čtverce. Jestli jo, asi by bylo lepší postupovat opačným směrem- pokrývat tahy vrcholy tak, že pro každý vrchol bude právě 7 možností jak jej pokrýt- buď bude vrchol holý (1 možnost), nebo pokytý dvěma hranami (6 možností). Při pokrývání by se počítaly hrany po obvodech čtverců, a verifikovalo/prožezávalo by se podle toho teprve dodatečně.

* Úplně jiné řešení: Nebudou se vůbec generovat "hrany", budu přímo "barvit" čtverce na 2 možné barvy. Hrany budou definovány implicitně, kde se stýkají rozdílné barvy, bude hrana. Tohle vypadá lákavě, protože pro každý čtverec jsou jen 2 možné tahy, takže stavový prostor je nejmenší. Jenže zase by to povolovalo "šachovnicové" vzory, které jsou ve správných řešeních zakázány, tohle by bylo potřeba explicitně testovat a vyhazovat.. Imlementace by jinak byla podobná jako u pokrývání vrcholů- verifikace/prožezávání podle počtu hran kolem každého čtverce..

Možná je ještě nějaké další dobré řešení? Preferuji jednoduchost a eleganci i mírně na úkor efektivity.        

Hodnocení: 100 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

vlastikroot avatar 1.9.2010 06:24 vlastikroot | skóre: 24 | blog: vlastikovo | Milevsko
Rozbalit Rozbalit vše Re: Automatický Slitherlink solver
Díky, to puzzle vypadá dobře :-)
Sg1-game | We will destroys the Christian's legion ... and the cross, will be inverted | IP 80.188.182.6
ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.