2 bài toán kinh điển về Kĩ Thuật Quay Lui (Backtracking)

Có thể bạn thích

Kĩ thuật quay lui (hay kĩ thuật Backtracking, thuật toán quay lui, thuật toán Backtracking) là một kĩ thuật cực kì phổ biến để giải những bài toán liệt kê các cấu hình. Bản chất của kĩ thuật này là thử qua tất cả các khả năng mà phần tử trong cấu hình có thể nhận được.

Để tiếp cận kiến thức từ bài viết một cách tốt nhất, bạn nên hiểu qua những khái niệm cơ bản về kĩ thuật này. Bạn có thể tham khảo tại đây!

 Giờ sẽ là bài toán đầu tiên, sẽ là bài toán cực kì kinh điển của kĩ thuật này:

Bài toán 1 - Bài toán xếp hậu 

Bài toán

Xét bàn cờ tổng quát 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ách 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.

Phân tích

Nhận thấy, với mỗi quân hậu, ta có thể ăn các quân khác trên cùng hàng và cùng cột. Do đó, hiển nhiên N quân hậu sẽ nằm ở mỗi hàng mỗi cột riêng, không có quân nào nằm cùng hàng, cùng cột với quân nào.

Ta sẽ mặc định cho các quân hậu này nằm ở những hàng khác nhau (quân 1 nằm ở hàng 1, quân 2 nằm ở hàng 2,... quân N nằm ở hàng N), không quân nào nằm cùng hàng với quân nào. Do đó nghiệm của bài toán sẽ là vị trí cột của những quân hậu.
Giờ ta chỉ cần xét những đường chéo để các quân hậu này phải chắc chắn không nằm trên đường chéo mà quân hậu khác "thống trị". Ta sẽ định nghĩa hướng Bắc (trên), Nam (dưới), Đông (phải), Tây (trái).

• Xét đường chéo Đông Bắc - Tây Nam: Nếu nhìn kĩ trên đường chéo này, bạn sẽ thấy vị trí của các ô trên đường chéo sẽ rất đặc biệt, mình tạm thời gọi vị trí của các ô là (a,b) (a là hàng, b là cột). Nhận thấy, giá trị a+b của các ô luôn luôn bằng nhau, nghĩa là bằng một hằng số C không đổi. Nguyên nhân là do trong quá trình di chuyển từ TN lên ĐB, số hàng sẽ giảm đi 1, số cột sẽ tặng thêm 1 một cách đều đặn, do đó a+b=C luôn làm một hằng số.
• Xét đường chéo Tây Bắc - Đông Nam: Tương tự như cách suy nghĩ ở trên. Ta thấy a-b=C luôn là một hằng số không đổi. Do trong quá trình di chuyển từ ĐN lên TB, số hàng và số cột đồng loạt giảm đi 1. 

Từ đó ta rút ra được gì? Giả sử ta có hằng số C bên trên.

1. Nếu xét theo hướng ĐB - TN thì giới hạn của hằng số C sẽ nằm trong khoảng  [2..2N].
2. Nếu xét theo hướng TB - ĐN thì giới hạn của hằng số C sẽ nằm trong khoảng [1-N..N-1].

Vậy thì C có ý nghĩa gì trong bài toán này? Nói cho công bằng thì vai trò của hằng số C này cực kì có ý nghĩa trong quá trình giải bài toán này, vì nó sẽ giúp ta đánh dấu những đường chéo "đã bị thống trị" bởi một quân hậu, do đó sẽ rất tiện lợi trong việc xét các quận hậu tiếp theo để nó không rơi vào ô "hủy diệt" của quân hậu khác.

Trong trường hợp này, C = 9 (ĐB - TN), C = 1 (TB - ĐN)

Cơ sở dữ liệu

Ta cần 3 mảng logic để đánh dấu các giá trị sau:

• Mảng đánh dấu cột A[1..N]: mảng này nhằm đánh dấu xem cột Ai có tự do hay không, nếu tự do thì A[i] = TRUE, A[i] = FALSE nếu như đã bị một quân hậu khác khống chế.
• Mảng đánh dấu đường chéo theo hướng ĐB - TN B[2..2N]: mảng này nhằm đánh dấu xem đường chéo ĐB - TN có tự do hay không, nếu có thì B[i] = TRUE, B[i] = FALSE nếu như đã bị một quân hậu khác khống chế.
• Mảng đánh dấu đường chéo theo hướng TB - ĐN C[1-N..N-1]: mảng này nhằm đánh dấu xem đường chéo TB - ĐN có tự hay hay không, nếu có thì C[i] = TRUE, C[i] = FALSE nếu như đã bị một quân hậu khác khống chế.

Ban đầu, tất cả các giá trị của ba mảng đều là TRUE, vì lúc khởi tạo cả ba đều tự do.

Code tham khảo

program XEPHAU;
uses crt;
var n: integer;
    x: array[1..8] of integer;
    a: array[1..8] of boolean;
    b: array[2..2*8] of boolean;
    c: array[-7..9] of boolean;
procedure DrawQueen;           
var i: integer;
begin
    for i := 2 to n+1 do begin
        GotoXY(X[i-1]*3,(i-1)*3+1);
        Write('Q');
    end;
    readln;
    for i := 2 to n+1 do begin
        GotoXY(X[i-1]*3,(i-1)*3+1);
        Write(' ');
    end;
end;
procedure DrawTable(n: integer);
var i,j: integer;
begin
    for i := 2 to n+1 do begin gotoxy((i-1)*3,2); write(i-1); end;
    writeln;
    for i := 1 to n do begin
        for j := 1 to n do if j = 1 then Write(' ---') else Write('---');
        Writeln;
        Write(i);
        for j := 1 to n do write('| |');
        Writeln;
        for j := 1 to n do if j = 1 then Write(' ---') else Write('---');
        Writeln;
    end;
end;

procedure Try(i: integer);
var j: integer;
begin
    for j := 1 to n do begin
        if a[j] and b[i+j] and c[i-j] then begin
            X[i] := j;
            if i = n then begin DrawQueen; end
            else begin
                a[j] := false; b[i+j] := false; c[i-j] := false;
                Try(i+1);
                a[j] := true; b[i+j] := true; c[i-j] := true;
            end;
            end;
    end;
end;

BEGIN
     clrscr;
     fillchar(a,sizeof(a),true);
     fillchar(b,sizeof(b),true);
     fillchar(c,sizeof(c),true);
     Write('N = ');readln(N);
     DrawTable(N);
     Try(1);
END.

Bài toán 2 - Mã đi tuần

Bài toá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ờ sao cho mỗi ô chỉ đi qua đúng một lần.

Phân tích

Ta đã biết quân Mã đi theo hình chữ L, nếu được đặt ở một vị trí thích hợp thì quân Mã này có thể có nhiều nhất là 8 đường để đi. Giả sử tọa độ của quân Mã là (x,y) thì 8 đường đi mà nó có thể đi là: (x-2,y+1), (x-1,y+2), (x+1,y+2), (x+2,y+1), (x+2,y-1), (x+1,y-2), (x-1,y-2), (x-2,y-1).

Nếu áp dụng những cách tính tọa độ trên cho tất cả các vị trí của quân Mã trên bàn cờ thì sẽ có trường hợp quân Mã sẽ bị "lọt" ra ngoài bàn cờ, do đó cần xét thêm trường hợp 1 <= x, y <= N.

Cơ sở dữ liệu

Ta cần 3 mảng số nguyên:

• Hx[1..8] = (-2,-1,1,2,2,1,-1,-2). Mảng này dùng để lưu các tọa độ x theo hàng của quân Mã.
• Hy[1..8] = (1,2,2,1,-1,-2,-2,-1). Mảng này dùng để lưu các tọa độ y theo cột của quân Mã.
• d[1..N,1..N]. Đây là mảng dùng để đánh dấu thứ tự của quân Mã.

Set giá trị d[x,y] = 1 vì vị trí này là vị trí đầu tiên của quân Mã. Tất cả các giá trị còn lại là 0, do ban đầu nó chưa đi qua ô nào cả.

Code tham khảo

program MaDiTuan;
uses crt;
const maxN = 20;
var N: integer;
    x,y: integer; 
    d: array[1..maxN,1..maxN] of integer;
    S: set of 1..maxN;
    Hx: Array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
    Hy: Array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);
procedure Init;
var i: integer;
begin
    Write('N = ');readln(N);
    fillchar(d,sizeof(d),0);
    S := [];
    for i := 1 to N do S := S+[i];
    repeat
        Writeln('Nhap toa do cua bat dau cua Ngua: ');
        Write('x = ');readln(x);
        Write('y = ');readln(y);
        if Not (x in S) or Not (y in S) then Writeln('Vui long nhap lai toa do hop le!');
    until (x in S) and (y in S);
    d[x,y] := 1;
end;
procedure Print;
var i,j: integer;
begin
    for i := 1 to N do begin
        for j := 1 to N do Write(d[i,j],' ');
        Writeln;
    end;
end;
procedure Try(i: integer);
var j,u,v: integer;
begin
    if i > N*N then Print else begin
    for j := 1 to 8 do begin
        u := x+Hx[j]; v := y+Hy[j];
        Write(u,' ',v);readln;
        if (u in S) and (v in S) then begin
            if d[u,v]=0 then begin
              d[u,v] := i; x := u; y := v;
                Try(i+1);
              d[u,v] := 0; x := u-Hx[j]; y := v-Hy[j];
            end;
        end;
    end;
    end;
end;
BEGIN
    clrscr;
    Init;
    Try(2);
    readln;
END.

Lưu ý khi sử dụng code

• Ý tưởng giải các bài toán trên không do chính tác giả suy nghĩ ra, do đó các bạn có thể sử dụng thoải mái code này trên trang web hay blog của bạn mà không cần để trích dẫn, không sao cả.
• Code chưa được chú thích, sẽ được chú thích trong thời gian sớm nhất.

Nguồn tham khảo

• Nguồn tham khảo và ý tưởng từ quyển sách: Giải Thuật Và Lập Trình của tác giả Lê Minh Hoàng
• Ngoài ra, tác giả còn tổng hợp ý tưởng từ quyển sách: Lý Thuyết Và Bài Tập Ngôn Ngữ Lập Trình Pascal của tác giả Hồ Xuyên - Hoàng Tư Anh Tuấn