บทเรียน 33

ALS-XZ

หลักการ

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

ทีละขั้นตอน

1. ดูชุดแรก ช่อง 2 ช่องนี้อยู่ในแถวเดียวกัน และรวมกันมีตัวเลือกต่างกัน 3 ตัว ซึ่งมากกว่าจำนวนช่องอยู่หนึ่งตัว เรียกว่า Almost Locked Set (ALS)
2. ทีนี้ดูชุดที่สอง ช่อง 3 ช่องนี้อยู่ในแถวเดียวกัน และรวมกันมีตัวเลือกต่างกัน 4 ตัว ซึ่งมากกว่าจำนวนช่องอยู่หนึ่งตัว จึงเป็น ALS เช่นกัน ทั้งสองชุดมีตัวเลือก 3 ร่วมกันในฐานะตัวเลือกร่วมจำกัด (RCC): ทุกช่องที่มีตัวเลือก 3 ในชุดหนึ่งเห็นทุกช่องที่มีตัวเลือก 3 ในอีกชุดหนึ่ง ดังนั้นตัวเลข 3 จึงวางได้ไม่เกินหนึ่งในสองชุดนี้ และไม่สามารถอยู่ในทั้งสองชุดพร้อมกันได้
3. ทั้งสองชุด มี 5 เป็นตัวเลือก เนื่องจากตัวเลข 3 วางได้ไม่เกินหนึ่งในสองชุด จึงมีอย่างน้อยหนึ่งชุดที่ไม่ใช้ 3 ชุดที่ไม่ใช้ 3 จะมีตัวเลือกต่างกันเหลืออยู่เท่ากับจำนวนช่อง จึงต้องวางตัวเลือกแต่ละตัวรวมถึง 5 ไว้ที่ใดที่หนึ่งภายในชุดนั้น ดังนั้น 5 จึงต้องถูกวางในอย่างน้อยหนึ่งในสองชุด และเราสามารถลบตัวเลือก 5 ออกจากช่องใดก็ตามที่อยู่นอกทั้งสองชุดและเห็นทุกช่องที่มีตัวเลือก 5 ในทั้งสองชุดได้ นี่คือที่มาของชื่อ: X คือ 3 ตัวเลือกที่ทั้งสองชุดมีร่วมกัน และ Z คือ 5 ตัวเลือกที่ถูกลบ