สอนใช้งานและแกะสูตร Template Sudoku Solver ของ Microsoft – Part2

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

ปกติแล้วการเล่น Sudoku มันคือ การต้องใส่เลข 1-9 ลงไปในช่องว่าง โดยที่แต่ละแถว แต่ละคอลัมน์ และแต่ละพื้นที่สี่เหลี่ยม 3×3 นั้น มีเลข 1-9 ไม่ซ้ำกันเลย (คนที่มาอ่านบทความนี้ถึงตอนที่ 2 ได้น่าจะพอรู้กติกาอยู่แล้วเนอะ)

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

อย่าลืม Unprotect Sheet

ทีนี้พอเรารู้หลักการแล้ว เราจะมาเริ่มแกะสูตรกัน แต่ปรากฏว่าเรามองไม่เห็นสูตรที่เค้าเขียนไว้ เพราะเค้าทำการ Protect Sheet ไว้อยู่ ดังนั้นให้เราทำการไปที่ Review -> Unprotect Sheet ก่อน

สูตรที่ Final Position Board

ถ้าเรา Double Click สูตรใน B15 จะเห็นเป็นดังนี้

=IF(COUNT($W$5:$Y$7)=1,SUM($W$5:$Y$7),IF(COUNT($AZ$5:$BB$7)=1,SUM($AZ$5:$BB$7),""))

จะเห็นได้ว่า มันใช้หลักการ Basic อย่างที่เราคิดนี่แหละ โดยจะเช็ค Possible Numbers ในตารางฝั่งซ้ายก่อน ถ้ามีเหลือ possible number ตัวเดียว (ใช้การ COUNT) ก็จะเอาตัวนั้นเลย (ใช้การ SUM) ถ้ามีหลายตัวค่อยเช็คฝั่งขวาด้วยหลักการเดียวกันคือถ้ามีตัวเดียวเอาตัวนั้น แต่ถ้ามีหลายตัวจะปล่อยให้เป็นช่องว่างไปด้วย “” (แสดงว่ายังไม่แน่ใจในคำตอบนั่นเอง)

ดูสูตรใน Possible Number ตารางซ้าย

ถ้าลองดับเบิ้ลคลิ๊กที่ AU8 จะได้ดังนี้

=IF(OR(GameState=0,$J$6=1,$J$16=1,AND($J$6="",OR($J$16=1,$J$16=""),$B$16<>1,$C$16<>1,$D$16<>1,$E$16<>1,$F$16<>1,$G$16<>1,$H$16<>1,$I$16<>1,$J$15<>1,$J$17<>1,$J$18<>1,$J$19<>1,$J$20<>1,$J$21<>1,$J$22<>1,$J$23<>1,$H$15<>1,$I$15<>1,$J$15<>1,$H$16<>1,$I$16<>1,$H$17<>1,$I$17<>1,$J$17<>1,OR($W$5<>"",$Z$5<>"",$AC$5<>"",$W$11<>"",$Z$11<>"",$AC$11<>""),OR($AF$5<>"",$AI$5<>"",$AL$5<>"",$AF$11<>"",$AI$11<>"",$AL$11<>""),OR($AO$14<>"",$AO$17<>"",$AO$20<>"",$AR$14<>"",$AR$17<>"",$AR$20<>""),OR($AO$23<>"",$AO$26<>"",$AO$29<>"",$AR$23<>"",$AR$26<>"",$AR$29<>""))),1,"")

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

จะเห็นว่าสูตรมันพยายามเขียน Logic ออกมาว่าเมื่อไหร่ควรจะแสดงเลข 1 (ช่อง AU8 เป็น Possible Number ของเลข 1) เมื่อไหร่ควรจะปล่อยเป็น Blank

สูตรแม้จะดูวุ่นวาย แต่ส่วน Logical Test ก็มีหลักการดังนี้

ถ้าตรงตามเงื่อนไขอย่างน้อยอันใดอันหนึ่งของสี่เงื่อนไขนี้ จะได้ผลลัพธ์เป็น 1 ทันที นอกนั้นจะได้เป็น Blank

• GameState=0
• ช่อง Starting Position ใส่เป็นเลข 1 ไว้แล้ว
• ช่อง Final Position เป็นเลข 1
• เงื่อนไขพิเศษ (เงื่อนไขข้อนี้แหละที่ยาวมากๆ เดี๋ยวขอเขียนอธิบายเพิ่ม)

เงื่อนไขพิเศษมี Logic ดังนี้ (โดยทุกข้อย่อยต้องเป็นจริง)

• ช่อง Starting Position ยังว่าง (ตัวนี้จะช่วยตัด Possible Number ได้มหาศาล)
• ช่อง Final Position เป็นเลข 1 หรือยังว่าง
• Final Position ในแถวเดียวกัน (ยกเว้นช่องตัวเอง) ไม่มีเลข 1
• Final Position ในคอลัมน์เดียวกัน (ยกเว้นช่องตัวเอง) ไม่มีเลข 1
• Final Position ในพื้นที่ 3×3 (ยกเว้นช่องตัวเอง) ไม่มีเลข 1
• Possible Number เป็นไปตามเงื่อนไขนี้ (ซึ่งก็ซับซ้อนอีก)

=AND(...,
OR($W$5<>"",$Z$5<>"",$AC$5<>"",$W$11<>"",$Z$11<>"",$AC$11<>""),
OR($AF$5<>"",$AI$5<>"",$AL$5<>"",$AF$11<>"",$AI$11<>"",$AL$11<>""),
OR($AO$14<>"",$AO$17<>"",$AO$20<>"",$AR$14<>"",$AR$17<>"",$AR$20<>""),
OR($AO$23<>"",$AO$26<>"",$AO$29<>"",$AR$23<>"",$AR$26<>"",$AR$29<>"")
)

คือดูในพื้นที่แนวเดียวกันว่าใน block นั้นอย่างน้อยตัวในตัวหนึ่งใน block จะต้องไม่ว่าง (แต่ละ block อยู่ภายใต้ OR 1 ชุด) แต่ไม่สนใจตัวที่อยู่ในแถวและคอลัมน์เดียวกันนะ โดยเงื่อนไขจะต้องเป็นจริงทุก block (เพราะว่าอยู่ภายใต้ AND)

การเขียนแบบนี้หมายถึงอะไร? ทำไมต้องเช็คว่าตัวใดตัวหนึ่งจะต้องไม่ว่างด้วย?

การเช็คว่าตัวใดตัวหนึ่งไม่ว่าง มันก็คือ การมองว่าในแต่ละ block 3×3 มีการลงเลข possible number นั้นๆ ไปแล้วในแนวอื่นที่ไม่ตรงกับตัวมันนั่นเอง เรียกได้ว่าถ้ามีการลงเลข 1 ในแนวอื่นแล้ว แสดงว่าช่องมันเองยังเป็นไปได้ที่จะเป็นเลข 1 อยู่นั่นเองครับ

สูตรทั้งหมดเป็นสูตรแบบงูกินหาง

ถ้าสังเกตดู สูตรใน Final Position มีการอ้างอิงจาก Possible Number และสูตรใน Possible Number ก็มีการคำนวณจาก Final position ด้วย แถม Possible Number ก็อ้างอิงกันเองพันกันมั่วไปหมดอีก ถ้าเราใช้สูตรพวกนี้ในโหมดการทำงานปกติ มันจะด่าเราว่าเราเขียนสูตรแบบ Circular Reference ทันที

เพื่อให้สูตร Circular Reference ทำงานได้ เราจึงต้องเปิดโหมดการทำงานแบบ Iterative Calculation ด้วย ซึ่งใน Template นี้มันเลือกไว้ให้อยู่แล้ว และตั้งให้ทำทีละ 1 Step แถมทำในโหมด Manual Cal ที่ต้องกด F9 เองด้วย

ลองใส่เลขทดสอบสูตร

ลองทดสอบการทำงานของสูตร โดยใส่ Starting Position เป็น 1 ลงไปช่องนึง แล้วปรับ Game Stage เป็น 1 แล้ว F9 รัวๆ

จะเห็นว่าการกด F9 ทีแรก จะทำให้ Possible Number ในพื้นที่ AR8:AT10 นั้นมีเลข 1 โผล่มาตัวเดียวเลย (เพราะเงื่อนไขช่อง Starting Position ยังว่าง $I$6=”” นั้นเป็นเท็จไปแล้ว) ทำให้ Final Position สามารถมีเลข 1 โผล่ออกมาได้เพราะ COUNT ได้ตัวเดียวในที่สุด

พอกด F9 ครั้งต่อๆ ไปจะทำให้ Possible Number ได้มีการตัดเลข 1 ในแนวเดียวกันออกจนหมดอีกด้วย อันนี้เป็นเพราะว่่าใน Final Position มีการลงเลข 1 ไปแล้วในแนวเดียวกัน ทำให้เงื่อนไขพิเศษที่เช็คใน Final Position เป็น FALSE นั่นเอง พอเป็น FALSE ทำให้ได้ค่า “” ออกมาในที่สุด

ผมลองใส่เลข 1 เพิ่ม ในระดับที่มันควรตอบได้แล้วว่าเลข 1 ตัวสุดท้ายอยู่ที่ไหน แต่มันก็ดันไม่ให้คำตอบออกมา เพราะ Possible Number ยังคงมีหลายเลขอยู่ แสดงว่า Logic เท่านี้ยังไม่เพียงพอ

ในทีุ่ดก็ถึงเวลาของ Solution Numbers ที่เป็น Game Stage 2 ซักที

หากไปดูสูตรใน BL14 จะเห็นสูตรนี้

=IF(AND(GameState=2,OR(AND($W$14="",$Z$14="",$AC$14="",$AF$14="",$AL$14="",$AO$14="",$AR$14="",$AU$14=""),AND($AI$5="",$AI$8="",$AI$11="",$AI$17="",$AI$20="",$AI$23="",$AI$26="",$AI$29=""),AND($AF$14="",$AL$14="",$AF$17="",$AI$17="",$AL$17="",$AF$20="",$AI$20="",$AL$20=""))),1,"")

เงื่อนไขที่มันจะแสดงเลข Solution เช่นเลข 1 ออกมาคือ ต้องมี Game Stage เป็น 2 และต้องทำเงื่อนไขพิเศษของ Solution Board ดังนี้ (อย่างน้อยข้อใดข้อหนึ่งต้องเป็นจริง)

• ในแถวเดียวกันนั้นว่างทั้งหมด
• ในคอลัมน์เดียวกันนั้นว่างทั้งหมด
• ในพื้นที่ Block เดียวกันนั้นว่างทั้งหมด

นี่คือสาเหตุที่ว่าพอเราปรับ Game Stage เป็น 2 แล้วกด F9 มันจึงมีเลขโผล่มาที่ Solution Numbers ซึ่งทำให้เลขโผล่ที่ Final Position ได้ในที่สุด (Game Stage2 ก็ยังสามารถคำนวณ Possible Numbers เพิ่มได้อยู่นะ)

สรุป

และนี่ก็คือหลักการคิดของตัว Sudoku Solver นี้ครับ ซึ่งสูตรที่แสดงออกมาใน Template ล่าสุดที่เราใช้กันอยู่นี้นั้นดูถึกอย่างมาก ซึ่งจริงๆ แล้วในอดีต Template นี้สูตรไม่ได้ถึกขนาดนี้ แต่เกิดจากการเขียนสูตรพวก INDEX ผสมกับ ROW/COLUMN/MOD ที่ซับซ้อนผสมอยู่ใน Defined Name ต่างหาก (ไม่แน่ใจเหมือนกันว่าทำไมถึงมาแก้สูตรให้กลายเป็นแบบถึก)

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