สารานุกรมซูโดกุ · คณิตศาสตร์และคอมพิวเตอร์

คณิตศาสตร์ของซูโดกุ

อัปเดตเมื่อ 2026-10-05

จัตุรัสละตินที่มีบล็อก

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

แหล่งข้อมูล: Wikipedia: Latin square

มีตารางทั้งหมดกี่แบบ

แบร์ทรัม เฟลเกนเฮาเออร์ (Bertram Felgenhauer) และเฟรเซอร์ จาร์วิส (Frazer Jarvis) นับตารางขนาด 9×9 ที่เติมครบแล้วในปี ค.ศ. 2005 พบว่ามี 6,670,903,752,021,072,936,960 แบบ หรือประมาณ 6.67 × 10²¹ หลายแบบเป็นตารางเดียวกันที่แปลงรูปไป หากนับสองตารางเป็นแบบเดียวกันเมื่อสามารถแปลงตารางหนึ่งให้เป็นอีกตารางได้ด้วยการสลับตัวเลขแทนกัน การหมุนหรือสะท้อน หรือการจัดลำดับแถวและคอลัมน์ใหม่ด้วยวิธีที่ยังรักษาความถูกต้องของตาราง จะเหลือตารางที่แตกต่างกันโดยสาระสำคัญ 5,472,730,538 แบบ จำนวนนี้คำนวณโดยเอ็ด รัสเซลล์ (Ed Russell) และเฟรเซอร์ จาร์วิส

แหล่งข้อมูล: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

คำใบ้ขั้นต่ำ 17 ตัว

ไม่มีซูโดกุมาตรฐานขนาด 9×9 ที่มีตัวเลขที่ให้มาไม่เกิน 16 ตัวแล้วมีคำตอบเดียวพอดี แกรี แมกไกวร์ (Gary McGuire), บาสเตียน ทูเกอมันน์ (Bastian Tugemann) และฌีล ซีวาริโอ (Gilles Civario) แสดงผลนี้ด้วยการค้นหาครบทุกกรณีด้วยคอมพิวเตอร์ และประกาศผลในเดือนมกราคม ค.ศ. 2012 จำนวน 17 ตัวเป็นขั้นต่ำ ไม่ใช่การรับประกัน: ตารางจำนวนมากที่มีตัวเลขที่ให้มา 17 ตัวยังมีมากกว่าหนึ่งคำตอบ

แหล่งข้อมูล: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

ซูโดกุในรูปของการระบายสีกราฟ

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

แหล่งข้อมูล: Wikipedia: Sudoku graph

ยากในกรณีทั่วไป แต่รวดเร็วสำหรับ 9×9

สำหรับตารางซูโดกุที่ขยายขนาดได้อย่างไม่จำกัด (n²×n² โดยมีบล็อกขนาด n×n) การตัดสินว่าตารางที่เติมไว้บางส่วนสามารถเติมจนสมบูรณ์ได้หรือไม่เป็นปัญหา NP-complete ผลนี้เผยแพร่โดยทากายูกิ ยาโตะ (Takayuki Yato) และทากาฮิโระ เซตะ (Takahiro Seta) ในปี ค.ศ. 2003 โดยทั่วไปโปรแกรมคอมพิวเตอร์ที่มีประสิทธิภาพแก้โจทย์ขนาด 9×9 ทั่วไปได้ในเวลาเพียงเสี้ยววินาที แต่เวลาที่ใช้ขึ้นอยู่กับโปรแกรม คอมพิวเตอร์ และโจทย์

แหล่งข้อมูล: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

ดูเพิ่มเติม

แหล่งข้อมูล

บทความทั้งหมด →