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áckhả năng có thể của ai. Với mỗi khả năngj kiểm tra xem nó có chấp nhận được không.
Xảy ra hai trường hợp.
Nếu j chấo 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 < nta 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ấtphù 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 < ghi nhận cấu hình >
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

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 thú,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;
Begin
For j:=1 to n do
If (b[j]) and (c[i + j]) and (d[i- j]) then
Begin
a [i] : = j;
b [j] : = false; c[i + j]: = false;
d [i] : = false;