แผนการเรียน
/

Day 04: Lab Practice
Mastering Backtracking

โจทย์ 10 ข้อเพื่อท้าทายทักษะการย้อนรอย

1. Generating Subsets: สร้างทุกสับเซต 2. Generating Permutations: สร้างทุกการสลับ 3. N-Queens Problem: ปริศนาควีน N ตัว 4. Subset Sum: หาเซตที่รวมได้ค่า T 5. 4 thought: การเติมเครื่องหมาย (Kattis) 6. Grid Paths: เส้นทางในตารางและ Pruning 7. Knight’s Tour: การเดินอัศวินให้ครบช่อง 8. Balanced Parentheses: สร้างวงเล็บที่สมดุล 9. Binomial Coefficients: การเลือกแบบเวียนเกิด 10. Palindrome Partitioning: การแบ่งสตริง

1. Subsets & 2. Permutations

Subsets:

สร้างเซตย่อยทั้งหมดจากเซต {0, 1, ..., n-1}

คำใบ้: ในแต่ละตัวเลข มี 2 ทางเลือกคือ "เลือก" หรือ "ไม่เลือก"

Permutations:

เรียงสับเปลี่ยนเลข $n$ ตัวในทุกรูปแบบที่เป็นไปได้

คำใบ้: ใช้ array chosen เพื่อจำว่าเลขใดใช้ไปแล้ว

ขั้นตอนการแก้โจทย์

Subsets: เรียก search(k+1) สองครั้ง ครั้งแรกไม่ต้องใส่ค่า $k$ ครั้งที่สองให้ push_back(k) ก่อนเรียก และอย่าลืม pop_back() หลังเรียกเสร็จ
Permutations: วนลูป 0 ถึง $n-1$ หาก !chosen[i] ให้ทำ chosen[i]=true, ใส่ลงในเวกเตอร์, เรียกตัวเอง, แล้วทำ chosen[i]=false และดึงออก (Undo)

3. The N-Queens Challenge

วางควีน $n$ ตัวบนกระดาน $n \times n$ ไม่ให้โจมตีกัน

คำใบ้: วางทีละแถว (Row) และเช็คแนวตั้ง (Column) รวมถึงแนวทแยงทั้งสอง (Diagonals)

Optimization Tip: ใช้ array เก็บสถานะแนวทแยง diag1[x+y] และ diag2[x-y+n-1] เพื่อเช็คใน $O(1)$

Backtracking Strategy

  1. 1. เริ่มต้นที่แถว $y=0$
  2. 2. วนลูปตำแหน่ง $x$ (คอลัมน์) แต่ละช่องบนแถวนั้น
  3. 3. ตรวจสอบว่าคอลัมน์ $x$ และแนวทแยงทั้งสองว่างหรือไม่
  4. 4. ถ้าว่าง: ทำเครื่องหมายว่าไม่ว่าง (Mark) และเรียก search(y+1)
  5. 5. **สำคัญ:** เมื่อกลับจากฟังก์ชัน ให้ล้างเครื่องหมาย (Unmark) เพื่อลองตำแหน่งอื่น

4. Subset Sum & 5. 4 thought

Subset Sum:

เลือกตัวเลขจากเซต $S$ ให้รวมกันได้ $T$

คำใบ้: เหมือนการสร้างสับเซตแต่ส่งผลรวมปัจจุบัน (Current Sum) ไปในพารามิเตอร์ด้วย

4 thought:

ใช้เลข 4 สี่ตัวและเครื่องหมาย $+ - * /$ เพื่อหาผลลัพธ์ $n$

คำใบ้: มีช่องว่าง 3 ช่อง แต่ละช่องเลือกได้ 4 เครื่องหมาย รวม $4^3=64$ วิธี

Logic Guide

Subset Sum: search(idx, current_sum) ถ้า current_sum == T ตอบ YES. ถ้า idx == n หรือ current_sum > T (Pruning) ให้ย้อนกลับ
4 thought: เขียนลูปซ้อนกัน 3 ชั้นเพื่อสุ่มเครื่องหมาย แล้วสร้างฟังก์ชันคำนวณลำดับความสำคัญ (Precedence) ของ $+ - * /$ ให้ถูกต้อง

6. Grid Paths & 7. Knight's Tour

Grid Paths (Pruning):

เดินในตาราง $7 \times 7$ ให้ครบทุกช่องโดยไม่ซ้ำจุดเดิม

คำใบ้: ใช้ Symmetry Pruning เพื่อลดการคำนวณลงครึ่งหนึ่ง

Knight's Tour:

เดินม้าหมากรุกให้ครบ 64 ช่องบนกระดาน $8 \times 8$

คำใบ้: ลองเดินไปยังช่องที่มีทางไปต่อ "น้อยที่สุด" ก่อน (Warnsdorf's Rule)

Advanced Backtracking

Grid Paths: หากถึงจุดจบก่อนเวลา หรือชนกำแพงที่แบ่งตารางเป็นสองส่วนที่ไม่สามารถไปถึงได้ทั้งคู่ ให้ตัดกิ่งทันที (Pruning)

Knight's Tour: สร้างอาเรย์การเคลื่อนที่ของม้า 8 ทิศทาง เช็คขอบกระดานและช่องที่เคยไปแล้ว หากไปครบ 64 ช่องให้พิมพ์คำตอบและจบโปรแกรม

8. Parentheses | 9. Binomial | 10. Partitioning

8. Balanced Brackets
สร้างวงเล็บ $n$ คู่ที่ถูกต้อง เช่น (()). คำใบ้: นับจำนวนวงเล็บเปิดและปิดที่เหลือ
9. Binomial Coeff.
หา $\binom{n}{k}$ ด้วยสูตร $\binom{n-1}{k-1} + \binom{n-1}{k}$. คำใบ้: อย่าลืม Base Case $k=0$ หรือ $k=n$
10. Palindrome Partition
แบ่งสตริงเป็นส่วนๆ โดยทุกส่วนต้องเป็นพาลินโดรม. คำใบ้: ลองตัดสตริงที่ตำแหน่ง $i$ แล้วเช็คพาลินโดรมก่อนทำต่อ

Final Logic Sets

8. Brackets: solve(open, close, s) ถ้า open > 0 ใส่ ( ได้. ถ้า close > open ใส่ ) ได้ เพื่อรักษาความสมดุล

9. Binomial: การเขียนแบบ Recursive ตรงๆ จะช้ามากหาก $n$ ใหญ่ ควรใช้ **Memoization** เข้ามาช่วยจดบันทึกค่าที่คำนวณแล้ว

10. Palindrome: วนลูปจุดตัดจากตำแหน่งปัจจุบัน หากส่วนหน้าเป็นพาลินโดรม ให้เรียกฟังก์ชันย้อนรอยกับส่วนสตริงที่เหลือ

"The secret of mastering backtracking is to visualize the recursion tree."