Backtracking — พื้นฐาน & แนวคิด

Backtracking (การย้อนรอย) คือเทคนิคสำหรับโจทย์ที่ต้อง build (สร้าง) คำตอบทีละชิ้น และมีหลาย choice (ทางเลือก) ในแต่ละก้าว เช่น หาทุก combination (ชุดค่า) ที่เป็นไปได้ ทุก permutation (การจัดเรียง) หรือทุกวิธีเลือกของ ไอเดียหลักคือ choose (เลือก) ทางหนึ่ง แล้ว explore (ลงลึก) ต่อไปเรื่อย ๆ ถ้าเจอทางตันหรือ explore ครบแล้ว ก็ backtrack (ถอยกลับ) มายกเลิกการเลือกล่าสุด (undo) เพื่อไปลองทางอื่นแทน มันคือการ search (ค้นหา) แบบเป็นระบบที่รับประกันว่าจะไม่พลาดคำตอบไหนเลย

recursion tree — ภาพในหัวของ backtracking

ลองนึกภาพว่าเรากำลังเดินอยู่ในเขาวงกตที่แตกเป็นทางแยกเยอะมาก ทุกครั้งที่เจอทางแยก เรา choose เดินทางหนึ่งไปก่อน ถ้าสุดทางแล้วไม่เจอทางออก เราก็ backtrack ย้อนกลับมาที่ทางแยกเดิมแล้วลองอีกทาง Backtracking ทำแบบเดียวกันเป๊ะ ๆ แต่ทำด้วย recursion (การเรียกตัวเอง)

เราวาดการทำงานเป็น recursion tree (ต้นไม้การเรียกตัวเอง) ได้ แต่ละ node (โหนด) คือ state (สถานะ) ปัจจุบัน คือคำตอบที่สร้างไปแล้วบางส่วน และแต่ละ branch (กิ่ง) ที่แตกออกไปคือ choice หนึ่งที่เราลอง สมมติต้อง build string (สตริง) ยาว 2 ตัวจากตัวอักษร a และ b ต้นไม้จะเป็นแบบนี้:

                   ""            <- ยังไม่เลือกอะไร
             /    \
          "a"      "b"        <- เลือกตัวแรก
         /   \    /   \
      "aa" "ab" "ba" "bb"     <- เลือกตัวที่สอง (คำตอบครบ)

แต่ละ leaf (ใบ) ของ tree คือคำตอบที่สมบูรณ์หนึ่งชุด การเดินลงจาก root (ราก) ไปหา leaf คือการ explore (ลงลึก) และเมื่อกลับขึ้นมาเพื่อไป branch ข้าง ๆ คือการ backtrack (ถอยกลับ)

template สามจังหวะ: choose → explore → unchoose

หัวใจของ backtracking ทุกข้อจะมี structure (โครง) เดียวกัน จำ template (แม่แบบ) สามจังหวะนี้ไว้: choose (เลือก) → explore (ลงลึก) → unchoose (ถอย) ทุกโจทย์ในหมวดนี้จะเข้ารูปนี้หมด แค่เปลี่ยนว่า choices คืออะไร และเงื่อนไข คำตอบครบ คืออะไร

def backtrack(path, choices):
        if is_complete(path):        # <- แทนที่ด้วยเงื่อนไข "คำตอบครบแล้ว" ของโจทย์
            result.append(path[:])   # เก็บสำเนาคำตอบ (สำคัญ! ต้อง copy)
            return
        for choice in choices:       # ลองทุกทางเลือกที่ทำได้
            path.append(choice)      # 1) choose  — เลือกทางนี้
            backtrack(path, ...)     # 2) explore — ลงลึกต่อ
            path.pop()               # 3) unchoose — ถอย เอาออกเพื่อลองทางอื่น