Eternity II pussel

Eternity II-pusslet

Eternity II-pusslet (förkortat E2 eller E II) är ett kantmatchande pussel som lanserades den 28 juli 2007. Det utvecklades av Christopher Monckton och marknadsförs och upphovsrättsskyddat av TOMY UK Ltd som en efterföljare till det ursprungliga Eternity-pusslet . Pusslet var en del av en tävling där ett pris på $2 miljoner erbjöds för den första kompletta lösningen. Tävlingen avslutades kl. 12.00 den 31 december 2010 utan att hitta någon lösning.

Beskrivning

Eternity II-pusslet är ett kantmatchande pussel som går ut på att placera 256 kvadratiska pusselbitar i ett 16 × 16 rutnät, begränsat av kravet att matcha intilliggande kanter. Det har utformats för att vara svårt att lösa med brute-force datorsökning.

Varje pusselbit har sina kanter på ena sidan markerade med olika form/färgkombinationer (här gemensamt kallade "färger"), som var och en måste matcha exakt med sin närliggande sida på varje intilliggande bit när pusslet är klart. Den andra sidan av varje bit är tom förutom ett identifieringsnummer och används inte i pusslet. Således kan varje del användas i endast 4 orienteringar. Det finns 22 färger, exklusive de gråa kanterna. Fem av färgerna finns uteslutande i de 60 kantparen ("diamanter") i den yttersta ringen, dvs mellan bården och hörnstyckena, medan de övriga 17 används i de återstående 420 "inre" kantparen. Färgerna används jämnt, var och en av de 5 kantfärgerna används i exakt 12 kantpar, och var och en av de 17 inre färgerna används för antingen 24 kantpar (5 färger) eller 25 kantpar (12 färger). Det totala antalet kantpar är 480. En av de fem kantfärgerna finns inte på någon hörnbit, medan alla de 17 inre färgerna används minst en gång på en kantbit.

Det finns 4 hörnstycken (med två grå sidor), 56 kantstycken (med en grå sida) och 14 ² = 196 inre delar (med fyra färgade sidor). Varje bit har ett unikt arrangemang av färger, och ingen av bitarna är rotationssymmetriska, så var och en av de 256 × 4 = 1024 valen av bit och orientering resulterar i ett annat mönster av kantfärger.

Pusslet skiljer sig från det första Eternity-pusslet genom att det finns en icke-valfri startbit (en obligatorisk ledtråd) som måste placeras i en specificerad position och orientering nära mitten av brädet.

Två ledtrådspussel var tillgängliga i och med lanseringen av produkten, som, om de lösts, ger varsin bitposition (tips) på huvudpusslet med 256 bitar. Clue Puzzle 1 är ett kvadratiskt (6 × 6) pussel med 36 bitar och Clue Puzzle 2 är ett rektangulärt (12 × 6) pussel med 72 delar. Två ytterligare ledtrådspussel med samma dimensioner gjordes tillgängliga 2008: det 36-delade ledtrådspusselet 3 och det 72-delade ledtrådspusselet 4. Regelboken säger att pusslet kan lösas utan att använda tipsen.

Komplexitet

Antalet möjliga konfigurationer för Eternity II-pusslet, förutsatt att alla bitar är distinkta och ignorerar de fasta bitarna med förutbestämda positioner, är 256! × 4 ²⁵⁶ , ungefär 1,15 × 10 ⁶⁶¹ . En snävare övre gräns för det möjliga antalet konfigurationer kan uppnås genom att ta hänsyn till den fasta biten i mitten och restriktionerna för bitarna på kanten: 1 × 4! × 56! × 195! × 4 ¹⁹⁵ , ungefär 1,12 × 10 ⁵⁵⁷ . En ytterligare övre gräns kan erhållas genom att överväga positionen och orienteringen av ledtrådsbitarna som erhållits genom ledtrådspusslen. I det här fallet är positionen och orienteringen av fem bitar känd, vilket ger en övre gräns på 4! × 56! × 191! × 4 ¹⁹¹ = 3,11 × 10 ⁵⁴⁵ , vilket ger ett sökutrymme 3,70 × 10 ¹¹⁵ gånger mindre än den första approximationen.

Till första approximation reducerar kantmatchningsbegränsningen antalet giltiga konfigurationer med en faktor på (1/5) för varje kantkantpar och (1/17) för varje inre kantpar. Antalet giltiga konfigurationer uppskattas då till 4! × 56! × 196! × 4 ¹⁹⁶ × (1/5) ⁶⁰ × (1/17) ⁴²⁰ ≈ 16,4, vilket är mycket nära enhet. Detta indikerar att pusslet sannolikt har utformats för att bara ha en eller ett fåtal lösningar, vilket maximerar svårigheten: fler lösningar (lösare begränsningar, t.ex. mindre färger) skulle göra det lättare att hitta en lösning (en av många), medan snävare begränsningar minskar sökutrymmet, vilket gör det lättare att hitta den (unika) lösningen. Optimering av antalet färger har undersökts empiriskt för mindre pussel, vilket bekräftar denna observation.

Konkurrens och lösning

Efter det första granskningsdatumet den 31 december 2008 meddelades att ingen fullständig lösning hade hittats. Ett pris på $10 000 tilldelades Louis Verhaard från Lund i Sverige för en dellösning med 467 matchande kanter av 480. Verhaard publicerade ytterligare tre dellösningar med samma antal matchande kanter.

Den 30 januari 2011 meddelar den officiella Eternity II-webbplatsen att "Sista datumet för den korrekta lösningen av Eternity II-pusslet passerar utan vinnare, och priset på $2 miljoner för en korrekt lösning av Eternity II-pusslet går inte att hämta."

Ingen verifierad komplett lösning på Eternity 2-pusslet har någonsin publicerats. Detta inkluderar Christopher Moncktons tänkta lösning, som förblir opublicerad. Flera falska lösningar är kända för att ha cirkulerat på nätet.

Historia och design

Det ursprungliga Eternity-pusslet var ett kakelpussel med ett miljonpris, skapat av Monckton . Det lanserades i juni 1999 och löstes av en datorsökalgoritm designad av Alex Selby och Oliver Riordan , som utnyttjade kombinatoriska svagheter i den ursprungliga pusseldesignen. Prissumman betalades ut i sin helhet till Selby och Riordan.

Ett pussel med slående likheter med båda evighetspusslen, Diamantdilemmat, med deadline 1990, 10 år före deadline för det ursprungliga evighetspusslet, har färre pusselbitar, 160 jämfört med 209 respektive 256 för de två första evighetspusslen, och ändå har Diamond Dilemma ännu inte lösts på över 25 år.

Eternity II-pusslet designades av Monckton 2005, denna gång i samarbete med Selby och Riordan, som designade ett datorprogram som genererade den slutliga Eternity II-designen. Enligt den matematiska spelentusiasten Brendan Owen verkar Eternity II-pusslet ha utformats för att undvika de kombinatoriska bristerna i det tidigare pusslet, med designparametrar som verkar ha valts för att göra pusslet så svårt som möjligt att lösa. I synnerhet, till skillnad från det ursprungliga Eternity-pusslet, finns det sannolikt bara ett mycket litet antal möjliga lösningar på problemet. Owen uppskattar att en brute-force backtracking-sökning kan ta cirka 2 × 10 ⁴⁷ steg att slutföra.

Monckton citerades av The Times 2005 när han sa:

"Våra beräkningar är att om du använde världens mest kraftfulla dator och lät den köra från och med nu till den projicerade slutet av universum, kanske den inte snubblar över en av lösningarna."

Även om det har visats att klassen av kantmatchande pussel , där Eternity II är ett specialfall, i allmänhet är NP-komplett , kan detsamma sägas om den allmänna klassen av polygonpackningsproblem, varav det ursprungliga Eternity-pusslet var ett specialfall.

Liksom det ursprungliga Eternity-pusslet är det lätt att hitta ett stort antal sätt att placera ett stort antal bitar på brädan vars kanter matchar, vilket gör att det verkar som att pusslet är enkelt. Men med tanke på det låga förväntade antalet möjliga lösningar är det förmodligen astronomiskt osannolikt att någon given dellösning kommer att leda till en komplett lösning.

Se även

TetraVex , ett liknande enklare (ingen bitrotation eller kantstycken) kantmatchande pusselspel från Microsoft Entertainment Pack , visat sig vara NP-komplett .

externa länkar

Programvara: