Čtvrtá série třicátého druhého ročníku KSP

Nelehká pandemická doba jara tohoto roku bohužel nepřála ani přípravě čtvrté série, ale již se k vám předposlední číslo jubilejního 25-tého ročníku KSPčka konečně dostává. Doufáme, že vás všechny zastihuje v co nejlepším zdraví a doufáme, že zdraví i nadále zůstanete a uvítáte vytržení od domácího učení další várkou zajímavých úloh.

Předchozí díl seriálu můžete odevzdávat až do konce dubna. V této sérii namísto seriálu přibalujeme kompetitivní úlohu, kde můžete navzájem mezi sebou poměřit schopnosti ve hledání optimálního řešení na těžkou úlohu. Zapojit se může každý, tak toho využijte! Mimo to série obsahuje další čtyři teoretické a jednu praktickou úlohu. A závěrem tohoto čísla je kuchařka o minimálních kostrách.

Připomínáme, že se z každé série stále započítává 5 nejlépe vyřešených úloh (tedy nemusíte vyřešit úplně všechny a i tak můžete dosáhnout na plný počet bodů). Také se vám body za úlohy přepočítávají podle vašeho služebního stáří – na přesnou definici se podívejte do pravidel na webu.

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50% bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, toto je poslední série, za kterou stihneme získat body, pokud potřebujete prominutí přijímaček uplatnit již letos (pokud tomu tak je, ozvěte se nám). Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, placku a možná i další překvapení.

Termín odeslání Vašich řešení této série je neděle 10. května 2020 ve 32:00 (tedy další ráno v 8:00). Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Odměna série: Třem nejúspěšnějším řešitelům kompetitivní úlohy pošleme sladkou odměnu.

Zadání úloh

V minulé sérii unikla posádka Hefaista ze základny zasažené podivnou iontovou bouří, aby následně zjistila, že část ztracených kolonistů pravděpodobně v rámci tajného výzkumu iontovou bouři vytvořila a vyslala ji proti zbytkům základny s cílem zamést stopy – tedy zbylé kolonisty a také posádku hlídkové a servisní lodi Hefaistos, která přiletěla kolonistům na pomoc.

Po dramatickém úniku (přečtěte si minulý díl) a po napíchnutí místní satelitní sítě se povedlo posádce a kolonistům zjistit souřadnice utajené základny a v hlasování o pokračování jste zvolili, že se mají pokusit přepadnout druhou tajnou základnu, protože jsme přece lepší! Tak čtěte pokračování…

* * *

„Já říkám, zaútočme na ně! Tady jsme jak sedící kachny, hned jak opadne to rušení z iontové bouře, tak nás uvidí,“ zahřměl přes celý můstek vždy bojovný mariňák Drake.

„Ale tohle není žádná válečná loď,“ oponoval mu pilot, „tohle je dobrá loď na zachycení neovladatelné lodi, průlety skrz prachové ohony komet a jinou drsnou jízdu… ale probůh, vždyť nemáme žádné pořádné zbraně, jenom protimeteorické dělo.“

„Kolonistů je na té základně nanejvýš devět – náklad sem sice propašovat mohli, ale další lidi by před kolonií neskryli. Nás je více a máme pořád plný set těžkých skafandrů do nebezpečného prostředí, ty něco vydrží. A dostatek nářadí na to propálit se několikametrovým pancířem hvězdné lodě, do té základny se můžeme dostat pěšky,“ pronesla po chvíli přemýšlení kapitánka Laren. „Navrhuji přistát vedle jejich základny a…“

Hlavní inženýr McCormack kapitánku přerušil: „Podle těhle snímků tam ale mají nějakou obrannou soustavu a pravděpodobně štítový…“

Než však stihl něco doříct, ozvalo se náhle zezadu z chodby jasné zvolání: „Tak už to hoď, vybuchne to!“

Inženýr přejel zděšeným nechápavým pohledem po ostatních a ještě než si to stihl uvědomit, už proskakoval průlezem z můstku do chodby vedoucí k prostorům pro posádku.

Vběhl do místnosti, ve které se tísnila většina shromážděných kolonistů, a pátral očima po něčem, co by mohlo vybuchnout. Výbuch na lodi ve vesmíru mohl mít fatální následky! Pak se ale zarazil, pohlédl na kolonisty v kroužku, rozchechtal se a svalil se smíchy na zem – kolonisté hráli pro ukrácení času hru!


Teoretická úloha32-4-1 Výbušné koťátko (9 bodů)


Kolonisté se pro ukrácení času rozhodli zahrát si hru – jedno z dětí z kolonie si s sebou totiž vzalo kulatou hračku v podobě koťátka, kterou si hráči hází a koťátko vždy po náhodné době „vybuchne“ a postříká toho, kdo ho právě drží, obarvenou vodou. Ten ze hry vypadává a ostatní hrají dál.

Bohužel tato hračka už byla stará a náhodné odpočítávadlo přestalo být náhodné. Teď se stávalo, že koťátko vždy „vybuchne“ po stejné době, která akorát stačí na to, aby si koťátko hodilo K hráčů.

Kolonistům to ale zjevně nevadí. N hráčů si stoupne do kroužku, nultý hráč koťátko spustí a hodí hráči po své levici. Ten ho opět hodí hráči po své levici a to se opakuje tak dlouho, než je koťátko hozeno K-krát – v náručí K-tého hráče „vybuchne“ a ten tak vypadává ze hry a vystupuje z kroužku ven. Přitom ale koťátko opět spustí a hodí ho opět hráči po své levici (a po K přehozeních opět vybuchne).

Postupně vypadávají všichni hráči, až zbude samotný poslední hráč, který vyhrává. My bychom chtěli vyhrát – zajímalo by nás tak, na jakou pozici se postavit v kroužku N hráčů, když víme, že koťátko „vybuchne“ u každého K-tého hráče. A chtěli bychom to spočítat rychleji, než to odsimulovat za NK kroků.

Řešení

Po tomto výbušném rozptýlení se posádka spolu se ředitelem kolonie opět vydali k plánovacímu stolu. Rychle se dohodli, že útok na cizí základnu je nezbytný. Pokusí se s Hefaistem co nejrychleji přistát, vyslat přepadové komando v těžkých skafandrech.

Základna měla obranný systém a nějaký set štítových emitorů. Hefaistos měl jen protimeteorické dělo, které se ale nabíjelo na plný výkon tak dlouho, že byl čas jen na jeden pořádný výstřel. Pilot s inženýrem připravili program, který měl při sestupu vybrat ten nejlepší cíl a vystřelit na něj.

Dva další technici, kapitánka a oba mariňáci se mezitím navlékli do těžkých skafandrů a připravili se u hangárového otvoru společně s nákladní plošinou obtěžkanou plazmovými řezáky a další technikou na vyrábění děr do dveří. Zbytek posádky se oblékl do lehčích skafandrů a i kolonisté každý dostali nouzový skafandr, kdyby se něco stalo.

Pak se na odvrácené straně planety zažehly hlavní motory Hefaista a nasměrovaly ho na prudkou sestupovou trajektorii. Hefaistos se roztřásl, ale držel pevně – na tvrdé vstupy do atmosféry byl přeci dělaný. Bez varování se loď vyřítila z noční polokoule do oslepujícího světla místního slunce, ale nic si z toho nedělala. Senzory začaly pátrat po naprogramovaných cílech. Kolem náhle proletěl soustředěný výboj energie, ale loď minul. Senzory teď už ale věděly, po čem se dívat. S metodickou přesností zaměřovaly jednotlivé energetické stopy na povrchu. Systém věděl, že má jenom jeden výstřel, a tak stále propočítával. Kolem proletěl druhý energetický výboj, ale i ten loď na sestupové dráze minul.


Teoretická úloha32-4-2 Jeden výstřel (10 bodů)


Kuchařková úloha

Senzory Hefaista zaznamenaly na povrchu u cizí základny soustavu pospojovaných energetických bodů zajišťujících obranu této základny. Body tvoří vrcholy pomyslného grafu a spoje mezi nimi pak jeho (neorientované) hrany. Soustava bodů nemusí být nutně souvislá, může tvořit více samostatných komponent.

Jednotlivé spoje (neboli hrany) přispívají do energetické soustavy různou silou. Každý spoj je ohodnocený kladným číslem a při čerpání energie ze soustavy se pak sečte energie spojů na minimální kostře zkonstruované podle těchto ohodnocení. Pokud soustava není souvislá, tak se spočítá minimální kostra v každé komponentě samostatně a výsledná energie je pak součet energií všech minimálních koster.

Hefaistos má protimeteorické dělo, které ale stihne vystřelit jen jednu ránu, kterou zvládne přerušit jeden spoj (jednu hranu v grafu). Vymyslete algoritmus, který určí v grafu takový spoj, jehož odstraněním se co nejvíce sníží energie celé energetické soustavy.

Příklad energetické soustavy a odstraněného spoje

Například na energetické síti z levé části obrázku vychází nejlépe přerušit spoj s ohodnocením 3, výsledné kostry s celkovou energií 11 jsou pak vyznačeny v pravé části obrázku. Kdybychom namísto toho přerušili například spoj s ohodnocením 4, tak si vůbec nepomůžeme a výsledná energie zkonstruované kostry dokonce vzroste na 18.

Řešení

Protimeteorické dělo na Hefaistu se zacílilo a pak lodí lehce trhlo, když vypustilo plazmový výboj na přesně vybrané místo energetické sítě u cizí základny. Spoj se s oslepujícím zábleskem rozletěl do okolí, štíty základny pohasly a Hefaistos se již obracel ke kruhovému obletu a vysouval přistávací nohy, když se proti němu rozletěl třetí energetický výboj z děla u základny. Tentokrát již neminul.

Proud energie proletěl pravou zadní částí Hefaista, utrhl část motorové sekce a prošel obálkou jeho fúzního reaktoru. Nouzové pojistky a pyropatrony, které byly hluboko do Hefaistova trupu instalovány před dlouhými lety v loděnici, v mžiku sekundy odstřelily zbylé plátování trupu a vymrštily selhávající fúzní reaktor co nejdál od lodi. Stihly to, na poslední chvíli. Reaktor se roztrhl až třicet metrů od trupu. Loď obklopil proud superpřehřáté plazmy o teplotě menšího slunce, který spaloval, co mu přišlo do cesty. Ohořelý ale stále celistvý hlavní trup Hefaista se z ohnivé koule vynořil o sekundu později a řítil se v kotrmelcích k povrchu.

Další z nouzových systémů odolné lodě zafungoval na výbornou a vnitřní prostory posádky okamžitě zaplavila extrémně expanzní vysokoporézní balistická pěna, která bleskově tuhla a chránila svůj cenný lidský náklad před nejhoršími nárazy. Hlavní počítač se po poškození svého jádra zasekl v nějaké smyčce vypisující na obrazovky na můstku sled chybových hlášení E3, F5, E7, G6. Ale jeho práci převzaly záložní počítače, jejichž jedinou starostí byla stabilizace lodi před dopadem. Nějakým zázrakem se jim povedlo loď pomocí trysek přetočit opět do polohy na břicho a se zbytky kdysi devítisettunové devadesátimetrové lodě přistát klouzavým pohybem – jestli se přistáním dá nazývat prudký náraz do země s odskočením a vyrytím třísetmetrové brázdy.

* * *

Balistická pěna uchránila posádku před nejhorším, i když asi nikdo nevyvázl bez alespoň lehkého zranění nebo pohmoždění. Brzy se rozsvítila nouzová světla a jednotliví lidé začali prudkými pohyby drtit pěnu, která je fixovala na jejich místech a nyní se začala rozpadat.

Hlavní inženýr se pokoušel rychle se probojovávat rozpadající se ztuhlou pěnou, než se dostal přes prostor osádky do hangáru, kde čekalo přepadové komando. Ti byli naštěstí uchráněni svými těžkými skafandry a všichni vypadali v pořádku, ale dveře se odmítaly otevřít. A to ani na manuální ovládání, i když do nich energie očividně šla. Hlavní inženýr rychle odtrhl krycí panel a podíval se na spálenou elektronickou destičku řídícího mechanismu. Odněkud magicky zhmotnil páječku a dal se do nouzové opravy.


Teoretická úloha32-4-3 Sběrnice na pájivém poli (12 bodů)


Hlavní inženýr potřebuje opravit řídící destičku od mechanismu otevírání dveří. Destičku si můžeme představit jako pájivé pole, což je většinou nějaká mřížka R×S kontaktů, kde můžeme pomocí pájení propojovat kontakty do cestiček.

Kdo pájivé pole neznáte, vyhledejte si na internetu obrázky. Pro naše potřeby stačí vědět, že lze na pájivém poli vytvořit cestička z „políček“ sousedících hranou (každé políčko mimo krajních tak má 4 sousedy).

Některá políčka na řídící destičce jsou již obsazena různými součástkami. Hlavní inženýr by ale potřeboval protáhnout po destičce od její vrchní hrany k její spodní hraně co nejširší sběrnici. Sběrnici představuje několik cestiček, které vedou po pájivém poli těsně vedle sebe a nikde se nerozcházejí, jak ukazuje například následující obrázek (tečky jsou středy políček, různé součástky představují plná políčka, tmavě je vyznačená sběrnice).

Příklad sběrnice na pájivém poli

Vymyslete algoritmus, který na vstupu dostane mapu volných políček na nepájivém poli a zjistí, jakou nejširší sběrnici (kolik cestiček vedle sebe) můžeme po volných políčkách nepájivého pole protáhnout od jeho horního ke spodnímu okraji. Sběrnice široká K musí začínat na K vedle sebe ležících volných políčkách na prvním řádku a končit na K vedle sebe ležících volných políčkách na posledním řádku.

Nezapomeňte v této úloze dokázat, že vaše řešení vždy vrátí optimální výsledek (že nemůže existovat sběrnice s více cestičkami).

Řešení

Hlavní inženýr odložil páječku, zasunul opravenou destičku zpět do slotu a praštil rukou do tlačítka nouzového otevírání. Těžké dveře chvíli vzdorovaly, protože vnější obšívka trupu byla výbuchem fúzního reaktoru spečena do celistvé skořápky, ale pak se skřípavým trhnutím hydraulické vzpěry skořápku prolomily a do lodi se vehnalo denní světlo.

Přepadové komando příliš nečekalo a v těžkých skafandrech se okamžitě vrhlo ven. Dva technici za sebou táhli nákladní plošinu naloženou užitečnými nástroji.

Vypadalo to, že zásah protimeteorického děla a padající trosky z Hefaista základnu celkem poničily – na hlavní budově zapuštěné do skalního masivu svítila zvenku jen nouzová světla a z některých míst základny se kouřilo. Štítový generátor i všechny obranné systémy vypadaly neaktivní – otázkou ale bylo, jak dlouho to vydrží.

V půlce cesty překvapilo komando trojici lidí v lehkých skafandrech, kteří se pravděpodobně vydali na průzkum vraku – nenapadlo je asi, že by takový pád mohl někdo přežít, nečekali, že loď bude tak odolná. Když zahlédli pětici mohutných postav, z nichž dvě svíraly nějaké zbraně, tak se na místě bez odporu vzdali. Mariňáci je jen svázali a kapitánka mezitím zavolala vysílačkou na Hefaista, aby pro ně někdo došel. Nebyl čas se zastavovat, na základně stále někde bylo šest bývalých obyvatel kolonie.

Po několikasetmetrovém přesunu dorazili k hlavním dveřím zasazeným do skalního masivu. „Prořezat tohle bude trvat aspoň hodinu, možná i víc,“ zhodnotil stav dveří jeden z techniků. Druhý technik, lodní expert na počítače Jason, mezitím napojil přenosný terminál na datový port u panelu dveří.

„Nejsou zakódované, jenom blokují otevírací signál z tohoto panelu“, trhnul hlavou k ovládání vedle dveří. „Můžu se pokusit poslat otevírací signál smyčkou přes jiné panely… ale oni ten signál taky okamžitě blokují. Musím najít nejkratší cestu zpět.“


Praktická opendata úloha32-4-4 Zpětný signál (10 bodů)


Pro vniknutí do základny by přepadový tým potřeboval otevřít hlavní vstupní dveře. Signál pro jejich otevření z lokálního panelu je ale blokován, je nutné signál poslat oklikou přes jiné počítače v síti.

Současně se ale osazenstvo základny brání a signály na otevření dveří blokují. Potřebovali bychom tedy najít co nejrychlejší cestu sítí zpět k našemu panelu, aby měli co nejmenší šanci ho zastavit.

Počítačová síť je tvořena jednotlivými uzly (řídící panel u vstupních dveří je jedním z nich), které jsou spojeny jednosměrnými komunikačními linkami. Navíc každá linka má jinou rychlost přenášení signálu, u každé komunikační linky tedy dostaneme číslo v milisekundách, jak dlouho trvá signálu přejít přes tuto komunikační linku do dalšího počítačového uzlu.

Naším cílem je tedy najít cestu, která začíná u našeho řídícího panelu, projde nějakou cestou sítí po komunikačních linkách a vrátí se nazpět do našeho panelu. Ze všech takových cest by měla být nejkratší.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu dostanete dvě čísla N a M udávající počet počítačů v síti a počet jednosměrných komunikačních linek mezi nimi. Na druhém řádku pak bude jedno číslo S udávající index řídícího panelu, ze kterého chceme vyslat signál a do kterého chceme, aby se signál nakonec vrátil. Na dalších M řádcích pak budou vždy trojice čísel a, b, x udávající, že z počítače a existuje přímá komunikační linka do počítače b a přenést po ní signál trvá x milisekund. Počítače indexujeme od nuly. Zaručujeme, že vstup nebude obsahovat smyčky (tedy vždy a≠ b) a že všechna x budou kladná.

Formát výstupu: Na první řádek výstupu vypište délku (v milisekundách) vámi nalezené nejkratší cesty vedoucí z vrcholu S zpět do vrcholu S. Na druhý řádek vypište počet počítačů na této cestě (počítaje počáteční i koncový) a na další řádek vypište mezerami oddělenou posloupnost indexů počítačů na této cestě.

Ukázkový vstup:
5 8
2
0 2 2
1 0 3
1 4 1
2 1 2
2 3 3
3 4 1
4 0 1
4 2 4
Ukázkový výstup:
6
5
2 1 4 0 2
Znázornění ukázkového vstupu

Řešení

Po Jasonově konzoli běhaly proudy písmen. Technik se pod hledím těžkého skafandru potil, ale nakonec vítězoslavně zvedl hlavu a ťukl do potvrzovací klávesy. Chvíli se nic nedělo, ale pak se hlavní dveře lehce zasunuly do podlahy a odhalily vstup do přechodové komory.

Pětičlenná skupinka vstoupila dovnitř. Vnitřní dveře přechodové komory již nebyly nijak blokované a hladce se před nimi otevřely. Ocitli se v krátké chodbě s několika bočními místnostmi – vnitřní prostory této základny nebyly příliš rozlehlé. Největší utěsněnou místností byl hangár spojený s dílnou, kde zrovna pracovali na úpravě jedné z družic, a pak sekce s několika laboratořemi, ve kterých to sršelo blesky. S utěsněným hangárem ještě sousedil větší neutěsněný hangár, ve kterém objevili malou transportní loď, kterou pravděpodobně vynášeli družice na oběžnou dráhu.

Na druhé straně základny pak byla obytná část a řídící centrum. Netrvalo dlouho a mariňákům se povedlo najít všech šest zbývajících obyvatel základny. Nikdo z nich očividně nebyl voják a podle některých nalezených papírů to celé byla akce velké korporace, která částečně financovala i výstavbu celé kolonie. Kapitánka Laren si v duchu oddechla – aspoň že to není nějaká tajná akce koloniální armády.

Poté, co do základny přivedli z havarovaného Hefaista všechny kolonisty, se ředitel kolonie přišel podívat na vězně.

„Taylore, jak jen jsi mohl? Co jste tu probůh dělali a proč?“ nemohl uvěřit tomu, že člověk, jehož ještě před měsícem považoval pouze za jednoho z geologů kolonie, kteří rádi vyráželi na dlouhé výpravy do pustiny, šéfuje nějaké skupině vědců zahrávajících si s iontovými bouřemi.

Než však mohl pokračovat, přerušilo všechny hlasité zakvílení alarmu od hlavní přehledové mapy. Po chvíli zkoumání a vyzvídání od zajatých vědců zjistili, že na celé planetě se v několika uzavřených stanicích „pěstují“ iontové bouře držené na místě a posilované magnetickými silovými paprsky. A stanice nejblíže této základně vlivem poškození energetické sítě zkolabovala a je potřeba ji opět nahodit.


Teoretická úloha32-4-5 Svázání bouře (13 bodů)


Iontová bouře byla držena ve své „líhni“ pomocí magnetických silových paprsků generovaných na přímých spojnicích mezi emitory. Každý emitor zvládne generovat i více magnetických silových paprsků, ale nikdy se žádné dva magnetické silové paprsky nesmí křížit (podle staré zásady „Nikdy nekřižte paprsky!“ by mohlo dojít až ke konci světa, nebo minimálně ke konci daných emitorů).

Známe souřadnice jednotlivých emitorů v rovině. Chceme naplánovat, mezi kterými dvojicemi emitorů budeme generovat paprsky tak, aby platilo:

  • Žádné dva paprsky se nekříží.
  • Neexistuje žádná dvojice emitorů, mezi něž bychom ještě mohli přidat paprsek tak, aniž by se porušila první podmínka.

Vymyslete algoritmus, který pro zadané souřadnice vydá dvojice emitorů, mezi kterými generovat paprsky, aby byly podmínky výše splněné. Vaše řešení nemusí obsahovat co nejvíce paprsků, ani paprsky nemusí tvořit žádný speciální tvar. Jde jen o to, že tam již nepůjde žádný další paprsek přidat.

Řešení

Iontovou bouři se povedlo opět svázat do její „líhně“. Podle všeho byly tyto líhně na planetě celkem čtyři a dvě z nich teď držely připravené iontové bouře (jedna iontová bouře byla použita na prvotní poničení kolonie a druhá pak na druhý útok na kolonii, vyrobit nové prý trvá několik měsíců).

Byli teď ale v nezáviděníhodné situaci. Na planetě byly dvě subprostorové vysílací stanice – jedna z nich na vážně poškozeném Hefaistu bez fůzního reaktoru zabořeném do země a druhá na hlavní základně kolonie, která byla prakticky smetena z povrchu planety. Navíc v této malé základně nebylo dostatek prostoru ani jídla, aby zvládla všechny kolonisty i posádku. Před posádkou Hefaista a před kolonisty tak stálo (již poslední) náročné rozhodnutí. Co dělat teď? Opět zahlasujte v anketě.

* * *

Možná vám vrtá hlavou, v jaké smyčce že se to zasekl hlavní počítač Hefaista po poškození lodě při sestupu. K vysvětlení této části příběhu se musíme vrátit zhruba dvacet minut před zahájením útoku na cizí základnu, dokud byl Hefaistos ještě na oběžné dráze.

V tu chvíli se dva kolonisti, shodou náhod nejmladší a nejstarší ze všech kolonistů, rozhodli ukrátit si čekání na další vývoj situace nějakou hrou. Hra s výbušným koťátkem je přestala bavit a tak si mladý Tom spustil na jednom z panelů na stěně své oblíbené sudoku. A starý Azachiáš si zase chtěl zahrát partii šachů proti lodnímu počítači.

V tu chvíli se ale objevila v sekci pro posádku kapitánka a začala vysvětlovat detaily nadcházející akce. Tom i Azachiáš nechali hry na panelech spuštěné a úplně na ně zapomněli.

Jenže hlavní počítač ne. V momentě jeho kritického poškození došlo k pomíchání běžících programových bloků, přepsání paměti procesů a ke spojení programů pro řešení sudoku a hraní šachů do jednoho. A v této smyčce hlavní počítač stále běží, napájen z nouzových článků na Hefaistovi…


Teoretická úloha32-4-6 Sudoku s koněm (15 bodů)


Toto je optimalizační kompetitivní úloha – na problém, který vám zde ukážeme, pravděpodobně neobjevíte optimální algoritmus, který by vám našel nejlepší možný výsledek. Ale můžete se pokusit najít dostatečně dobrý výsledek – nejlépe takový, který bude lepší, než výsledky všech ostatních řešitelů.

Bodovat tuto úlohu budeme tak, že nejlepší řešení dostane plný počet bodů a ostatní dostanou body odstupňovaně podle toho, jak dobrého skóre dosáhnou. Vše vyhodnotíme po konci série. A přidáme i nějaká referenční organizátorská řešení :)

Úloha

Pro sudoku, neboli mřížku 9×9, existuje posloupnost tahů šachovým jezdcem, která navštíví každé políčko právě jednou (bude tak mít právě 81 kroků), nemusí se však vrátit na startovní pozici. Takové posloupnosti často říkáme otevřená jezdcova procházka a najít jí není tak těžké. Také je to pouze jedna z částí naší úlohy.

Pro nějaké vyřešené sudoku a pro konkrétní procházku jezdcem definujme skóre jako posloupnost 81 cifer v pořadí, v jakém na ně jezdec na vyřešeném sudoku vstoupí.

Příkladem může být třeba následující sudoku s následujícím pořadím návštěv jezdcem (začínáme na nule) a následujícím skóre:

1 2 3 8 7 4 5 6 9
8 4 5 1 9 6 7 2 3
6 7 9 2 3 5 1 4 8
2 1 4 7 5 9 8 3 6
3 9 6 4 8 1 2 7 5
7 5 8 6 2 3 9 1 4
9 6 2 3 1 8 4 5 7
4 8 1 5 6 7 3 9 2
5 3 7 9 4 2 6 8 1

80 77 50 41 52 73 70 43 12
49 40 53 78  3 42 11 72 69
76 79  2 51 74 71 44 13 10
39 48 75 54 57  4  9 68 65
30  1 58 47  8 55 66 45 14
23 38 29 56 59 46  5 64 67
 0 31 24 35 28  7 60 15 18
37 22 33 26 61 20 17  6 63
32 25 36 21 34 27 62 19 16
999999988887945513787987235218365143745248661734183275716562466216243355243462171

Vaším úkolem je najít takové vyřešené sudoku, na kterém půjde najít procházku takovou, která dá co nejvyšší skóre (když budeme skóre chápat jako číslo o 81 cifrách).

Pro řešení sudoku klidně můžete použít externí knihovny či nějaké weby, není naším cílem zkoušet vás z napsání solveru na sudoku. Ale napište nám prosím odkaz na použité nástroje do řešení.

Co odevzdávat

Budeme po vás chtít jednak co nejvyšší nalezené skóre (a sudoku s procházkou, které k němu vedou), ale také slovní popis řešení říkající, jakou cestou jste k výsledku došli. Můžete přibalit i zdroják programu či sbírku skriptů, které jste použili.

Upozorňujeme, že bez slovního popisu a vysvětlení, jak jste k výsledku došli, nebudeme výsledky uznávat. Pamatujte na to.

Své řešení odevzdávejte jako ZIP obsahující:

  • Soubor sudoku.txt se zápisem sudoku ve formátu jako výše (9 řádků, čísla oddělená mezerami)
  • Soubor prochazka.txt s procházkou ve formátu jako výše (9 řádků, čísla oddělená mezerami)
  • Soubor skore.txt s 81-ciferným skóre získaným z procházky
  • Slovní popis řešení (třeba v PDF) a případně jakékoliv další použité programy.
U prvních tří souborů se prosím pokoušejte držet zadaného formátu, velmi nám to usnadní kontrolu. Děkujeme.

Řešení

Čtvrtý díl příběhu pro vás sepsal

Jirka Setnička