I slutningen af bogen "Harry Potter og De Vises Sten" er der en interessant gåde. Harry og Hermione kommer ind i rummet, hvorefter indgangene til det blokeres af magisk ild, og de kan kun forlade det ved at løse følgende gåde:
[fra "folkeoversættelsen" af bogen "Harry Potter and the Philosopher's Stone"]Foran dig er fare, og bag dig er frelse,
To vil hjælpe dig, som du finder iblandt os;
Med en af de syv fremad vil du fortsætte med at bevæge dig
Den anden vil bære dig tilbage med det samme.
Hos to af os finder du kun nældevin,
Og tre bringer døden, står på række i hemmelighed.
Så vælg hvilken du er bestemt til at smage,
For at gøre dette giver vi fire tips.
Forgæves forsøgte giften at skjule sin dødelige varme,
Du vil altid finde den til venstre for vinen,
Og ved, at de, der er på kanten, har en anden gave,
Men hvis du vil gå længere, vil ingen hjælpe.
Vi adskiller os i størrelse alt, fra kant til kant,
Din død sidder ikke i en mindre, men heller ikke i en større;
Anden fra højre ende og anden fra venstre
De smager som tvillinger, selvom de ser anderledes ud.
Kort sagt skal de finde ud af, hvilke flasker der indeholder hvilke potions.
I denne artikel vil vi løse alle 42 mulige varianter af dette puslespil ved hjælp af programmering og tegne en graf over resultaterne (som billedet ovenfor, kun meget større).
Vent et øjeblik, hvor kom 42 muligheder fra?
Dette skyldes, at placeringen af de "mindre" og "større" potions ikke er angivet. Den større kan være et af syv steder, hvilket giver 6 resterende muligheder for den mindre, for i alt 7 * 6 = 42. Det vil ikke være muligt at finde ud af præcis hvilken ordning J.K. Rowling havde i tankerne, da han kom op. med denne gåde, medmindre hun fortæller om det på din twitter. I mellemtiden, indtil den uundgåelige dag kommer, kan vi vælge en tilfældig version og arbejde med den. Der vil dog ikke være nogen garantier for dets løselighed, og derfor arbejder vi for det fælles bedste ved at løse alle 42 varianter af puslespillet (eller bevise deres uløselighed).
JA BESTEM ALLEREDE
For det første er her alle begrænsningerne i puslespillet, omformuleret på en enkel måde:
- Der er to harmløse eliksirer, 3 forgiftede, en der giver dig mulighed for at gå fremad, og en der giver dig mulighed for at gå tilbage.
- Til venstre for hver af de to harmløse potions er en giftig.
- Drikkerne på begge sider er forskellige, og ingen af dem giver dig mulighed for at gå fremad.
- De største og mindste flasker indeholder ikke gift.
- Den anden flaske til venstre og den anden flaske til højre indeholder den samme drik.
Hvordan skal man håndtere det? Overvej følgende mulighed. Bemærk, at der, som gåden siger, i rækken er 1 flaske mindre end alle de andre i størrelsen, og 1 flaske større end alle de andre.
Lad os prøve at gå dumt igennem alle mulighederne - tag en flaske ad gangen og vælg alle mulige muligheder for indholdet.
For eksempel kan den første flaske ikke indeholde en potion, der flytter os frem på grund af begrænsning #3. Den indeholder heller ikke en sikker drik på grund af begrænsning #2 - ingen gift kan placeres til venstre for den. Dette efterlader os med mulighederne for Poisoned Potion og Returning Potion. Lad os prøve begge muligheder.
På de følgende billeder er grønne potions gift, orange potions er sikre drikke, blå potions bevæger sig bagud, og lilla potions bevæger sig fremad.
Lad os gentage denne proces for begge arbejdsmuligheder - tag den anden flaske og prøv skiftevis alle de gyldige indholdsmuligheder. Dette vil give os følgende:
Hvis vi fortsætter i denne retning og kasserer alle arbejdsmuligheder, hvor en flaske ikke kan fyldes med en eliksir uden at overtræde de anførte begrænsninger, kommer vi til den eneste acceptable mulighed:
Vi havde naturligvis ingen garantier for at finde en løsning. Der er muligvis ikke en løsning, eller der kan være mere end én (og hvis du har flere løsninger, svarer det til, at gåden ikke kan løses, da det ikke vides, hvilken af eliksirerne der er korrekte).
Anvendelse af algoritmen på alle varianter giver os følgende løsninger. 8 puslespilsmuligheder kan løses, 8 har ingen løsninger, og 26 har flere løsninger.
Mere om løsninger
Er der noget til fælles mellem alle de løste varianter af puslespillet? Ja! Bemærk venligst, at i dem er de mindste eller største flasker på 2. eller 6. pladser. Dette giver os mulighed for at konkludere, at 2. og 6. flaske indeholder sikre eliksirer på grund af restriktioner #4 og #5. Uden dette trin kan vi ikke eliminere muligheden for, at disse flasker indeholder gift og ender med flere mulige løsninger. Også løste muligheder kræver, at den anden "særlige" flaske (mindste eller største) er på 3. eller 4. plads. Ellers kan den nøjagtige placering af den eliksir, der bevæger os fremad, ikke findes.
Resultaterne af
Jeg slutter af med et citat fra bogen.
Hermione åndede højt, og Harry blev overrasket over at se, at hun smilede – det var det sidste, han kunne komme i tanke om. "Strålende," sagde Hermione. "Det er ikke magi - det er logik, en gåde. Mange af de største tryllekunstnere har ikke et gram logik, og de ville sidde fast her for evigt."
Men hey, måske kan vi finde ud af den kanoniske version af puslespillet baseret på dialogen fra bogen:
"Forstået," sagde hun. "Den mindste flaske vil tage os gennem den sorte ild og til Stenen."
...
"Hvem vil lade dig vende tilbage gennem den lilla ild?"
Hermione pegede på en rund flaske i højre side af rækken.
For pokker. Denne mulighed giver os stadig flere løsninger. Tweet, DR.
Kode
Hvis du er interesseret i koden til at løse dette puslespil og tegne diagrammer, kan du .
Kilde: www.habr.com