Ở trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu về đệ quy. Ngày hôm nay, chúng ta sẽ tiếp tục đi tìm hiểu về quay lui, một khái niệm gắn liền với đệ quy và được áp dụng rất nhiều trong các bài toán. Hiểu về quay lui sẽ giúp các bạn hiểu rõ logic của hàm đệ quy hơn.

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học
• Vector trong C++
• Đệ quy

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Khái niệm quay lui
• Cách áp dụng quay lui vào bài toán

Bài toán đặt ra

Cho bàn cờ vua có kích thước n × n [4 ≤ n ≤ 10], các cột được đánh số từ 1 đến n theo chiều từ trái qua phải, các hàng được đánh số từ 1 đến n theo chiều từ trên xuống dưới. Hãy tìm cách đặt n quân hậu trên bàn cờ sao cho không có 2 quân hậu nào ở cùng một hàng, cột hay đường chéo.

Ví dụ:

Giải thích ví dụ: Output trong ví dụ trên là vị trí các quân hậu trong bàn cờ thoả mãn yêu cầu. Dưới đây là hình minh hoạ cho vị trí các quân hậu.

Ý tưởng chung

Trước hết, cần phải nói rằng: Có thể có rất nhiều cách đặt quân hậu trên bàn cờ thoả mãn yêu cầu đề bài. Trên thực tế, với n = 8 thì có 12 cách xếp các quân hậu thoả mãn.

Bây giờ thì hãy quay lại với bài toán của chúng ta. Bài toán trên thực chất là một bài toán rất nổi tiếng trong Tin học đã được đặt ra vào những năm 1848. Trong các cách giải được đưa ra, cách phổ biến nhất đó chính là: Thử. Ta sẽ thử đặt 8 quân hậu vào các ô của bàn cờ sau đó kiểm tra xem liệu cách đặt đó có phù hợp hay không.

Vậy thì chúng ta nên thử như thế nào đây?

• Do các quân hậu không thể cùng nằm trên một hàng nên chắc chắn khi thử chúng ta sẽ phải đặt n quân hậu trên n hàng riêng biệt. Như vậy là đã đảm bảo điều kiện về hàng.
• Với mỗi hàng chúng ta sẽ đặt thử các quân hậu vào các vị trí trên hàng đó rồi tiến hành kiểm tra 2 điều kiện còn lại. Việc đặt thử này có thể tiến hành bằng việc dùng vòng lặp để duyệt qua tất cả các vị trí.
• Nếu gặp một trường hợp thoả mãn chúng ta có thể in ra kết quả và thoát chương trình.

Chi tiết về chuyện thử như thế nào hãy để ở phần sau. Bây giờ hãy xem xét một vấn đề: Chúng ta sẽ kiểm tra điều kiện không cùng cột và đường chéo như thế nào?

• Với điều kiện về cột, chúng ta sẽ sử dụng một mảng đánh dấu lại các cột đã có quân hậu. Nếu có một quân hậu được đặt vào cột đã được đánh dấu thì cách xếp hậu là không thoả mãn. Như vậy là ta đã kiểm tra được điều kiện về cột
• Với đường chéo, mọi thứ sẽ phức tạp hơn. Ta nhận thấy, với mỗi quân hậu sẽ có 2 đường chéo để di chuyển. Chúng ta sẽ quy ước: đường chéo có chiều từ trái qua phải sẽ là “đường chéo chính”, đường chéo có chiều từ phải qua trái sẽ là “đường chéo phụ”.

• Hãy cùng nhìn vào các ô ở đường chéo chính trong hình minh hoạ trên. Toạ độ các ô đó là [1, 2]; [2, 3]; [3, 4]. Các bạn đã nhận ra điểm đặc biệt của các toạ độ kia chưa? Hiệu số giữa chỉ số hàng và cột là cố định với tất cả các ô thuộc cùng một đường chéo chính và mỗi đường chéo chính lại có một hiệu số riêng đặc trưng cho nó.
• Bây giờ hãy cùng nhìn vào đường chéo phụ trong hình minh hoạ. Toạ độ các ô trên đường chéo phụ là [1,2]; [2, 1]. Khác với đường chéo chính, tổng của chỉ số hàng và chỉ số cột của các ô thuộc cùng một đường chéo phụ là giống nhau và mỗi đường chéo phụ lại có một tổng riêng đặc trưng cho nó.
• Từ hai nhận xét trên, ta có thể dùng hai mảng đánh dấu lại hiệu của đường chéo chính và tổng của đường chéo phụ. Nếu quân hậu được đặt vào đường chéo đã được đánh dấu thì có nghĩa là không hợp lệ.

Triển khai ý tưởng

Chúng ta hiện tại sẽ có hai công việc chính:

• Đặt thử các quân hậu
• Kiểm tra tính hợp lệ của quân hậu được đặt vào

Với việc kiểm tra tính hợp lệ, chúng ta chỉ cần dùng 3 mảng đánh dấu một chiều với mục tiêu như đã trình bày ở trên. Việc này là không khó khăn. Bây giờ, vấn đề chính sẽ là làm sao để đặt thử các quân hậu.

Hãy thử hình dung luồng chạy của chương trình trong ví dụ ban đầu qua đoạn mã giả sau:

• Xét hàng 1, đặt thử quân hậu tại vị trí cột 1. Phép đặt hợp lệ. Ta đánh dấu các cột, 2 đường chéo chứa quân hậu này. Chuyển qua xét hàng 2.
• Xét hàng 2, đặt thử quân hậu tại vị trí cột 1. Phép đặt không hợp lệ do cùng cột với quân hậu đặt trước đó [hàng 1].
• Xét hàng 2, đặt thử quân hậu tại vị trí cột 2. Phép đặt không hợp lệ do cùng đường chéo chính với quân hậu đặt trước đó [hàng 1].
• Xét hàng 2, đặt thử quân hậu tại vị trí cột 3. Phép đặt hợp lệ. Ta đánh dấu các cột, 2 đường chéo chứa quân hậu này. Chuyển qua xét hàng 3.
• Xét hàng 3, đặt thử quân hậu tại vị trí cột 1. Phép đặt không hợp lệ do cùng cột với quân hậu đặt trước đó [hàng 1].
• Xét hàng 3, đặt thử quân hậu tại vị trí cột 2. Phép đặt không hợp lệ do cùng đường chéo phụ với quân hậu đặt trước đó [hàng 2].
• Xét hàng 3, đặt thử quân hậu tại vị trí cột 3. Phép đặt không hợp lệ do cùng cột với quân hậu đặt trước đó [hàng 2].
• Xét hàng 3, đặt thử quân hậu tại vị trí cột 4. Phép đặt không hợp lệ do cùng đường chéo chính với quân hậu đặt trước đó [hàng 2].
• Do các phương án với hàng 3 đều không khả thi, quay lại xét hàng 2.
• Xét hàng 2, xoá bỏ đánh dấu về cột và 2 đường chéo với cột 3 đang được chọn.
• Xét hàng 2, đặt thử quân hậu tại vị trí cột 4 [do vị trí lần trước xét đang là 3]. Phép đặt hợp lệ. Ta đánh dấu các cột, 2 đường chéo chứa quân hậu này. Chuyển qua xét hàng 3.
• Quá trình tương tự
• Khi ta xét đến hàng thứ 5 [hàng không có thật] có nghĩa là cả 4 hàng cần đặt quân hậu đều đã đặt thành công thì ta tin ra kết quả và dừng chương trình.

Nhìn vào quá trình vừa rồi, các bạn có thấy quen không? Nếu chưa nhận ra được, hãy nhìn vào mô hình bên dưới của lời giải trên.

Các bạn đã nhận ra mô hình này là của thứ gì chưa? Đó chính là mô hình của đệ quy mà ở bài trước mà mình đã trình bày. Phương pháp được sử dụng ở đây gọi là quay lui. Thế thì chính xác quay lui là gì?

Quay lui

Khái niệm

Quay lui là một thuật toán được thiết kế dựa trên đệ quy với ý tưởng: Tại mỗi bước, ta sẽ tìm một lời giải hợp lí cho bước đó rồi tiếp tục xét đến bước tiếp theo.

Thực chất, trong cuộc sống, có rất nhiều hành động chúng ta đang áp dụng chiến thuật quay lui. Giả sử, chúng ta biết nhà một người bạn chắc chắn nằm ở một trong những ngõ của con đường này nhưng chúng ta không biết chính xác ngõ nào. Có phải khi đó, ta sẽ đi vào từng ngõ. Với ngõ đó, ta sẽ đến từng nhà, hỏi thăm xem liệu đó có phải nhà chúng ta cần tìm không. Nếu đi đến cuối ngõ mà vẫn không tìm thấy, ta sẽ “quay lui” về đường chính để đi tìm ở một ngõ khác.

Ý tưởng

Sử dụng chiến lược quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.

Mô hình chung

Giả thiết cấu hình cần liệt kê có dạng x1, x2, x3,…,xn. Khi đó thuật toán quay lui được thực hiện qua các bước sau:

• Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử cho x1 ta sẽ:
• Xét tất cả các giá trị x2 có thể nhận, thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử cho x2 ta sẽ xét các giá trịx3 có thể nhận và tiếp tục như vậy
• Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó. In ra cấu hình tìm được.

Giải quyết bài toán ban đầu

Vậy chính xác, bài toán ban đầu sẽ được code như thế nào với tư tưởng quay lui.

`

include

using namespace std; const int MaxN = 1 + 1e5; int n; bool mark[3][MaxN]; vector res; void Try[int row]{

if[row == n + 1]{  
    for[int i = 0 ; i < n ; ++i] cout