Thuật toán quay lui và ứng dụng
Lã Văn Chinh
Giả thiết một cấu hình cần tìm được mô tả bởi một bộ phận gồm n thành phần a1, a2,... an. Giả sử
tìm được i - 1 thành phần a1, a2, ai-1, ta tìm thành phần thứ i bằng cách duyệt tất cả các khả năng
có thể của ai. Với mỗi khả năng j kiểm tra xem nó có chấp nhận được không. Xảy rahai trường hợp.
nhận được thì xác định ai theo j và kiểm tra xem i = n chưa, nếu i = n thì ta ghi nhận một cấu hình,
còn nếu i < ta gọi tiến hành xác định ai+1.
Nếu thử tất cả các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước xác
định lại ai-1
Nội dung của thuật toán này rất phù hợp với việc gọi đệ quy. Ta có thủ tục đệ quy sau đây:
Procedure Try (i:tinteger);
Var j:integer;
Begin
For j:=1 to n do
if chấp nhận j then
begin
xác nhận aj theo j
if i=n then
else try(i+1);
end;
end;
Để minh hoạ cho thuật toán này ta áp dụng giải bài toán xếp hậu:
Nội dung bài toán: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao cho chúng
không ăn được nhau.
Giải: Ta xếp n con hậu trên n dòng, heo nguyên lý nhân ta có
n
n cách sắp xếp thoả mãn điều kiện
đầu bải. Để làm điều đó ta dùng thủ tục đệ quy mô tả ở trên để giải. Ta đánh ghi số cột và dòng của
bàn cờ từ 1 đến n, mỗi cách sắp xếp ứng với 1 bộ gồm a
1
,a

Var
i:integer;
Begin
Write('Cho do rong ban co n= ');
Readln(n);
Count:=0;
d:=0;
For i:=1 to n do b[i]:=true;
For i:=2 to 2*n do c[i]:=true;
For i:=1-n to n-1 do d[i]:=true;
End;
Procedure Result;
Var
i:integer;
Begin
d:=d+1;
count:=count+1;
Write('Cach xep thu',count:5,'.');
for i:=1 to n do write(a[i]:2);
Writeln;
if d = 24 then
begin
readln;
d :
= 0;
end;
end;
Procedure try(i:integer);
Var
j : integer;