Thuật toán QUAY LUI 💎(Backtracking)
🧠 Thuật toán Quay lui (Backtracking) là gì?Quay lui (Backtracking) là một chiến lược giải quyết vấn đề bằng cách thử từng bước để tìm ra lời giải. Nếu một bước đi không dẫn đến kết quả mong muốn (vi phạm điều kiện), thuật toán sẽ "quay lại" bước trước đó, hủy bỏ lựa chọn vừa thực hiện và thử một hướng đi khác. Nó giống như việc bạn đi trong một mê cung: cứ đi tới ngã rẽ, nếu gặp đường cụt, bạn lùi lại ngã rẽ gần nhất và chọn lối đi còn lại.
👑 Ví dụ Kinh điển: Bài toán N quân hậu (N-Queens)Đây là ví dụ "huyền thoại" để minh họa cho Quay lui. Nhiệm vụ là đặt $N$ quân hậu trên một bàn cờ $N \times N$ sao cho không có hai quân hậu nào có thể ăn được nhau (không cùng hàng, không cùng cột, và không cùng đường chéo).Ý tưởng giải thuật:Thử: Đặt một quân hậu vào một cột ở hàng hiện tại. Kiểm tra: Nếu vị trí đó an toàn (không bị các quân hậu trước đó tấn công). Tiến tới: Di chuyển xuống hàng tiếp theo và lặp lại bước 1.Quay lui: Nếu không thể đặt quân hậu ở bất kỳ cột nào của hàng hiện tại, ta quay lại hàng phía trên, di chuyển quân hậu ở hàng đó sang vị trí tiếp theo.
Bước: 0 / 0
Sẵn sàng minh họa giải thuật Quay lui!