จำนวนคำใบขั้นต่ำที่ Sudoku สามารถมีคือเท่า?
อัปเดตล่าสุด
ซูโดกุที่ถูกต้อง - หนึ่งที่มีคำตอบเดียว - ต้องการอย่างน้อย 17 ตัวเลขที่กำหนด นี่เป็นผลลัพธ์ทางคณิตศาสตร์ที่ได้รับการพิสูจน์ ปثقาใด ๆ ที่มี 16 ตัวเลขที่กำหนดหรือน้อยกว่าจะมีหลายคำตอบหรือไม่มีเลย
หลักฐานปี 2012
ในปี 2012 Gary McGuire, Bastian Tugemann และ Gilles Civario แห่ง University College Dublin ได้ตีพิมพ์บทพิสูจน์ว่าไม่มี Sudoku ที่มี 16 เบาะแสที่ถูกต้องอยู่ งานของพวกเขาเป็นเชิงคำนวณเป็นหลัก: พวกเขาค้นหาพื้นที่ทั้งหมดของตารางที่มี 16 เบาะแสที่เป็นไปได้และยืนยันว่าไม่มีตารางใดที่ให้คำตอบเดียว การค้นหาต้องใช้เวลาคำนวณประมาณ 7 ล้าน core-hours
ก่อนหน้านี้ มีความเชื่อกันอย่างกว้างขวางว่า 17 เป็นจำนวนขั้นต่ำและมีปริศนา 17 เบาะแสหลายพันชิ้นที่ถูกค้นพบโดยการทดลอง ทีมของ McGuire ได้ให้บทพิสูจน์ที่เข้มงวดครั้งแรกว่า 16 เป็นไปไม่ได้
ปริศนา 17 คำใบ้มีลักษณะอย่างไร
ปริศนา 17-clue นั้นเบาบางมาก - 17 given digits ใน 81 cells, เหลือ 64 ว่าง พวกมันเป็นหนึ่งในปริศนาที่ยากที่สุดในการแก้และโดยทั่วไปต้องใช้ advanced techniques การค้นหาปริศนา 17-clue ที่ถูกต้องนั้นต้องใช้ความพยายามในการคำนวณหลายทศวรรษ ณ เวลาที่เขียน, มีมากกว่า 49,000 ปริศนา Sudoku 17-clue ที่แตกต่างกันโดยพื้นฐานที่รู้จัก
สิ่งนี้หมายถึงอะไรสำหรับการออกแบบปริศนา
ปริศนาที่ตีพิมพ์สำหรับผู้แก้มนุษย์ไม่ค่อยมีต่ำกว่า 22 เบาะแส ปริศนาระดับความยาก Expert และ Master โดยทั่วไปใช้ 22-27 ตัวเลขที่กำหนด ในขณะที่ปริศนา Easy ใช้ 36-45 ขั้นต่ำ 17 เบาะแสเป็นขอบเขตทางทฤษฎี - ในทางปฏิบัติ ความสามารถในการแก้ด้วยเทคนิคที่ดีและเส้นทางการแก้ที่สนุกมีความสำคัญมากกว่าจำนวนเบาะแสเพียงอย่างเดียว