Có tài liệu còn gọi nó là ” Thử và sai”. đã là đệ quy quay lui thì trong thủ tục của nó là thủ tục đệ quy và có “quay lui”. Ta tìm hiểu quay lui ở đâu và như thế nào?
Trước hết ta xét ví dụ:
Một từ được gọi là chân chính loại M, N nếu nó được xây dựng từ tập hợp gồm M ký tự, có độ dài N và không có 2 từ con nào liên tiếp giống nhau.
Giả sử tập M={‘1’, ‘2’, ‘3’}
Ví dụ: 1232; 2123; 1231 là những từ chân chính loại 3,4; còn 1123;1212;1233 là những từ không phải là từ chân chính loại 3,4.
Tất nhiên ở đây không phải là ta xây dựng tất cả các từ có độ dài N, sau đó loại trừ những từ không thoả mãn, mà ta lần lượt xây dựng các xâu.
Khởi tạo ban đầu là xâu rỗng, ta tiến hành ghép các ký tự , tại mỗi bước ghép ta kiểm tra xem nó có thoả mãn điều kiện bài toán không[ có hai từ con liền nhau giống nhau không]. Nếu thoả mãn ta kiểm tra xem xâu có độ dài bằng N hay chưa. Nếu xâu đã có độ dài bằng N ta in kết quả, nếu chưa có độ dài bằng N ta ghép bước tiếp. Nếu tất cả các ký tự được chọn để ghép đều không thoả mãn điều kiện bài toán thì việc chọn ký tự trước đó sai, ta phải xoá ký tự trước đó đi và thay bởi ký tự khác để bước ghép tiếp được thành công. Việc xoá ký tự trước đó để tìm ký tự khác ghép vào người ta gọi là quay lui. Trong trường hợp xâu có độ dài bằng N[ đã thoả mãn bài toán] thì ta được một kết quả. Để tìm kết quả khác, ta xoá ký tự cuối cùng này đi rồi tìm ký tự khác để ghép vào cũng gọi là quay lui.
Việc đó thể hiên ở thủ tục procedure find[ x : integer];
Còn hàm function ok[i : integer]:boolean; là để kiểm tra xem có hai từ con liền nhau giống nhau hay không
function ok[i : integer]:boolean;
var k : integer;
begin
ok := true;
for k := 2 to i div 2 do
if copy[s,i-2*k+1,k] = copy[s,i-k+1,k] then
begin
ok := false;
exit;
end;
end;
procedure find[ x : integer];
var i : integer;
begin
if x > n then
xuat
else
for i := 1 to m do
if s[length[s]] st[i] then
begin
s := s + st[i];
if ok[s] then
begin
find[x+1];
delete[s,length[s],1];{ xoá để quay lại bước trước}
end
else
delete[s,length[s],1]; { xoá để quay lại bước trước}
end;
end;
Ta xét ví dụ 2: Đường đi trên lưới ô vuông
Cho lưới ô vuông cấp NxM. Trên mỗi ô [i,j] của lưới ghi một số nguyên a[i,j]. Ô [x,y] đi được sang ô [x’,y’] nếu 2 ô này chung cạnh và a[x,y]