ปริศนา Griductive ถูกสร้างขึ้นอย่างไร

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

นั่นไม่ใช่เป้าหมายในการออกแบบ แต่เป็นการรับประกันทางคณิตศาสตร์ ที่บังคับใช้ด้วยตัวแก้ปัญหาระดับเดียวกับที่ใช้ในการวิจัยเชิงปฏิบัติการและการตรวจสอบชิป บทความนี้จะอธิบายว่าทำอย่างไร

ทำไมความเป็นเอกลักษณ์จึงสำคัญ

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

ดังนั้นตัวสร้างปริศนาจึงไม่เพียงแค่สร้างปริศนาที่ บังเอิญ มีคำตอบเดียว แต่มัน พิสูจน์ ว่าไม่มีคำตอบที่สองก่อนที่ปริศนาจะถูกเผยแพร่

ท่อส่งห้าขั้นตอน

ปริศนา Griductive แต่ละข้อถูกสร้างผ่านท่อส่งห้าขั้นตอน นี่คือสิ่งที่เกิดขึ้นในแต่ละขั้นตอน

ขั้นตอนที่ 1: สร้างคำตอบแบบสุ่ม

ตัวสร้างเริ่มต้นด้วยการสร้างตารางคำตอบที่ถูกต้อง การกำหนดแบบสุ่มว่าแต่ละเซลล์เป็นผู้ต้องสงสัยหรือผู้บริสุทธิ์ นี่คือความจริงพื้นฐานที่ผู้เล่นจะนิรนัยในที่สุด

ณ จุดนี้ ยังไม่มีเบาะแส กระดานเป็นเพียงการกำหนดค่าแบบสุ่มที่สอดคล้องกับข้อจำกัดเชิงโครงสร้างพื้นฐาน (ขนาดตาราง จำนวนผู้ต้องสงสัยในช่วงที่ถูกต้อง)

ขั้นตอนที่ 2: สร้างคลังเบาะแส

ถัดไป ตัวสร้างจะระบุเบาะแสที่เป็นไปได้ทุกข้ออย่างครบถ้วนที่ เป็นจริง บนกระดานคำตอบ

Griductive มีประเภทเบาะแสที่แตกต่างกันมากกว่า 26 ประเภท ได้แก่ การนับ การเปรียบเทียบ เชิงพื้นที่ เชิงอัตถิภาวนิยม ความเป็นเอกลักษณ์ การเชื่อมต่อ และอื่นๆ สำหรับแต่ละประเภท ตัวสร้างจะทดสอบทุกพารามิเตอร์ที่ถูกต้องกับกระดาน ตาราง 4x4 สามารถสร้างเบาะแสที่เป็นตัวเลือกได้หลายพันข้อ เฉพาะเบาะแสที่ประเมินว่าเป็น "จริง" บนคำตอบเท่านั้นที่ถูกเก็บไว้

นี่คือวัตถุดิบที่ตัวสร้างทำงานด้วย: คลังข้อความที่เป็นจริงจำนวนมาก ซึ่งส่วนใหญ่เป็นข้อมูลซ้ำซ้อน

ขั้นตอนที่ 3: เลือกชุดเบาะแสที่น้อยที่สุด (ส่วนที่ยาก)

นี่คือจุดที่งานจริงเกิดขึ้น ตัวสร้างต้องเลือกชุดย่อยเล็กๆ ของเบาะแสจากคลังเพื่อให้:

1. เบาะแสเพียงพอ เบาะแสร่วมกันจำกัดพื้นที่คำตอบให้เหลือกระดานที่ถูกต้องเพียงหนึ่งเดียว
2. ไม่มีเบาะแสที่ซ้ำซ้อน การลบเบาะแสใดเบาะแสหนึ่งจะทำให้มีคำตอบหลายคำตอบ

ตัวสร้างใช้วิธี การตอบสนองข้อจำกัดแบบโลภ:

1. เริ่มต้นโดยไม่ได้เลือกเบาะแสใดเลย พื้นที่คำตอบเปิดกว้าง กระดานหลายแบบอาจถูกต้อง
2. ให้คะแนนเบาะแสทุกตัวเลือกตามความสามารถในการ ลดพื้นที่คำตอบ เบาะแสที่กำจัดความเป็นไปได้ที่เหลือ 80% จะได้คะแนนสูงกว่าเบาะแสที่กำจัดเพียง 10%
3. เลือกเบาะแสที่ได้คะแนนสูงสุดและเพิ่มเข้าในชุด
4. แก้โมเดลข้อจำกัดใหม่ด้วยชุดเบาะแสที่อัปเดตแล้ว
5. ทำซ้ำจนกว่าตัวแก้ปัญหาจะยืนยันว่าเหลือคำตอบเพียงหนึ่งเดียว
6. ตัดแต่ง: ตรวจสอบชุดสุดท้ายและลบเบาะแสใดก็ตามที่ไม่จำเป็นสำหรับความเป็นเอกลักษณ์ สิ่งนี้ทำให้ปริศนาสะอาดและหลีกเลี่ยงการให้ข้อมูลฟรีแก่ผู้เล่น

ผลลัพธ์คือชุดเบาะแสที่กระชับและยุติธรรม เพียงพอที่จะแก้ปริศนาได้อย่างสมบูรณ์ โดยไม่มีเบาะแสที่สูญเปล่า

ขั้นตอนที่ 4: ให้คะแนนความยาก

เมื่อชุดเบาะแสถูกล็อกแล้ว ตัวสร้างจะให้คะแนนความยากของปริศนาในมาตราส่วน 0-100 ปัจจัยสี่ประการมีส่วนร่วม:

• สัดส่วนเบาะแสง่าย (35%) — มีเบาะแสที่เป็นการนับโดยตรงหรือข้อความระบุตัวตนกี่ข้อ เบาะแสง่ายมากขึ้นหมายถึงปริศนาง่ายขึ้น
• สัดส่วนเบาะแสซับซ้อน (30%) — มีเบาะแสกี่ข้อที่ต้องการการใช้เหตุผลหลายขั้นตอนหรือเชิงพื้นที่ สิ่งเหล่านี้ต้องการห่วงโซ่การนิรนัยที่ลึกกว่า
• ความขาดแคลนข้อมูล (20%) — เบาะแสถูกให้น้อยเพียงใดเมื่อเทียบกับขนาดตาราง เบาะแสน้อยลงหมายถึงมีข้อมูลให้ทำงานน้อยลง
• ขนาดตาราง (15%) — ตารางที่ใหญ่กว่ายากกว่าโดยธรรมชาติในการติดตาม ปริศนา 5x5 มีเซลล์เกือบสามเท่าของ 3x3

เบาะแสแต่ละประเภทยังมีระดับความซับซ้อนเฉพาะตัวตามการใช้เหตุผลที่ต้องการ เบาะแสเช่น "Julia เป็นผู้ต้องสงสัย" นั้นง่ายที่สุดเท่าที่จะเป็นไปได้ เบาะแสเช่น "Julia เป็นคนเดียวในแถว 3 ที่มีเพื่อนบ้านที่เป็นผู้ต้องสงสัยเพียง 1 คน" ต้องอ้างอิงหลายเซลล์พร้อมกันและได้คะแนนสูงกว่ามาก

ขั้นตอนที่ 5: สร้างคำใบ้และจัดรูปแบบผลลัพธ์

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

ปริศนาสุดท้ายถูกบรรจุพร้อมข้อมูลทั้งหมดที่เกมต้องการ: เมทาดาทา ชุดเบาะแส ลำดับคำใบ้ และคะแนนความยาก

ตัวแก้ปัญหา: วิธีพิสูจน์ความเป็นเอกลักษณ์

หัวใจของท่อส่งคือ Google OR-Tools CP-SAT ตัวแก้ปัญหาการเขียนโปรแกรมเชิงข้อจำกัดที่ผสมผสานการแพร่กระจายข้อจำกัด การเขียนโปรแกรมจำนวนเต็ม และการแก้ปัญหา SAT

ปริศนากลายเป็นปัญหาทางคณิตศาสตร์อย่างไร

แต่ละเซลล์บนตารางถูกสร้างแบบจำลองเป็น ตัวแปรบูลีน: ผู้ต้องสงสัย (1) หรือผู้บริสุทธิ์ (0) แต่ละเบาะแสกลายเป็นข้อจำกัดทางคณิตศาสตร์หนึ่งข้อหรือมากกว่าเหนือตัวแปรเหล่านั้น

ตัวอย่างเช่น:

• "มีผู้ต้องสงสัยเพียง 2 คนในแถว 3" กลายเป็น: cell[3,0] + cell[3,1] + cell[3,2] + cell[3,3] = 2
• "ผู้ต้องสงสัยทั้งหมดในคอลัมน์ A เชื่อมต่อกัน" กลายเป็น: ข้อจำกัดการเชื่อมต่อที่รับรองว่าเซลล์ผู้ต้องสงสัยในคอลัมน์ A สร้างห่วงโซ่ต่อเนื่องโดยไม่มีช่องว่าง
• "แถว 1 มีผู้ต้องสงสัยมากกว่าคอลัมน์ B" กลายเป็น: sum(row_1) > sum(col_B)

วิธีตรวจสอบความเป็นเอกลักษณ์

หลังจากประกอบชุดเบาะแสแล้ว ตัวสร้างจะถาม CP-SAT คำถามที่แม่นยำ: "ด้วยข้อจำกัดเหล่านี้ มีการกำหนดค่าที่ถูกต้องมากกว่าหนึ่งอันหรือไม่?"

CP-SAT ไม่ได้แค่หา คำตอบหนึ่ง แต่สามารถระบุ คำตอบทั้งหมด ได้ หากตัวแก้ปัญหาพบเพียงหนึ่ง ปริศนานั้นถูกต้อง หากพบสองหรือมากกว่า ตัวสร้างจะกลับไปขั้นตอนที่ 3 และเพิ่มเบาะแสอีกข้อ

นี่คือการพิสูจน์อย่างเป็นทางการ ไม่ใช่การประมาณ CP-SAT สำรวจพื้นที่คำตอบทั้งหมดอย่างครบถ้วน หากมันบอกว่ามีคำตอบเดียว ก็มีเพียงหนึ่งเดียวเท่านั้น ไม่มีข้อยกเว้น

ทำไมไม่ใช้วิธีบรูทฟอร์ซ?

ตาราง 5x5 มี 25 เซลล์ แต่ละเซลล์มี 2 ค่าที่เป็นไปได้ นั่นคือ 2 ยกกำลัง 25 = 33 ล้านกระดานที่เป็นไปได้ การบรูทฟอร์ซทั้งหมดนั้นช้าและไม่สามารถขยายขนาดได้

CP-SAT เร็วกว่าอย่างมากเพราะ การแพร่กระจายข้อจำกัด: เมื่อเบาะแสบอกว่า "แถว 3 มีผู้ต้องสงสัยเพียง 2 คน" ตัวแก้ปัญหาจะลดพื้นที่การค้นหาสำหรับทุกเซลล์ในแถว 3 ทันทีโดยไม่ต้องตรวจสอบแต่ละชุดค่าผสมทีละอัน เบาะแสที่ซับซ้อนยิ่งเสริมผลนี้ ในทางปฏิบัติ CP-SAT พิสูจน์ความเป็นเอกลักษณ์สำหรับปริศนา 5x5 ได้ในเวลาไม่กี่มิลลิวินาที

อะไรอาจผิดพลาดได้ (และเราป้องกันอย่างไร)

"ถ้าเบาะแสคลุมเครือล่ะ?"

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

คำจำกัดความเหล่านี้ถูกสร้างโดยตรงในโมเดลข้อจำกัด ไม่มีขั้นตอนการตีความภาษาธรรมชาติที่ความคลุมเครืออาจแทรกเข้ามาได้ เอกสารอ้างอิง รายละเอียดเพิ่มเติม ในเกมจะแสดงให้ผู้เล่นเห็นอย่างชัดเจนว่าคำหลักเชิงพื้นที่แต่ละคำหมายถึงอะไร

"ถ้าตัวแก้ปัญหามีบั๊กล่ะ?"

ตัวแก้ปัญหา CP-SAT เป็นเครื่องมือที่ได้รับการทดสอบอย่างดีและใช้กันอย่างแพร่หลาย ดูแลโดยทีมการเพิ่มประสิทธิภาพของ Google แต่เราไม่ได้พึ่งพาความเชื่อมั่นเพียงอย่างเดียว ปริศนาที่สร้างขึ้นทุกข้อจะได้รับการตรวจสอบอย่างอิสระ:

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

"ถ้าการสร้างเบาะแสพลาดกรณีขอบล่ะ?"

เบาะแสแต่ละประเภทมีฟังก์ชันการประเมินอย่างเป็นทางการที่ทดสอบกับการกำหนดค่าปริศนาที่รู้จัก ขั้นตอนการสร้างคลังเบาะแสจะรวมเฉพาะเบาะแสที่ประเมินว่าเป็นจริงบนคำตอบจริงเท่านั้น เบาะแสที่เป็นเท็จบนคำตอบไม่มีทางปรากฏในปริศนา

ผลลัพธ์

เมื่อคุณเปิดปริศนา Griductive นี่คือสิ่งที่เกิดขึ้นแล้ว:

1. คำตอบแบบสุ่มถูกสร้างขึ้น
2. เบาะแสที่เป็นตัวเลือกหลายพันข้อถูกประเมินกับมัน
3. ชุดย่อยที่น้อยที่สุดและไม่ซ้ำซ้อนถูกเลือก
4. ตัวแก้ปัญหาอย่างเป็นทางการ พิสูจน์ ว่าคำตอบเดียวเท่านั้นที่สอดคล้องกับเบาะแสเหล่านั้น
5. ตัวแก้ปัญหาอัตโนมัติตรวจสอบอย่างอิสระว่าปริศนาสามารถแก้ได้ด้วยการนิรนัยล้วนๆ
6. คะแนนความยากถูกคำนวณและลำดับคำใบ้ถูกสร้างขึ้น

ทุกปริศนา ทุกวัน ในทุกขนาดตารางทั้งสี่ ไม่มีข้อยกเว้น

สัญญานั้นยังคงอยู่: หากคุณติดขัด แสดงว่ามีเบาะแสที่คุณยังไม่ได้ใช้อย่างเต็มที่ หากคุณคิดว่ามีคำตอบที่เป็นไปได้สองข้อ ให้อ่านเบาะแสอีกครั้ง ตรรกะจะแก้ไขมัน และหากคุณต้องการหลักฐาน กราฟตรรกะจะแสดงห่วงโซ่การนิรนัยที่แน่นอนจากเบาะแสสู่คำตอบ

ต่อไป: เบาะแสที่เล่าเรื่อง

ตอนนี้ เบาะแสของ Griductive อ่านเหมือนข้อความตรรกะที่แม่นยำ ชัดเจนและไม่คลุมเครือ แต่ยอมรับว่าค่อนข้างเป็นทางการ "มีผู้ต้องสงสัยเพียง 2 คนในแถว 3" ทำหน้าที่ได้ แต่มันไม่ได้ทำให้คุณรู้สึกเหมือนนักสืบกำลังทำคดี

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

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

การรับประกันเดียวกัน ความเข้มงวดเดียวกัน แต่ปริศนาที่รู้สึกเหมือนสมการน้อยลงและเหมือนคดีที่น่าไขมากขึ้น

ไม่ต้องเดา ไม่ต้องพึ่งโชค รับประกันทางคณิตศาสตร์

เล่นปริศนาวันนี้ ->