ไขปริศนาความลับในเกม Sudoku

  Sudoku 数独

มีน้องคนนึง(ไม่รู้ว่าน้องจริงหรือป่าว) ที่เข้ามาอ่าน  Mathminton แล้วมาโพสต์ถามเอาไว้ เรื่องของ Sudoku

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

ครับเข้าเรื่องการดีกว่าสำหรับคนที่ไม่รู้ว่ามันคืออะไร ไม่รู้เลยว่ามันคืออะไรมารู้จักมันซะหน่อยก่อนดีกว่าครับ

เริ่มกันที่ประวัติก่อนนะคับ

เกมซูโดกุจริงๆแล้วเป็นเกม ที่เกิดครั้งแรกที่สหรัฐอเมริกาในปี พ.ศ.  2522  ในชื่อ เกม Number Place   แต่ก็ไม่ได้น่าสนใจอะไร จนกระทั้งเกมนี้แพร่เข้าไปในญี่ปุ่น เกมนี้ได้เปลี่ยน ชื่อเป็น ซูโดกุ เกมนี้กับได้รับความนิยมอย่างล้นหลาม และนิยมไปจนทั่วโลก (สงสัยเปลี่ยนชื่อแล้วเฮงดี น่าลองเปลี่ยนชื่อตัวเองเป็นชื่อญี่ปุ่นบ้างเนอะ อิคึๆ )
หลักการของเกมแบบพื้นฐานคือการใช้ ตารางตัวเลขแบบจัตุรัส ขนาด 9*9 เป็นตาราง 81 ช่องในช่องพวกนี้จะแบ่งตัวเองออกเป็น 9 ส่วน แต่ละส่วนเป็นจตุรัสแบบ 3*3 เสร็จแล้วเกมจะกำหนดเลขในตารางบางส่วนมาให้เราเติมเลขให้ครบทุกช่องในตารางนี้โดยที่ มีกติกอยู่นิดส์นึงว่า เลขในแต่ละแถวแต่ละหลัก และแต่ละตารางย่อยนั้นจะต้องเป็นเลข 1-9 ที่ไม่ซ้ำกันเลย
Sudoku เป็นเกมคณิตศาสตร์เข้าใจง่ายๆ เพราะกติกาไม่ยาก เล่นได้ตั้งแต่ ประถม ป.1 ป.2 ยัน คนชราที่นอนเล่นในโรงพยาบาล 
ให้ประโยชน์เกี่ยวกับสมาธิ และการคิดอย่างมีเหตุผล

ตัวอย่างเกม

[How to play]

เทคนิคการเล่นSudoku ที่ผู้เล่นเป็นส่วนใหญ่คือ วิธีการตัดส่วนที่เป็นไปไม่ได้ออก 
เป็นเทคนิคง่ายแต่ใช้ได้ไม่ยาก
เริ่มด้วยการดูที่ตารางนี้ก่อนครับ

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

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

 ทำในลักษณะเช่นนี้ไปเรื่อยๆ โดยการใช้ข้อมูลตัวเลขที่จะได้มาใหม่เรื่อยๆ ในการเติมเลขเพิ่มจนกระทั้งเต็มกระดาน

คำเตือน: การเดามักจะนำไปสู่หายนะ อาจเป็นเหตุให้พิการ หรือเสียชีวิตได้ (ออกจะเวอร์ไป)

มาเข้าถึงปัญหาที่คาใจคนหลายๆ คนกันนะครับ ด้วยความยากของมัน ตารางซูโดกุมีด้วยกันหลายรูปแบบ แต่ด้วยเงื่อนไขที่มากขนาดนั้น ทำให้เรามั่นใจได้ว่าจำนวนมันมีการจำกัด แล้วไอ้ที่ว่าจำกัดนั้นมันมีเท่าไรกันแน่นะ ก่อนนั้นเรามาลองจำลองปัญหาให้ง่ายขึ้นกันก่อนดีกว่าครับ

ตารางซูโดกุแบบ 4*4 ใส่เลข 1-4 ไปในช่องของตารางโดยไม่ให้เลขในแต่และแถว แต่ละหลักเป็นเลขซ้ำกัน รวมไปถึงในสี่เหลื่ยมเล็กขนาด 2*2 มีเลขซ้ำกัน 

อย่างไม่มีเงื่อนๆไขอะไรเราก็เติมมั่วก่อนในแถวแรกครับ

เสร็จแล้วเราก็ต่อด้วยการเติ่มเลขที่แถวต่อไป ได้ทั้งหมดสี่ แบบต่อไปนี้ครับ เพราะการเติมแบบอื่นๆจะถูกจำกัดด้วยเงื่อนไขต่างๆตามกติกาครับ

Sudoku 4*4 ทั้งสี่แบบ

ครับเสร็จแล้ว เราก็มาดูกันไปทีละส่วนนะครับแบบที่ 1 นับจากซ้าย เราก็จะเติมเลขจนเต็มได้ทั้งหมดสี่แบบตามนี้ครับโดยเริ่มเติมกากช่องซ้าย ไปทางขวาพร้อมทั้งแถวบนแถวล่าง 

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

 ด้วยเหตุ เช่นนี้เราจึงต้องทำการลองให้ครบทุกกรณี จนถึงกรณีสุดท้ายครับ

เสร็จสรรพครบทุกกรณี เราก็ลองนับครับ นับแล้วมี Sudoku ที่เป็นไปได้อยุ่ 12 แบบด้วยกัน
ทีนี้เราก็กลับไปส่วนเริ่มต้นที่เรามั่วเลขไว้ครับ เราลองเปลียนเป็นแบบอื่น มันก็คงจะได้ 12 แบบ เหมือนกัน ดังนั้นด้วยวิชาคอมบินาทอริก เราจะสับเปลี่ยนตัวเลขได้ทั้งหมด 4! วิธี แต่ละวิธีมีตารางตัวเลขอาจเกิดได้ยู่ 12 แบบ ดังนั้นตาราง Sudoku แบบ 4*4 ที่เป็นไปได้ทั้งหมดจึงเป็น 4! 12 = 288 แบบ


เป็นอันว่าจบครับ


มาดูกันที่แบบธรรมดากันดีกว่าครับ

 ตารางแบบ 9*9 มี 9 แถว 9 หลัก แล้วก็มีกล่องย่อยๆ 9 กล่อง จะขอเรียกพวกมันว่า B1 ถึง B9 ละกันครับ

เริ่มแรกเราก็จะใช้วิธีคล้ายๆกันกับ 4*4 ครับ
คือ เติมเลขมั่วๆใส่ไปในช่อง B1 ก่อนละกันครับ แล้วก็นับจำนวนวิธีว่าได้เท่าเราสุด ท้ายก็เราไปคูณกับ 9! เราก็จะได้จำนวนหน้า Sudoku ที่เป็นไปได้ทั้งหมด

เสร็จแล้วพอเราก็จะมาใส่ชุดตัวเลขที่ตำแหน่ง แถวบนสุดของ B2 และ B3 ได้ตัวเลขยี่สิบชุดดังนี้

 เช่น ถ้าเราเลือกตัวเลขชุดแรกนั้นคือ {4,5,6}|{7,8,9} set แรก ใส่ใน B2 set ที่สองเราใส่ใน B3 โดย {4,5,6} นี้หมายถึง จะใส่เป็น 4|5|6 ก็ได้หรือจะเป็น 5|6|4 หรือ 4|6|5 อย่างไงก็ ขอให้มีเลขให้ครบ

 ทั้งตัวเลขชุดที่เหลือก็จะถูก ล็อคไปเป็นลำดับ แล้วก็จะมีอย่างเช่น {4,5,7}|{6,8,9} มันก็จะมีตัวเลขบางส่วนยังไม่เข้าที่เข้าทาง ก็จะติด a b c ไว้

 พอเสร็จเราก็คำนวณวิธีกันก่อนครับได้ วิธีการใส่เลขสามแถวแรกใน B1 B2 B3 ได้มีทั้งหมด คือแบบแรกมีวิธีการใส่เลขได้เลยอยู่ (3!)^6 วิธี ก็จะมี {4,5,6}|{7,8,9} กับ {7,8,9}|{4,5,6} รวมเป็น 2 แบบ ส่วนที่เหลือต้องติด a b c ซึ่งแต่ละตัวแทนเลข 3 ตัว ก็จะได้เป็น 
3(3!)^6 รวมจำนวนวิธีได้เป็น  2*(3!)^6 + 18*3(3!)^6 = 56 (3!)^6 = 2612736 แบบ


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


ดูรายละเอียดการคำนวณเพิ่มเติมได้ที่
  afjarvis sudoku

ปัญหาต่อไปครับ

คือจำนวนตัวตัวเลขเริ่มต้นที่น้อยที่สุดที่ จะทำให้ game Sudoku ของเราเฉลยแค่ทางเดียว คืออะไร

จำนวนนี้ยังไม่เห็นมีใครมาตอบอะไรชัดเจนนะครับ ปัญหานี้คงต้องลองมาหาแก้กันต่อไปนะครับ แต่ถ้าให้ผมเดาละก็น่าจะเป็น 16 หรือ 17 นี่ละ ถ้าเป็น 16 นี้ยังไม่เคยเห็นแต่
ถ้า Sudoku ที่ให้ตัวเลขเริ่มต้นมา 17 ละ ก็เรามีตัวอย่างมากมาย

 เช่น

 อันนี้เฉลย มีคำตอบแบบเดียว

 อันนี้เฉลย มีคำตอบแบบเดียว แต่ด้วยความน้อยของมันกว่าจะได้ออกมาก็.....นะ

ถ้าใครเจอ จำนวนน้อยกว่านี้ก็ลองโพสบอกผมมาละกันครับ...






จบแล้วเราก็มาลองเล่นเกมกันดีกว่า Sudoku ทดสอบฝีมือกันเล่น