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í
×
    včera 17:44 | IT novinky

    Vláda Spojených států získala desetiprocentní podíl v americkém výrobci čipů Intel. Oznámili to podle agentur americký prezident Donald Trump a ministr obchodu Howard Lutnick. Společnost Intel uvedla, že výměnou za desetiprocentní podíl obdrží státní dotace v hodnotě 8,9 miliardy dolarů (zhruba 186 miliard Kč). Částka podle Intelu zahrnuje dříve přislíbené subvence 5,7 miliardy dolarů z programu CHIPS na podporu výroby čipů v USA,

    … více »
    Ladislav Hagara | Komentářů: 2
    včera 17:33 | Nová verze

    Organizace Apache Software Foundation (ASF) vydala verzi 27 integrovaného vývojového prostředí a vývojové platformy napsané v Javě NetBeans (Wikipedie). Přehled novinek na GitHubu. Instalovat lze také ze Snapcraftu a Flathubu.

    Ladislav Hagara | Komentářů: 0
    včera 04:22 | Nová verze

    Knihovna FFmpeg byla vydána ve verzi 8.0 „Huffman“. Přibyla mj. podpora hardwarově akcelerovaného kódování s využitím API Vulcan, viz seznam změn.

    Fluttershy, yay! | Komentářů: 0
    22.8. 17:44 | IT novinky

    Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) vydal Zprávu o stavu kybernetické bezpečnosti ČR za rok 2024 (pdf). V loňském roce NÚKIB evidoval dosud nejvíce kybernetických bezpečnostních incidentů s celkovým počtem 268. Oproti roku 2023 se však jedná pouze o drobný nárůst a závažnost dopadů evidovaných incidentů klesá již třetím rokem v řadě. V minulém roce NÚKIB evidoval pouze jeden velmi významný incident a významných incidentů bylo zaznamenáno 18, což oproti roku 2023 představuje pokles o více než polovinu.

    Ladislav Hagara | Komentářů: 1
    22.8. 13:55 | Komunita

    Byl publikován aktuální přehled vývoje renderovacího jádra webového prohlížeče Servo (Wikipedie). Servo mimo jiné nově zvládne animované obrázky APNG a WebP.

    Ladislav Hagara | Komentářů: 0
    22.8. 13:11 | IT novinky

    Na chytré telefony a počítačové tablety v Rusku bude od začátku příštího měsíce povinné předinstalovávat státem podporovanou komunikační aplikaci MAX, která konkuruje aplikaci WhatsApp americké společnosti Meta Platforms. Oznámila to dnes ruská vláda. Ta by podle kritiků mohla aplikaci MAX používat ke sledování uživatelů. Ruská státní média obvinění ze špehování pomocí aplikace MAX popírají. Tvrdí, že MAX má méně oprávnění k přístupu k údajům o uživatelích než konkurenční aplikace WhatsApp a Telegram.

    Ladislav Hagara | Komentářů: 36
    22.8. 04:22 | IT novinky

    Společnost PINE64 stojící za telefony PinePhone nebo notebooky Pinebook publikovala na svém blogu srpnový souhrn novinek. Kvůli nedostatečnému zájmu byla ukončena výroba telefonů PinePhone Pro.

    Ladislav Hagara | Komentářů: 2
    21.8. 22:22 | Nová verze

    Po pěti měsících vývoje byla vydána nová verze 0.15.1 programovacího jazyka Zig (GitHub, Wikipedie). Verze 0.15.0 byla přeskočena. Přispělo 162 vývojářů. Přehled novinek v poznámkách k vydání.

    Ladislav Hagara | Komentářů: 0
    21.8. 21:55 | Komunita

    Před sedmi lety společnost Valve představila fork projektu Wine s názvem Proton umožňující v Linuxu přímo ze Steamu hrát počítačové hry do té doby běžící pouze ve Windows. Aktuální přehled podporovaných her na stránkách ProtonDB

    Ladislav Hagara | Komentářů: 0
    21.8. 14:55 | IT novinky

    Společnost DuckDuckGo rozšířila svůj AI chat Duck.ai o GPT-5 mini (𝕏). Duck.ai umožňuje anonymní přístup bez vytváření účtů k několika modelům umělé inteligence. Aktuálně k GPT-4o mini, GPT-5 mini, Llama 4 Scout, Claude Haiku 3.5 a Mistral Small 3.

    Ladislav Hagara | Komentářů: 6
    Pro otevření více webových stránek ve webovém prohlížečí používám
     (77%)
     (8%)
     (3%)
     (5%)
     (6%)
     (0%)
    Celkem 62 hlasů
     Komentářů: 6, poslední 21.8. 13:35
    Rozcestník

    Automatický Slitherlink solver

    30.8.2010 11:33 | Přečteno: 1775× | 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 :-)
    We will destroys the Christian's legion ... and the cross, will be inverted
    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.