วิธีแก้

วิธีแก้ซูโดกุโดยไม่เดา

hugh
เผยแพร่:อัปเดต:อ่าน 9 นาที
วิธีแก้ซูโดกุโดยไม่เดา

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

ตัวเลขที่เป็นไปได้คือความเป็นไปได้ ตัวเลขที่ใส่แล้วคือข้อสรุป อย่าสับสนสองอย่างนี้

อะไรนับเป็นการเดา

การเดาคือการผูกมัดกับตัวเลขโดยไม่มีหลักฐานทางตรรกะ มักพร้อมแผนจะ Undo ถ้าเกิดข้อขัดแย้ง โน้ตตัวเลขที่เป็นไปได้ไม่ใช่การเดา: มันบันทึกทุกค่าที่ข้อจำกัดที่รู้แล้วยังอนุญาต การตัดขั้นสูงก็ไม่ใช่การเดาเมื่อแพทเทิร์นถูกต้อง ตัวอย่างเช่น X-Wing อาจไม่บอกว่าตัวเลขไปที่ไหน แต่พิสูจน์ว่าตัวเลขนั้นไปที่ไหนไม่ได้ การทดสอบที่ใช้จริงง่าย: ก่อนเปลี่ยนตาราง คุณระบุกฎที่ยังจริงในทุกทางจบที่เป็นไปได้ได้หรือไม่

เวิร์กโฟลว์ไม่เดาที่ทำซ้ำได้

  1. กวาดหาการใส่ตรง ๆ เริ่มด้วยซิงเกิลเปลือยและซิงเกิลซ่อนในแถว คอลัมน์ และบล็อกที่หนาแน่น ตรวจหน่วยที่การใส่ใหม่แต่ละครั้งแตะถึงอีกครั้ง
  2. สร้างรายการตัวเลขที่เป็นไปได้ที่ซื่อสัตย์ เมื่อการกวาดตรง ๆ ค้าง ให้จดตัวเลขที่ข้อจำกัดทั้งสามยังอนุญาต ลบโน้ตเก่าทันทีหลังการใส่ทุกครั้ง
  3. ค้นตามลำดับเทคนิคที่คงที่ ลองคู่ ล็อกแคนดิเดต สามตัว และแพทเทิร์น fish หลังข้อสรุปที่ง่ายหมดแล้วเท่านั้น ลำดับที่นิ่งช่วยไม่ให้ล่าทั้งตารางแบบสุ่ม
  4. ต้องมีหลักฐานที่พูดออกมาได้ พูดต้นทางและผล: “5 ถูกล็อกไว้ที่แถว 2 ในบล็อกนี้ ดังนั้น 5 โผล่ที่อื่นในแถว 2 ไม่ได้” ถ้าประโยคคลุมเครือ อย่าลบตัวเลขที่เป็นไปได้
  5. รีเซ็ตมุมมองเมื่อติด ตรวจโน้ต เปลี่ยนตัวเลขที่เป็นไปได้หรือหน่วยที่กำลังกวาด แล้วกลับไปหาซิงเกิล อย่าเปลี่ยนความหงุดหงิดเป็นการใส่ที่ไม่มีหลักฐาน
{3,8}123
เวิร์กโฟลว์: เก็บ {3,8} เป็นตัวเลขที่เป็นไปได้ ตามการตัดที่มีเหตุผล และใส่ตัวเลขเมื่อความเป็นไปได้หนึ่งถูกตัดแล้วเท่านั้น

ตัวอย่างทีละขั้น: แทนการเดาสองทางด้วยตรรกะ

สมมติ r6c4 มีตัวเลขที่เป็นไปได้ {3,8} การเลือก 3 จะเป็นการเดา เพราะทั้งสองค่ายังผ่านกฎแถว คอลัมน์ และบล็อกทันที แทนการแยกกิ่ง ให้ดูว่า 3 และ 8 โผล่ที่ไหนในหน่วยที่เกี่ยวข้อง แล้วหาแพทเทิร์นที่ตัดตัวใดตัวหนึ่ง

  1. อย่าใส่ตัวเลขที่เป็นไปได้ทั้งสอง ปล่อย {3,8} เป็นโน้ต การไม่มีตัวซ้ำทันทีไม่ใช่หลักฐานว่ากิ่งหนึ่งถูก ข้อขัดแย้งอาจโผล่หลายตาถัดไป
  2. ดูตำแหน่งในบล็อก ถ้า 3 ทั้งหมดในบล็อกอยู่ในแถว 6 บล็อกชี้ไปที่แถว 6 ใช้ล็อกแคนดิเดตตัด 3 จากช่องอื่นในแถว 6 นอกบล็อก
  3. ส่งต่อการตัด สมมติ r6c9 เปลี่ยนจาก {3,5} เป็น {5} ใส่ 5 แล้วอัปเดตแถว 6 คอลัมน์ 9 และบล็อก ตัวเลขใหม่อาจตัด 8 จากช่องร่วมกลุ่มกับ r6c4
  4. กลับมาใส่เมื่อมีเหตุผลแล้วเท่านั้น ถ้าตรรกะภายหลังตัด 8 จาก r6c4 ให้ใส่ 3 และบันทึกเหตุผล ค่าสุดท้ายเดียวกันตอนนี้เป็นข้อสรุป ไม่ใช่กิ่งที่คุณบังเอิญลองก่อน

นิสัยที่พรางการเดา

เรียกตัวเลขที่ดูเข้าท่าว่า “เห็นชัด”

ค่าอาจเข้ากับแถว คอลัมน์ และบล็อกปัจจุบันแล้วยังผิด “ดูถูก” ไม่ใช่กฎ ชี้ซิงเกิล เซตย่อย หรือแพทเทิร์นที่บังคับมัน

ใช้ข้อขัดแย้งโดยไม่ติดตามกิ่ง

กิ่งทดลองยาวและพลาดง่าย ถ้ากำลังเรียนการแก้เชิงตรรกะ ให้เลี่ยง เพื่อให้เทคนิคที่โจทย์กำลังสอนยังมองเห็น

เชื่อตัวเลขที่เป็นไปได้ที่เก่า

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

เช็กลิสต์ฝึกไม่เดา

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

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

คำถามการแก้โดยไม่เดา

ซูโดกุที่ถูกต้องทุกอันแก้โดยไม่เดาได้ไหม

โจทย์ที่สร้างดีมีเจตนาให้มีคำตอบเดียว แต่วิธีตรรกะที่ต้องใช้อาจเกินชุดเครื่องมือปัจจุบันของผู้แก้ ในทางปฏิบัติ ระดับความยากที่เผยแพร่ตั้งใจให้ตรงกับชุดเทคนิคที่รู้จัก

การใช้คำใบ้เหมือนการเดาไหม

ไม่ คำใบ้ที่มีประโยชน์ชี้ตาที่ตรรกะรองรับ ถือเป็นบทเรียน: ตั้งชื่อเทคนิค ตรวจว่าทำไมใช้ได้ แล้วหาแพทเทิร์นเดียวกันในภายหลังของคำตอบ

โน้ตตัวเลขที่เป็นไปได้อนุญาตในการแก้เชิงตรรกะไหม

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

ถ้าไม่มีเทคนิคที่รู้จักใช้ได้ ควรทำอะไร

ตรวจโน้ตก่อน แล้วกวาดซิงเกิลอีกครั้ง จากนั้นเทียบระดับความยากของโจทย์กับชุดเทคนิคของคุณ การเรียนวิธีถัดไปมีค่ากว่าการผูกมัดที่อธิบายไม่ได้

backtracking นับเป็นอัลกอริทึมแก้ที่ถูกต้องไหม

ใช่สำหรับซอฟต์แวร์และการตรวจคำตอบ คู่มือนี้โฟกัสการแก้เชิงตรรกะของคน เป้าคืออธิบายข้อสรุปแต่ละขั้นและเรียนรู้โครงของโจทย์

บทความที่เกี่ยวข้อง