A könyv végén, a „Harry Potter és a bölcsek köve” című műben, egy érdekes rejtvény található. Harry és Hermione belépnek egy szobába, amelynek bejáratait varázslatos tűz zárja el, és csak az alábbi rejtvény megoldásával tudnak kijutni belőle:
Előtted a veszély, mögötted a megmenekülés,
Kettő segít neked, akiket köztünk találsz;
Az egyik hétből előre visz tovább az utad,
A másik pedig azonnal hátra repít téged.
Kettő közülünk csak csalánbort rejt,
A hárman halált hoznak, titokban állnak sorban.
Tehát válassz, melyiket kívánod megízlelni,
Ehhez négy nyomot adunk.
Felesleges, hogy a méreg próbálja eltakarni halálos hevét,
Mindig balra találod a bort,
Tudjad, hogy akik a szélek közt állnak, különböző ajándékokat rejtenek,
De ha tovább akarsz jutni, egyik sem segít.
Mérjük meg mindannyian, milyen méretűt, a szélétől a széléig,
Nem kisebb, de nem is nagyobb a te halálod itt;
A második a jobb szélén és a bal szélen is második,
Ízben mint az ikrek, bár kinézetük eltérő.
[a „népi fordításból” a „Harry Potter és a bölcsek köve” című könyvből]
Egyszerűbben fogalmazva, meg kell érteniük, melyik palackban milyen főzetek vannak.
Ebben a cikkben 42 lehetséges megoldást fogunk kidolgozni ehhez a rejtvényhez programozás segítségével, és elkészítünk egy diagramot az eredményekről (mint a fenti képen, csak sokkal nagyobb méretben).
Egy pillanat, honnan jöttek a 42 variáns?
Mindez azért van, mert a „kisebb” és a „nagyobb” főzetek elhelyezkedését nem jelölték meg. A nagyobb bármelyik hét hely egyikén lehet, ami hat maradék variációt ad a kisebbnek, tehát 7 * 6 = 42. Kideríteni, hogy Joan Rowling mely elrendezést gondolta, amikor ezt a rejtvényt találta ki, nem lehetséges, hacsak ő erről nem mesél a Twitterén. De amíg ez a visszafordíthatatlan nap el nem jön, választhatunk véletlenszerű verziót, és dolgozhatunk vele. Azonban garanciát arra, hogy megoldható lesz, nem tudunk adni, ezért dolgozunk a közjóért, megoldva a rejtvény 42 variánsát (vagy bizonyítva azok megoldhatatlanságát).
MÁR OLD MEG
Először is, itt vannak a rejtvény összes korlátozása, egyszerűsített formában átírva:
- Van két ártalmatlan főzet, 3 mérgezett, egy, ami előrejutást biztosít, és egy, ami hátrafelé visz.
- Minden ártalmatlan főzet bal oldalán egy mérgezett áll.
- A két oldalon lévő italok különböznek, és egyik sem engedi átjutni az embert.
- A legnagyobb és legkisebb üveg nem tartalmaz mérget.
- A bal oldali második üveg és a jobb oldali második üveg ugyanolyan italt tartalmaznak.
Mit kezdjünk ezzel? Nézzünk meg egy következő lehetőséget. Érdemes megjegyezni, hogy a rejtvény szerint a sorban van 1 üveg, ami kisebb mint a többi, és 1 üveg, ami nagyobb mint a többi.
Megpróbáljuk egyszerűen végigpróbálni az összes lehetőséget - egy üveget venni, és az összes lehetséges tartalmat összeilleszteni.
Például az első üvegben nem lehet olyan ital, ami előre visz minket a 3. korlátozás miatt. Emellett nem tartalmazhat biztonságos italt a 2. korlátozás miatt - mellette nem lehet méreg. Ez lehetővé teszi számunkra a mérgezett ital és a visszafelé haladó ital lehetőségeit. Próbáljuk ki mindkettőt.
A következő képeken a zöld italok mérget jelentenek, a narancssárgák biztonságos italokat, a kékek visszafelé haladó italokat, a lilák pedig előre haladókat.
Ismételjük meg ezt a folyamatot mindkét működő lehetőséggel - vegyük a második üveget, és felváltva próbáljuk ki az összes megengedett tartalmat. Ez a következőt adja nekünk:
A részletes vizsgálat során, és az összes munkatehetőséget elvetve, amelyek esetén valamilyen üveget nem lehet itallal megtölteni anélkül, hogy megsértsük a felsorolt korlátozásokat, eljutunk az egyetlen megengedett lehetőséghez:
Természetesen nem volt garanciánk arra, hogy találunk megoldást. Lehet, hogy nem volt megoldás, vagy több is lehetett (ha van több megoldás, az egyenlő azzal, hogy a rejtvényt nem lehet megoldani, mivel nem ismert, melyik ital a helyes).
Az algoritmus alkalmazása minden lehetőségre a következő megoldásokat adja. 8 megoldható rejtvényvariáció van, 8-nak nincs megoldása, és 26-nak van több megoldása.
További részletek a megoldásokról
Van-e közös vonás az összes megoldható rejtvény között? Igen! Figyeljünk arra, hogy a legkisebb vagy legnagyobb palack a 2. vagy a 6. helyen áll. Ez lehetővé teszi számunkra, hogy arra a következtetésre jussunk, hogy a 2. és a 6. palack biztonságos italokat tartalmaz a 4. és 5. számú korlátozások miatt. E lépés nélkül nem tudjuk kizárni a lehetőségét annak, hogy ezekben a palackokban méreg van, és végül több lehetséges megoldáshoz jutunk. A megoldható változatok azt is megkövetelik, hogy a második „különleges” palack (legkisebb vagy legnagyobb) a 3. vagy 4. helyen álljon. Különben nem találjuk meg az előre mozdító ital pontos helyét.
Összegzés
Befejezem egy idézettel a könyvből.
Hermione sóhajtott, és Harry ámulva vette észre, hogy mosolyog – ez volt az utolsó óra, ami eszébe jutott. „Zseniális – mondta Hermione. – Ez nem varázslat – ez logika, rejtvény. Sok nagyszerű varázslónak egy gramm logikája sincs, és ők örökre itt ragadnának.”
De várj – talán meg fogjuk érteni a rejtvény kanonikus változatát a könyvből vett párbeszéd alapján:
„Megértettem – mondta. – A legkisebb palack átvezet minket a fekete tűzön és a Kőhöz.”
…
„De melyik ad majd vissza a lila tűzön?”
Hermione a jobb oldalán lévő kerek palackra mutatott.
A fenébe. Ez a lehetőség még mindig több megoldást ad nekünk. Írjatok tweeteket, D.R.
Kód
Ha érdekel a kód a rejtvény megoldásához és a diagramok készítéséhez, azt .
Forrás: habr.com
