นักคณิตศาสตร์พิสูจน์ "ซูโดคุที่ใบ้มาน้อยกว่า 17 ตัวเลขจะไม่มีคำตอบที่สมบูรณ์"

ซูโดคุ (sudoku) น่าจะเป็นเกมคณิตศาสตร์ที่แพร่หลายมากที่สุดในยุคนี้ แม้แต่หนังสือพิมพ์ยังมีลงให้ผู้อ่านลองเล่นกันทุกวัน กติกาของเกมคือให้เอาตัวเลข 1-9 ใส่ลงไปในตาราง 9x9 โดยไม่ให้มีตัวเลขซ้ำกันในแนวตั้งหรือแนวนอนหรือในช่องตารางย่อย 3x3 ในตอนเริ่มต้นจะมีตัวเลขใบ้ตรงตำแหน่งต่างๆ มาให้ก่อน นักคณิตศาสตร์ก็สังเกตกันมานานแล้วว่าไม่เคยมีเกมซูโดคุอันไหนให้ตัวเลขใบ้น้อยกว่า 17 ตำแหน่งมาก่อน แต่ก็ไม่มีใครพิสูจน์ได้ว่าทำไมต้องเป็นตัวเลขนี้ จนกระทั่งทีมวิจัยที่นำโดย Gary McGuire แห่ง University College Dublin คิดอัลกอริธึมที่จะใช้พิสูจน์ขึ้นมา วิธีพิสูจน์ของ Gary McGuire ใช้หลักการที่เรียกว่า "hitting-set algorithm" โดยคร่าวๆ คือเขาต้องจำลองออกมาว่ามีรูปแบบการเรียงตัวเลขแบบใดได้บ้างที่จะบรรจุลงไปในตารางซูโดคุได้ และเนื่องจากเกมซูโดคุที่ใช้ได้จะต้องมีคำตอบเพียง 1 รูปแบบเท่านั้น ฉะนั้นตัวเลขที่ใบ้ให้มาในตอนแรกจะต้อง 'ตี' คำตอบที่เป็นรูปแบบอื่นๆ ให้ตกไป คราวนี้ก็เหลือแค่พิสูจน์ว่าตัวเลขใบ้ที่น้อยกว่า 17 ตัว (ตั้งแต่ 16 ตัวลงไป) ไม่เพียงพอที่จะตีรูปแบบอื่นจนเหลือคำตอบแค่อันเดียวได้ ฟังดูแล้วก็ง่ายๆ แต่การพิสูจน์ต้องใช้วิธี brute force เท่านั้น (หรือที่  See More..