Giải Thuật Và Lập Trình: §3. Thuật Toán Quay Lui | V1Study

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Giải thuật và lập trình Phần 1: Bài toán liệt kê Lời mở đầu §1. Nhắc lại một số kiến thức đại số tổ hợp §2. Phương pháp sinh (GENERATION) §3. Thuật toán quay lui §4. Kỹ thuật nhánh cận Phần 2: Cấu trúc dữ liệu và giải thuật Lời mở đầu §1. Các bước cơ bản khi tiến hành giải các bài toán tin học §2. Phân tích thời gian thực hiện giải thuật §3. Đệ quy và giải thuật đệ quy §4. Cấu trúc dữ liệu biểu diễn danh sách §5. Ngăn xếp và hàng đợi §6. CÂY (TREE) §7. Ký pháp tiền tố, trung tố và hậu tố §8.1. Sắp xếp (SORTING) - Phần 1 §8.2. Sắp xếp (SORTING) - Phần 2 §9. Tìm kiếm (SEARCHING) Bài tập phần độ phức tạp giải thuật Bài tập phần Biểu diễn danh sách, Stack và Queue Phần 3: Quy hoạch động Lời mở đầu §1. Công thức truy hồi §2. Phương pháp quy hoạch động §3.1. Dãy con đơn điệu tăng dài nhất §3.2. Bài toán cái túi §3.3. Biến đổi xâu §3.4. Dãy con có tổng chia hết cho K §3.5. Phép nhân tổ hợp dãy ma trận §3.6. Bài tập luyện tập Phần 4: Các thuật toán trên đồ thị Lời mở đầu §1. Các khái niệm cơ bản §2. Biểu diễn đồ thị trên máy tính §3. Các thuật toán tìm kiếm trên đồ thị §4. Tính liên thông của đồ thị §5. Vài ứng dụng của các thuật toán tìm kiếm trên đồ thị §6. Chu trình Euler, đường đi Euler, đồ thị Euler §7. Chu trình Hamilton, đường đi Hamilton, đồ thị Hamilton §8. Bài toán đường đi ngắn nhất §9. Bài toán cây khung nhỏ nhất §10. Bài toán luồng cực đại trên mạng §11. Bài toán tìm bộ ghép cực đại trên đồ thị hai phía §12. Bài toán tìm bộ ghép cực đại với trọng số cực tiểu trên đồ thị hai phía. Thuật toán Hungari §13. Bài toán tìm bộ ghép cực đại trên đồ thị Giải thuật và lập trình: §3. Thuật toán quay lui Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

Thuật toán 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.

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

1) 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ử gán cho x1 ta sẽ:

2) Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3 … cứ tiếp tục như vậy đến bước:

...

n) 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ị đó, thông báo cấu hình tìm được (x1, x2, …, xn).

Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tử dạng (x1, x2, .., xn) bằng cách thử cho x1 nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x1 lại liệt kê tiếp cấu hình n - 1 phần tử (x2, x3, …, xn).

Mô hình của thuật toán quay lui có thể mô tả như sau:

{Thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận}

procedure Try(i: Integer);

begin

for (mọi giá trị V có thể gán cho xi) do

begin

<Thử cho xi := V>;

if (xi là phần tử cuối cùng trong cấu hình) then

<Thông báo cấu hình tìm được>

else

begin

<Ghi nhận việc cho xi nhận giá trị V (Nếu cần)>; Try(i + 1); {Gọi đệ quy để chọn tiếp xi+1}

<Nếu cần, bỏ ghi nhận việc thử xi := V, để thử giá trị khác>;

end;

end;

end;

Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1).

Liệt kê các dãy nhị phân độ dài n

Input/Output với khuôn dạng như trong P_1_02_1.PAS

Biểu diễn dãy nhị phân độ dài N dưới dạng (x1, x2, …, xn). Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị {0, 1} gán cho xi. Với mỗi giá trị thử gán cho xi lại thử các giá trị có thể gán cho xi+1.Chương trình liệt kê bằng thuật toán quay lui có thể viết:

P_1_03_1.PAS * Thuật toán quay lui liệt kê các dãy nhị phân độ dài n

program BinaryStrings;

const

InputFile = 'BSTR.INP';

OutputFile = 'BSTR.OUT';

max = 30;

var

x: array[1..max] of Integer;

n: Integer;

f: Text;

procedure PrintResult; {In cấu hình tìm được, do thủ tục tìm đệ quy Try gọi khi tìm ra một cấu hình}

var

i: Integer;

begin

for i := 1 to n do Write(f, x[i]);

WriteLn(f);

end;

procedure Try(i: Integer); {Thử các cách chọn xi}

var

j: Integer;

begin

for j := 0 to 1 do {Xét các giá trị có thể gán cho xi, với mỗi giá trị đó}

begin

x[i] := j; {Thử đặt xi}

if i = n then PrintResult {Nếu i = n thì in kết quả}

else Try(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp xi+1}

end;

end;

begin

Assign(f, InputFile); Reset(f);

ReadLn(f, n); {Nhập dữ liệu}

Close(f);

Assign(f, OutputFile); Rewrite(f);

Try(1); {Thử các cách chọn giá trị x1}

Close(f);

end.

Ví dụ: Khi n = 3, cây tìm kiếm quay lui như sau:

Result

Cây tìm kiếm quay lui trong bài toán liệt kê dãy nhị phân

LIỆT KÊ CÁC TẬP CON TỪ K PHẦN TỬ

Input/Output có khuôn dạng như trong P_1_02_2.PAS

Để liệt kê các tập con k phần tử của tập S = {1, 2, …, n} ta có thể đưa về liệt kê các cấu hình (x1, x2, …, xk) ở đây các xi ϵ S và x1 < x2 < … < xk. Ta có nhận xét:

xk ≤ n

xk-1 ≤ xk - 1 ≤ n - 1

…

xi ≤ n - k + i

…

x1 ≤ n - k + 1.

Từ đó suy ra xi-1 + 1 ≤ xi ≤ n - k + i (1 ≤ i ≤ k) ở đây ta giả thiết có thêm một số x0 = 0 khi xét i = 1. Như vậy ta sẽ xét tất cả các cách chọn x1 từ 1 (=x0 + 1) đến n - k + 1, với mỗi giá trị đó, xét tiếp tất cả các cách chọn x2 từ x1 + 1 đến n - k + 2,… cứ như vậy khi chọn được đến xk thì ta có một cấu hình cần liệt kê. Chương trình liệt kê bằng thuật toán quay lui như sau:

P_1_03_2.PAS * Thuật toán quay lui liệt kê các tập con k phần tử

program Combination;

const

InputFile = 'SUBSET.INP';

OutputFile = 'SUBSET.OUT';

max = 30;

var

x: array[0..max] of Integer;

n, k: Integer;

f: Text;

procedure PrintResult; (*In ra tập con {x1, x2, …, xk}*)

var

i: Integer; begin

Write(f, '{');

for i := 1 to k - 1 do Write(f, x[i], ', ');

WriteLn(f, x[k], '}');

end;

procedure Try(i: Integer); {Thử các cách chọn giá trị cho x[i]}

var

j: Integer; begin

for j := x[i - 1] + 1 to n - k + i do begin

x[i] := j;

if i = k then PrintResult else Try(i + 1);

end;

end;

begin

Assign(f, InputFile); Reset(F);

ReadLn(f, n, k);

Close(f);

Assign(f, OutputFile); Rewrite(f);

x[0] := 0;

Try(1);

Close(f);

end.

Nếu để ý chương trình trên và chương trình liệt kê dãy nhị phân độ dài n, ta thấy về cơ bản chúng chỉ khác nhau ở thủ tục Try(i) - chọn thử các giá trị cho xi, ở chương trình liệt kê dãy nhị phân ta thử chọn các giá trị 0 hoặc 1 còn ở chương trình liệt kê các tập con k phần tử ta thử chọn xi là một trong các giá trị nguyên từ xi-1 + 1 đến n - k + i. Qua đó ta có thể thấy tính phổ dụng của thuật toán quay lui: mô hình cài đặt có thể thích hợp cho nhiều bài toán, khác với phương pháp sinh tuần tự, với mỗi bài toán lại phải có một thuật toán sinh kế tiếp riêng làm cho việc cài đặt mỗi bài một khác, bên cạnh đó, không phải thuật toán sinh kế tiếp nào cũng dễ cài đặt.

LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K

Để liệt kê các chỉnh hợp không lặp chập k của tập S = {1, 2, …, n} ta có thể đưa về liệt kê các cấu hình (x1, x2, …, xk), ở đây các xi ϵ S và khác nhau đôi một.

Như vậy thủ tục Try(i) - xét tất cả các khả năng chọn xi - sẽ thử hết các giá trị từ 1 đến n, mà các giá trị này chưa bị các phần tử đứng trước chọn. Muốn xem các giá trị nào chưa được chọn ta sử dụng kỹ thuật dùng mảng đánh dấu:

Khởi tạo một mảng c1, c2, …, cn mang kiểu logic. Ở đây ci cho biết giá trị i có còn tự do hay đã bị chọn rồi. Ban đầu khởi tạo tất cả các phần tử mảng c là TRUE có nghĩa là các phần tử từ 1 đến n đều tự do.

Tại bước chọn các giá trị có thể của xi ta chỉ xét những giá trị j có cj = TRUE có nghĩa là chỉ chọn những giá trị tự do.

Trước khi gọi đệ quy tìm xi+1: ta đặt giá trị j vừa gán cho xi là đã bị chọn có nghĩa là đặt cj := FALSE để các thủ tục Try(i + 1), Try(i + 2)… gọi sau này không chọn phải giá trị j đó nữa.

Sau khi gọi đệ quy tìm xi+1: có nghĩa là sắp tới ta sẽ thử gán một giá trị khác cho xi thì ta sẽ đặt giá trị j vừa thử đó thành tự do (cj := TRUE), bởi khi xi đã nhận một giá trị khác rồi thì các phần tử đứng sau: xi+1, xi+2 … hoàn toàn có thể nhận lại giá trị j đó. Điều này hoàn toàn hợp lý trong phép xây dựng chỉnh hợp không lặp: x1 có n cách chọn, x2 có n - 1 cách chọn, …Lưu ý rằng khi thủ tục Try(i) có i = k thì ta không cần phải đánh dấu gì cả vì tiếp theo chỉ có in kết quả chứ không cần phải chọn thêm phần tử nào nữa.

Input: file văn bản ARRANGE.INP chứa hai số nguyên dương n, k (1 ≤ k ≤ n ≤ 20) cách nhau ít nhất một dấu cách.

Output: file văn bản ARRANGE.OUT ghi các chỉnh hợp không lặp chập k của tập {1, 2, …, n}.

ARRANGE.INP	ARRANGE.OUT
3 2	1 2
1 3
2 1
2 3
3 1
3 2

Thuật toán:

program Arrangement;

const

InputFile = 'ARRANGES.INP';

OutputFile = 'ARRANGES.OUT';

max = 20;

var

x: array[1..max] of Integer;

c: array[1..max] of Boolean;

n, k: Integer;

f: Text;

procedure PrintResult; {Thủ tục in cấu hình tìm được}

var

i: Integer;

begin

for i := 1 to k do Write(f, x[i],' ');

WriteLn(f);

end;

procedure Try(i: Integer); {Thử các cách chọn xi}

var

j: Integer; begin

for j := 1 to n do

if c[j] then {Chỉ xét những giá trị j còn tự do}

begin

x[i] := j;

if i = k then PrintResult {Nếu đã chọn được đến xk thì chỉ việc in kết quả}

else

begin

c[j] := False; {Đánh dấu: j đã bị chọn}

Try(i + 1); {Thủ tục này chỉ xét những giá trị còn tự do gán cho xi+1, tức là sẽ không chọn phải j}

c[j] := True; {Bỏ đánh dấu: j lại là tự do, bởi sắp tới sẽ thử một cách chọn khác của xi}

end;

end;

end;

begin

Assign(f, InputFile); Reset(f);

ReadLn(f, n, k);

Assign(f, OutputFile); Rewrite(f);

FillChar(c, SizeOf(c), True); {Tất cả các số đều chưa bị chọn}

Try(1); {Thử các cách chọn giá trị của x1}

Close(f);

end.

Nhận xét: khi k = n thì đây là chương trình liệt kê hoán vị.

BÀI TOÁN PHÂN TÍCH SỐ

Bài toán

Cho một số nguyên dương n ≤ 30, hãy tìm tất cả các cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách.

Cách làm:

Ta sẽ lưu nghiệm trong mảng x, ngoài ra có một mảng t. Mảng t xây dựng như sau: ti sẽ là tổng các phần tử trong mảng x từ x1 đến xi: ti := x1 + x2 + … + xi.

Khi liệt kê các dãy x có tổng các phần tử đúng bằng n, để tránh sự trùng lặp ta đưa thêm ràng buộc xi-1 ≤ xi.

Vì số phần tử thực sự của mảng x là không cố định nên thủ tục PrintResult dùng để in ra 1 cách phân tích phải có thêm tham số cho biết sẽ in ra bao nhiêu phần tử. Thủ tục đệ quy Try(i) sẽ thử các giá trị có thể nhận của xi (xi ≥ xi - 1).

Khi nào thì in kết quả và khi nào thì gọi đệ quy tìm tiếp?

Lưu ý rằng ti - 1 là tổng của tất cả các phần tử từ x1 đến xi-1 do đó, khi ti = n tức là (xi = n - ti - 1) thì in kết quả.

Khi tìm tiếp, xi+1 sẽ phải lớn hơn hoặc bằng xi. Mặt khác ti+1 là tổng của các số từ x1 tới xi+1 không được vượt quá n. Vậy ta có ti+1 ≤ n ⇔ ti-1 + xi + xi+1 ≤ n ⇔ xi + xi + 1 ≤ n - ti - 1 tức là xi ≤ (n - ti - 1)/2. Ví dụ đơn giản khi n = 10 thì chọn x1 = 6, 7, 8, 9 là việc làm vô nghĩa vì như vậy cũng không ra nghiệm mà cũng không chọn tiếp x2 được nữa.

Một cách dễ hiểu ta gọi đệ quy tìm tiếp khi giá trị xi được chọn còn cho phép chọn thêm một phần tử khác lớn hơn hoặc bằng nó mà không làm tổng vượt quá n. Còn ta in kết quả chỉ khi xi mang giá trị đúng bằng số thiếu hụt của tổng i-1 phần tử đầu so với n.

Vậy thủ tục Try(i) thử các giá trị cho xi có thể mô tả như sau: (để tổng quát cho i = 1, ta đặt x0 = 1 và t0 = 0).

Xét các giá trị của xi từ xi - 1 đến (n - ti-1) div 2, cập nhật ti := ti - 1 + xi và gọi đệ quy tìm tiếp. Cuối cùng xét giá trị xi = n - ti-1 và in kết quả từ x1 đến xi.

Input: file văn bản ANALYSE.INP chứa số nguyên dương n ≤ 30.

Output: file văn bản ANALYSE.OUT ghi các cách phân tích số n.

ANALYSE.INP	ANALYSE.OUT
6	6 = 1+1+1+1+1+1
6 = 1+1+1+1+2
6 = 1+1+1+3
6 = 1+1+2+2
6 = 1+1+4
6 = 1+2+3
6 = 1+5
6 = 2+2+2
6 = 2+4
6 = 3+3
6 = 6

Thuật toán:

P_1_03_4.PAS * Thuật toán quay lui liệt kê các cách phân tích số

program Analyses;

const

InputFile = 'ANALYSE.INP';

OutputFile = 'ANALYSE.OUT';

max = 30;

var

n: Integer;

x: array[0..max] of Integer;

t: array[0..max] of Integer;

f: Text;

procedure Init; {Khởi tạo}

begin

Assign(f, InputFile); Reset(f);

ReadLn(f, n);

Close(f);

x[0] := 1;

t[0] := 0;

end;

procedure PrintResult(k: Integer);

var

i: Integer; begin

Write(f, n, ' = ');

for i := 1 to k - 1 do Write(f, x[i], '+');

WriteLn(f, x[k]);

end;

procedure Try(i: Integer);

var

j: Integer;

begin

for j := x[i - 1] to (n - T[i - 1]) div 2 do {Trường hợp còn chọn tiếp xi+1}

begin

x[i] := j;

t[i] := t[i - 1] + j; Try(i + 1);

end;

x[i] := n - T[i - 1]; {Nếu xi là phần tử cuối thì nó bắt buộc phải là … và in kết quả}

PrintResult(i);

end;

begin

Init;

Assign(f, OutputFile); Rewrite(f);

Try(1);

Close(f);

end.

Bây giờ ta xét tiếp một ví dụ kinh điển của thuật toán quay lui:

BÀI TOÁN XẾP HẬU

Bài toán

Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột hoặc cùng đường chéo. Hãy tìm các xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào.

Ví dụ một cách xếp với n = 8:

Xếp 8 quân hậu trên bàn cờ 8x8

Phân tích

Rõ ràng n quân hậu sẽ được đặt mỗi con một hàng vì hậu ăn được ngang, ta gọi quân hậu sẽ đặt ở hàng 1 là quân hậu 1, quân hậu ở hàng 2 là quân hậu 2… quân hậu ở hàng n là quân hậu n. Vậy một nghiệm của bài toán sẽ được biết khi ta tìm ra được vị trí cột của những quân hậu.

Nếu ta định hướng Đông (Phải), Tây (Trái), Nam (Dưới), Bắc (Trên) thì ta nhận thấy rằng:

• Một đường chéo theo hướng Đông Bắc - Tây Nam (ĐB-TN) bất kỳ sẽ đi qua một số ô, các ô đó có tính chất: Hàng + Cột = C (Const). Với mỗi đường chéo ĐB-TN ta có 1 hằng số C và với một hằng số C: 2 £ C £ 2n xác định duy nhất 1 đường chéo ĐB-TN vì vậy ta có thể đánh chỉ số cho các đường chéo ĐB- TN từ 2 đến 2n
• Một đường chéo theo hướng Đông Nam - Tây Bắc (ĐN-TB) bất kỳ sẽ đi qua một số ô, các ô đó có tính chất: Hàng - Cột = C (Const). Với mỗi đường chéo ĐN-TB ta có 1 hằng số C và với một hằng số C: 1 - n £ C £ n - 1 xác định duy nhất 1 đường chéo ĐN-TB vì vậy ta có thể đánh chỉ số cho các đường chéo ĐN- TB từ 1 - n đến n - 1.

Đường chéo ĐB-TN mang chỉ số 10 và đường chéo ĐN-TB mang chỉ số 0

Cài đặt:

Ta có 3 mảng logic để đánh dấu:

• Mảng a[1..n]. ai = TRUE nếu như cột i còn tự do, ai = FALSE nếu như cột i đã bị một quân hậu khống chế.
• Mảng b[2..2n]. bi = TRUE nếu như đường chéo ĐB-TN thứ i còn tự do, bi = FALSE nếu như đường chéo đó đã bị một quân hậu khống chế.
• Mảng c[1 - n..n - 1]. ci = TRUE nếu như đường chéo ĐN-TB thứ i còn tự do, ci = FALSE nếu như đường chéo đó đã bị một quân hậu khống chế.

Ban đầu cả 3 mảng đánh dấu đều mang giá trị TRUE. (Các cột và đường chéo đều tự do).

Thuật toán quay lui:

• Xét tất cả các cột, thử đặt quân hậu 1 vào một cột, với mỗi cách đặt như vậy, xét tất cả các cách đặt quân hậu 2 không bị quân hậu 1 ăn, lại thử 1 cách đặt và xét tiếp các cách đặt quân hậu 3…Mỗi cách đặt được đến quân hậu n cho ta 1 nghiệm.
• Khi chọn vị trí cột j cho quân hậu thứ i, thì ta phải chọn ô (i, j) không bị các quân hậu đặt trước đó ăn, tức là phải chọn cột j còn tự do, đường chéo ĐB-TN (i+j) còn tự do, đường chéo ĐN-TB(i-j) còn tự do. Điều này có thể kiểm tra (aj = bi+j = ci-j = TRUE).
• Khi thử đặt được quân hậu thứ i vào cột j, nếu đó là quân hậu cuối cùng (i = n) thì ta có một nghiệm. Nếu không:
  • Trước khi gọi đệ quy tìm cách đặt quân hậu thứ i + 1, ta đánh dấu cột và 2 đường chéo bị quân hậu vừa đặt khống chế (aj = bi+j = ci-j := FALSE) để các lần gọi đệ quy tiếp sau chọn cách đặt các quân hậu kế tiếp sẽ không chọn vào những ô nằm trên cột j và những đường chéo này nữa.
  • Sau khi gọi đệ quy tìm cách đặt quân hậu thứ i + 1, có nghĩa là sắp tới ta lại thử một cách đặt khác cho quân hậu thứ i, ta bỏ đánh dấu cột và 2 đường chéo bị quân hậu vừa thử đặt khống chế (aj = bi+j = ci-j := TRUE) tức là cột và 2 đường chéo đó lại thành tự do, bởi khi đã đặt quân hậu i sang vị trí khác rồi thì cột và 2 đường chéo đó hoàn toàn có thể gán cho một quân hậu khác.

Hãy xem lại trong các chương trình liệt kê chỉnh hợp không lặp và hoán vị về kỹ thuật đánh dấu. Ở đây chỉ khác với liệt kê hoán vị là: liệt kê hoán vị chỉ cần một mảng đánh dấu xem giá trị có tự do không, còn bài toán xếp hậu thì cần phải đánh dấu cả 3 thành phần: Cột, đường chéo ĐB-TN, đường chéo ĐN- TB. Trường hợp đơn giản hơn: Yêu cầu liệt kê các cách đặt n quân xe lên bàn cờ nxn sao cho không quân nào ăn quân nào chính là bài toán liệt kê hoán vị

• Input: file văn bản QUEENS.INP chứa số nguyên dương n ≤ 12.
• Output: file văn bản QUEENS.OUT, mỗi dòng ghi một cách đặt n quân hậu.

QUEENS.INP	QUEENS.OUT
5	(1,	1);	(2,	3);	(3,	5);	(4,	2);	(5,	4);
(1,	1);	(2,	4);	(3,	2);	(4,	5);	(5,	3);
(1,	2);	(2,	4);	(3,	1);	(4,	3);	(5,	5);
(1,	2);	(2,	5);	(3,	3);	(4,	1);	(5,	4);
(1,	3);	(2,	1);	(3,	4);	(4,	2);	(5,	5);
(1,	3);	(2,	5);	(3,	2);	(4,	4);	(5,	1);
(1,	4);	(2,	1);	(3,	3);	(4,	5);	(5,	2);
(1,	4);	(2,	2);	(3,	5);	(4,	3);	(5,	1);
(1,	5);	(2,	2);	(3,	4);	(4,	1);	(5,	3);
(1,	5);	(2,	3);	(3,	1);	(4,	4);	(5,	2);

Thuật toán:

P_1_03_5.PAS * Thuật toán quay lui giải bài toán xếp hậu

program n_Queens;

const

InputFile = 'QUEENS.INP';

OutputFile = 'QUEENS.OUT';

max = 12;

var

n: Integer;

x: array[1..max] of Integer;

a: array[1..max] of Boolean;

b: array[2..2 * max] of Boolean;

c: array[1 - max..max - 1] of Boolean;

f: Text;

procedure Init; begin

Assign(f, InputFile); Reset(f);

ReadLn(f, n);

Close(f);

FillChar(a, SizeOf(a), True); {Mọi cột đều tự do}

FillChar(b, SizeOf(b), True); {Mọi đường chéo Đông Bắc - Tây Nam đều tự do}

FillChar(c, SizeOf(c), True); {Mọi đường chéo Đông Nam - Tây Bắc đều tự do}

end;

procedure PrintResult;

var

i: Integer; begin

for i := 1 to n do Write(f, '(', i, ', ', x[i], '); ');

WriteLn(f);

end;

procedure Try(i: Integer); {Thử các cách đặt quân hậu thứ i vào hàng i}

var

j: Integer; begin

for j := 1 to n do

if a[j] and b[i + j] and c[i - j] then {Chỉ xét những cột j mà ô (i, j) chưa bị khống chế}

begin

x[i] := j; {Thử đặt quân hậu i vào cột j}

if i = n then PrintResult else

begin

a[j] := False; b[i + j] := False; c[i - j] := False; {Đánh dấu}

Try(i + 1); {Tìm các cách đặt quân hậu thứ i + 1}

a[j] := True; b[i + j] := True; c[i - j] := True; {Bỏ đánh dấu}

end;

end;

end;

begin

Init;

Assign(f, OutputFile); Rewrite(f);

Try(1);

Close(f);

end.

Tên gọi thuật toán quay lui, đứng trên phương diện cài đặt có thể nên gọi là kỹ thuật vét cạn bằng quay lui thì chính xác hơn, tuy nhiên đứng trên phương diện bài toán, nếu như ta coi công việc giải bài toán bằng cách xét tất cả các khả năng cũng là 1 cách giải thì tên gọi Thuật toán quay lui cũng không có gì trái logic. Xét hoạt động của chương trình trên cây tìm kiếm quay lui ta thấy tại bước thử chọn xi nó sẽ gọi đệ quy để tìm tiếp xi+1 có nghĩa là quá trình sẽ duyệt tiến sâu xuống phía dưới đến tận nút lá, sau khi đã duyệt hết các nhánh, tiến trình lùi lại thử áp đặt một giá trị khác cho xi, đó chính là nguồn gốc của tên gọi "thuật toán quay lui".

Bài tập:

Bài 1

Một số chương trình trên xử lý không tốt trong trường hợp tầm thường (n = 0 hoặc k = 0), hãy khắc phục các lỗi đó.

Bài 2

Viết chương trình liệt kê các chỉnh hợp lặp chập k của n phần tử.

Bài 3

Cho hai số nguyên dương l, n. Hãy liệt kê các xâu nhị phân độ dài n có tính chất, bất kỳ hai xâu con nào độ dài l liền nhau đều khác nhau.

Bài 4

Với n = 5, k = 3, vẽ cây tìm kiếm quay lui của chương trình liệt kê tổ hợp chập k của tập {1, 2, …, n}.

Bài 5

Liệt kê tất cả các tập con của tập S gồm n số nguyên {S1, S2, …, Sn} nhập vào từ bàn phím.

Bài 6

Tương tự như bài 5 nhưng chỉ liệt kê các tập con có max - min ≤ T (T cho trước).

Bài 7

Một dãy (x1, x2, …, xn) gọi là một hoán vị hoàn toàn của tập {1, 2,…, n} nếu nó là một hoán vị và thoả mãn xi khác i với mọi i: 1 ≤ i ≤ n. Hãy viết chương trình liệt kê tất cả các hoán vị hoàn toàn của tập trên (n vào từ bàn phím).

Bài 8

Sửa lại thủ tục in kết quả (PrintResult) trong bài xếp hậu để có thể vẽ hình bàn cờ và các cách đặt hậu ra màn hình.

Bài 9

Mã đi tuần: Cho bàn cờ tổng quát kích thước nxn và một quân Mã, hãy chỉ ra một hành trình của quân Mã xuất phát từ ô đang đứng đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đúng 1 lần.

Bài 10

Chuyển tất cả các bài tập trong bài trước đang viết bằng sinh tuần tự sang quay lui.

Bài 11

Xét sơ đồ giao thông gồm n nút giao thông đánh số từ 1 tới n và m đoạn đường nối chúng, mỗi đoạn đường nối 2 nút giao thông. Hãy nhập dữ liệu về mạng lưới giao thông đó, nhập số hiệu hai nút giao thông s và d. Hãy in ra tất cả các cách đi từ s tới d mà mỗi cách đi không được qua nút giao thông nào quá một lần.

Nguồn: Giáo trình Giải thuật và Lập trình - Lê Minh Hoàng - Đại học sư phạm Hà Nội » Tiếp: §4. Kỹ thuật nhánh cận « Trước: §2. Phương pháp sinh (GENERATION) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×