ปริศนาEternity II ( E2หรือE II ) เป็นปริศนาจับคู่ขอบที่เปิดตัวเมื่อวันที่ 28 กรกฎาคม พ.ศ. 2550 ^{[ 1 ] [ 2 ]} ปริศนา นี้ได้รับการพัฒนาโดยChristopher Moncktonและทำการตลาดและจดลิขสิทธิ์โดยTOMY UK Ltd ในฐานะผู้สืบทอดของปริศนา Eternity รุ่นดั้งเดิม ปริศนานี้เป็นส่วนหนึ่งของการแข่งขันที่มีรางวัล 2 ล้านดอลลาร์สหรัฐสำหรับผู้ที่แก้ปริศนาได้ครบเป็นครั้งแรก การแข่งขันสิ้นสุดลงเวลาเที่ยงของวันที่ 31 ธันวาคม พ.ศ. 2553 โดยไม่มีผู้ใดแก้ปริศนาได้

ปริศนา Eternity II เป็นปริศนาจับคู่ขอบที่ต้องวางชิ้นส่วนปริศนาสี่เหลี่ยมจัตุรัส 256 ชิ้นลงในตารางขนาด 16 × 16 โดยมีข้อจำกัดคือต้องจับคู่ขอบที่อยู่ติดกัน ปริศนานี้ถูกออกแบบมาให้ยากต่อการค้นหาด้วยคอมพิวเตอร์แบบใช้กำลังทั้งหมด (brute-force)

ชิ้นส่วนจิ๊กซอว์แต่ละชิ้นจะมีขอบด้านหนึ่งที่ทำเครื่องหมายด้วยรูปทรง/สีที่แตกต่างกัน (เรียกรวมกันว่า "สี" ในที่นี้) ซึ่งแต่ละสีจะต้องตรงกันอย่างแม่นยำกับด้านที่อยู่ติดกันบนชิ้นส่วนแต่ละชิ้นเมื่อต่อจิ๊กซอว์เสร็จสมบูรณ์ ด้านอีกด้านของแต่ละชิ้นส่วนจะว่างเปล่า ยกเว้นหมายเลขระบุ และไม่ได้ใช้ในการต่อจิ๊กซอว์ ดังนั้นแต่ละชิ้นส่วนจึงสามารถใช้ได้เพียง 4 ทิศทางเท่านั้น มีสีทั้งหมด 22 สี ไม่รวมขอบสีเทา (ขอบสีเทาต้องหันออกด้านนอกของจิ๊กซอว์ เพื่อสร้างกรอบสีเทา) ห้าสีพบได้เฉพาะในคู่ขอบ ("รูปเพชร") 60 คู่ในวงแหวนด้านนอกสุด กล่าวคือระหว่างชิ้นส่วนขอบและชิ้นส่วนมุม ในขณะที่อีก 17 สีใช้ในคู่ขอบ "ด้านใน" ที่เหลืออีก 420 คู่ สีต่างๆ ถูกใช้เท่าๆ กัน โดยสีขอบทั้ง 5 สีถูกใช้ในคู่ขอบ 12 คู่พอดี และสีด้านในทั้ง 17 สีถูกใช้ในคู่ขอบ 24 คู่ (5 สี) หรือ 25 คู่ (12 สี) จำนวนคู่ขอบทั้งหมดคือ 480 คู่ สีขอบหนึ่งในห้าสีจะไม่ปรากฏในชิ้นส่วนมุมใดๆ ในขณะที่สีด้านในทั้ง 17 สีถูกใช้ในชิ้นส่วนขอบอย่างน้อยหนึ่งครั้ง

มีชิ้นส่วนมุม 4 ชิ้น (มีด้านสีเทา 2 ด้าน), ชิ้นส่วนขอบ 56 ชิ้น (มีด้านสีเทา 1 ด้าน) และชิ้นส่วนด้านใน 14 × ² = 196 ชิ้น (มีด้านสี 4 ด้าน) แต่ละชิ้นมีรูปแบบการจัดเรียงสีที่ไม่ซ้ำกัน และไม่มีชิ้นส่วนใดสมมาตรแบบหมุนได้ ดังนั้น ตัวเลือกของชิ้นส่วนและการวางแนวทั้งหมด 256 × 4 = 1024 แบบ จึงส่งผลให้เกิดรูปแบบสีของขอบที่แตกต่างกัน

ปริศนานี้แตกต่างจากปริศนา Eternity แรกตรงที่มีชิ้นส่วนเริ่มต้นที่ไม่สามารถเลือกได้ (คำใบ้บังคับ) ซึ่งต้องวางไว้ในตำแหน่งและทิศทางที่กำหนดใกล้กับจุดศูนย์กลางของกระดาน^{[ 3 ]}

มีปริศนาคำใบ้สองชุดให้เลือกใช้เมื่อเปิดตัวผลิตภัณฑ์ ซึ่งหากแก้ได้แต่ละชุดจะให้ตำแหน่งชิ้นส่วน (คำใบ้) บนปริศนาหลัก 256 ชิ้น ปริศนาคำใบ้ที่ 1 เป็นปริศนาสี่เหลี่ยมจัตุรัส (6 × 6) 36 ชิ้น และปริศนาคำใบ้ที่ 2 เป็นปริศนาสี่เหลี่ยมผืนผ้า (12 × 6) 72 ชิ้น ปริศนาคำใบ้เพิ่มเติมอีกสองชุดที่มีขนาดเท่ากันได้ถูกเพิ่มเข้ามาในปี 2551 ได้แก่ ปริศนาคำใบ้ที่ 3 จำนวน 36 ชิ้น และปริศนาคำใบ้ที่ 4 จำนวน 72 ชิ้น คู่มือระบุว่าสามารถแก้ปริศนาได้โดยไม่ต้องใช้คำใบ้^{[ 3 ]}จำนวนคำใบ้ทั้งหมดที่ทราบคือ 5

ตัวอย่างปริศนา 16 ชิ้น (4 × 4) มีให้บริการบนเว็บไซต์ Eternity II อย่างเป็นทางการในรูปแบบเกม Flash ^{[ 4 ]}

จำนวนรูปแบบที่เป็นไปได้ของปริศนา Eternity II โดยสมมติว่าชิ้นส่วนทั้งหมดแตกต่างกัน และไม่นับรวมชิ้นส่วนคงที่ที่มีตำแหน่งที่กำหนดไว้ล่วงหน้า คือ 256! × 4 ²⁵⁶หรือประมาณ 1.15 × 10 ⁶⁶¹ค่าขอบเขตบนที่แคบกว่าของจำนวนรูปแบบที่เป็นไปได้ สามารถทำได้โดยการพิจารณาชิ้นส่วนคงที่ตรงกลางและข้อจำกัดที่กำหนดไว้สำหรับชิ้นส่วนที่ขอบ: 1 × 4! × 56! × 195! × 4 ¹⁹⁵หรือประมาณ 1.12 × 10 ⁵⁵⁷ค่าขอบเขตบนเพิ่มเติม สามารถหาได้โดยการพิจารณาตำแหน่งและการวางแนวของชิ้นส่วนคำใบ้ที่ได้จากปริศนาเบาะแส ในกรณีนี้ ตำแหน่งและการวางแนวของชิ้นส่วนห้าชิ้นเป็นที่ทราบ ทำให้ได้ค่าขอบเขตบนที่ 4! × 56! × 191! × 4 ¹⁹¹ = 3.11 × 10 ⁵⁴⁵ซึ่งส่งผลให้พื้นที่การค้นหามีขนาดเล็กกว่าการประมาณค่าครั้งแรกถึง 3.70 × 10 ^{115 เท่า}

โดยประมาณเบื้องต้น ข้อจำกัดการจับคู่ขอบจะลดจำนวนการกำหนดค่าที่ถูกต้องลงด้วยปัจจัย (1/5) สำหรับทุกคู่ขอบด้านนอก และ (1/17) สำหรับทุกคู่ขอบด้านใน จำนวนการกำหนดค่าที่ถูกต้องจะถูกประมาณโดย 4! × 56! × 196! × 4 ¹⁹⁶ × (1/5) ⁶⁰ × (1/17) ⁴²⁰ ≈ 16.4 ซึ่งใกล้เคียงกับหนึ่งมาก สิ่งนี้บ่งชี้ว่าปริศนาน่าจะถูกออกแบบมาให้มีเพียงหนึ่งหรือสองวิธีแก้ปัญหา^{[ 5 ] [ 6 ]}ซึ่งจะเพิ่มความยากสูงสุด: วิธีแก้ปัญหาที่มากขึ้น (ข้อจำกัดที่หลวมกว่า เช่น สีที่น้อยลง) จะทำให้หาวิธีแก้ปัญหาได้ง่ายขึ้น (หนึ่งในหลายๆ วิธี) ในขณะที่ข้อจำกัดที่เข้มงวดกว่าจะลดพื้นที่การค้นหา ทำให้หาวิธีแก้ปัญหา (ที่ไม่ซ้ำกัน) ได้ง่ายขึ้น การเพิ่มประสิทธิภาพจำนวนสีได้รับการตรวจสอบเชิงประจักษ์สำหรับปริศนาขนาดเล็ก ซึ่งยืนยันข้อสังเกตนี้^{[ 7 ]}

หลังจากการตรวจสอบครั้งแรกในวันที่ 31 ธันวาคม พ.ศ. 2551 มีการประกาศว่าไม่พบวิธีแก้ปัญหาที่สมบูรณ์ รางวัล 10,000 ดอลลาร์สหรัฐ มอบให้แก่ Louis Verhaard จากเมืองลุนด์ ประเทศสวีเดน สำหรับวิธีแก้ปัญหาบางส่วน^{[ 8 ]}โดยมีขอบที่ตรงกัน 467 เส้นจากทั้งหมด 480 เส้น^{[ 9 ]} Verhaard ได้เผยแพร่วิธีแก้ปัญหาบางส่วนเพิ่มเติมอีก 3 วิธีที่มีจำนวนขอบที่ตรงกันเท่ากัน^{[ 8 ]}

ณ วันที่ 30 มกราคม 2554 เว็บไซต์อย่างเป็นทางการของ Eternity II ประกาศว่า "วันสุดท้ายสำหรับการหาคำตอบที่ถูกต้องของปริศนา Eternity II ผ่านไปแล้วโดยไม่มีผู้ชนะ และรางวัล 2 ล้านดอลลาร์สหรัฐสำหรับคำตอบที่ถูกต้องของปริศนา Eternity II ก็ไม่มีผู้ใดมาขอรับ" ^{[ 10 ]}

ยังไม่มีการเผยแพร่คำตอบที่สมบูรณ์และได้รับการตรวจสอบแล้วสำหรับปริศนาในเกม Eternity 2 ซึ่งรวมถึงคำตอบที่คริสโตเฟอร์ มอนค์ตันตั้งใจไว้ด้วย ซึ่งก็ยังไม่ได้รับการเผยแพร่ มีรายงานว่ามีคำตอบปลอมหลายชุดถูกเผยแพร่ทางออนไลน์

ปริศนา Eternityดั้งเดิมเป็นปริศนาการเรียงกระเบื้องที่มีรางวัลหนึ่งล้านปอนด์ สร้างโดยMoncktonเปิดตัวในเดือนมิถุนายน พ.ศ. 2542 และได้รับการแก้ไขโดยอัลกอริทึมการค้นหา ด้วยคอมพิวเตอร์ ที่ออกแบบโดยAlex SelbyและOliver Riordanซึ่งใช้ประโยชน์จากจุดอ่อนเชิงการจัดเรียงของการออกแบบปริศนาดั้งเดิม^{[ 11 ]}เงินรางวัลถูกจ่ายให้กับ Selby และ Riordan อย่างเต็มจำนวน

ปริศนาที่มีความคล้ายคลึงอย่างมากกับปริศนาแห่งนิรันดร์ทั้งสอง คือ ปริศนาDiamond Dilemmaซึ่งมีกำหนดส่งคำตอบในปี 1990 ซึ่งเร็วกว่ากำหนดส่งคำตอบของปริศนาแห่งนิรันดร์ดั้งเดิมถึง 10 ปี แต่มีชิ้นส่วนน้อยกว่า คือ 160 ชิ้น เมื่อเทียบกับ 209 และ 256 ชิ้นของปริศนาแห่งนิรันดร์สองข้อแรก และถึงกระนั้น ปริศนา Diamond Dilemma ก็ยังไม่มีใครแก้ได้มานานกว่า 25 ปีแล้ว

ปริศนา Eternity II ออกแบบโดย Monckton ในปี 2005 โดยครั้งนี้ร่วมมือกับ Selby และ Riordan ซึ่งออกแบบโปรแกรมคอมพิวเตอร์ที่สร้างการออกแบบ Eternity II ขั้นสุดท้าย^{[ 12 ]}ตามที่ Brendan Owen ผู้ชื่นชอบ เกมคณิตศาสตร์ กล่าว ปริศนา Eternity II ดูเหมือนจะได้รับการออกแบบมาเพื่อหลีกเลี่ยงข้อบกพร่องเชิงการจัดเรียงของปริศนาก่อนหน้า โดยมีพารามิเตอร์การออกแบบที่ดูเหมือนจะถูกเลือกเพื่อให้ปริศนายากต่อการแก้มากที่สุด โดยเฉพาะอย่างยิ่ง ต่างจากปริศนา Eternity ดั้งเดิม น่าจะมีเพียงจำนวนวิธีแก้ปัญหาที่เป็นไปได้เพียงเล็กน้อยเท่านั้น^{[ 5 ]} Owen ประมาณการว่าการค้นหา แบบย้อนกลับด้วย กำลังทั้งหมดอาจใช้เวลาประมาณ 2 × 10⁴⁷ขั้นตอนในการดำเนินการให้เสร็จสิ้น ^{[ 13 ]}

หนังสือพิมพ์ เดอะไทมส์อ้างคำพูดของมอนค์ตันในปี 2005 ว่า:

"การคำนวณของเราคือ หากคุณใช้คอมพิวเตอร์ที่ทรงพลังที่สุดในโลกและปล่อยให้มันทำงานตั้งแต่ตอนนี้จนถึงจุดสิ้นสุดของจักรวาลตามที่คาดการณ์ไว้ มันอาจจะไม่พบวิธีแก้ปัญหาใดๆ เลย" ^{[ 12 ]}

แม้ว่าจะมีการแสดงให้เห็นแล้วว่าคลาสของปริศนาการจับคู่ขอบซึ่ง Eternity II เป็นกรณีพิเศษนั้นโดยทั่วไปแล้วเป็น NP - complete ^{[ 14 ]} ก็สามารถกล่าวได้เช่นเดียวกันกับคลาสทั่วไปของปัญหาการบรรจุรูป หลายเหลี่ยม ซึ่งปริศนา Eternity ดั้งเดิมเป็นกรณีพิเศษ

เช่นเดียวกับปริศนา Eternity ดั้งเดิม การหาทางวางชิ้นส่วนจำนวนมากบนกระดานโดยให้ขอบของชิ้นส่วนทั้งหมดตรงกันนั้นทำได้ง่าย ทำให้ดูเหมือนว่าปริศนานี้ง่าย อย่างไรก็ตาม เมื่อพิจารณาจากจำนวนวิธีแก้ปัญหาที่เป็นไปได้ที่คาดว่าจะน้อยมาก จึงเป็นไปได้ยากมากที่วิธีแก้ปัญหาบางส่วนใดๆ จะนำไปสู่วิธีแก้ปัญหาที่สมบูรณ์

• TetraVexเกมปริศนาจับคู่ขอบที่ง่ายกว่า (ไม่มีการหมุนชิ้นส่วนหรือชิ้นส่วนขอบ) จากMicrosoft Entertainment Pack ^{[ 15 ]}แสดงให้เห็นว่าเป็นNP- complete ^{[ 16 ]}
• กระเบื้องหวัง

• เว็บไซต์ทางการ (เก็บถาวร)
• ตัวอย่างเกมปริศนา 4x4 ในรูปแบบ Flash จากเว็บไซต์เดิม (ซึ่งปัจจุบันปิดตัวไปแล้ว) (เก็บถาวรไว้)
• เครื่องมือแสดงภาพโซลูชันออนไลน์
• เว็บบอร์ดสนทนาเกม Eternity II (Groups.io)
• คำอธิบายเกี่ยวกับเกม Eternity II และการอภิปรายเกี่ยวกับโปรแกรมแก้ปริศนา
• คำอธิบายเกี่ยวกับโปรแกรมแก้ปริศนา Eternity II ของ Louis Verhaard ที่ Anna Karlsson ใช้
• คำอธิบายของปริศนาที่คล้ายกัน Diamond Dilemma

ซอฟต์แวร์:

• โปรแกรมแก้ปัญหา Eternity II แบบโอเพนซอร์สสำหรับ Matlab
• ซอฟต์แวร์แก้ไข/แก้ปัญหาเกม Eternity II แบบโอเพนซอร์ส
• ซอฟต์แวร์เกมปริศนา Eternity II แบบโอเพนซอร์ส
• E2Lab  : ซอฟต์แวร์แก้ไข/แก้ปริศนาเกม Eternity II ฟรี
• E2Solver  : โปรแกรมแก้ปริศนา Eternity II แบบโอเพนซอร์ส
• แอป Android สำหรับเกมปริศนาจับคู่ขอบแบบ Eternity II
• แอปพลิเคชันสำหรับ iPhone และ iPad สำหรับเกมปริศนาจับคู่ขอบแบบ Eternity II