Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Tư tưởng

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 từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1...n]:

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước:
• ...
• ....
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking(k) {
  for([Mỗi phương án chọn i(thuộc tập D)]) {
    if ([Chấp nhận i]) {
      [Chọn i cho X[k]];
      if ([Thành công]) {
        [Đưa ra kết quả];
      } else {
        Backtracking(k+1);
        [Bỏ chọn i cho X[k]];
      }
    }
  }
}

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9×9×9)

void solveSudoku(int S[][9], int x, int y){
    if(y == 9){
        if(x == 8){
            printSolution(S);
            exit(0);
        } else {
            solveSudoku(S, x+1,0);
        }
    } else if(S[x][y] == 0){
        for (int k = 1; k <=9; k++){
            if(checkValid(S,x,y,k)){
                S[x][y] = k;
                solveSudoku(S, x, y+1);
                S[x][y] = 0;
            }
        }
    } else {
        solveSudoku(S,x,y+1);
    }
}
boolean checkValid(int S[][9], int x, int y, int k){
    for(int i = 0; i <9 ; i++){
        if(S[x][i] == k) return false;
    }
    for(int i = 0; i <9 ; i++){
        if(S[i][y] == k) return false;
    }
    int a = x/3, b = y/3;
    for(int i = 3*a; i < 3*a+3; i++){
        for(int j = 3*b; j < 3*b+3; j++){
            if(S[i][j] == k) return false;
        }
    }
    return true;
}

Nhận xét

• -Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.

Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:

Quay lui (tiếng Anh: backtracking) là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Các bài toán thỏa mãn ràng buộc là các bài toán có một lời giải đầy đủ, trong đó thứ tự của các phần tử không quan trọng. Các bài toán này bao gồm một tập các biến mà mỗi biến cần được gán một giá trị tùy theo các ràng buộc cụ thể của bài toán. Việc quay lui là để thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều tổ hợp chưa hoàn chỉnh, và nhờ đó giảm thời gian chạy.

Nội dung chính của phương pháp này là việc xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả thiết cấu hình cần được tìm được mô tả bằng một bộ giá trị (x 1 ,x 2 ,..,x N ).Giả sử đã xác định được i - 1 thành phần (x 1 ,x 2 ,...,x i-1 ),bây giờ ta xác định thành phần x i bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số từ 1 đến ni ). Với mỗi khả năng j, kiểm tra xem j có được chấp nhận hay không. Có thể có hai trường hợp có thể xảy ra:

- Nếu j được chấp nhận thì xác định x i theo j, sau đó nếu j = N thì ta được một cấu hình, trái lại ta tiếp tục tiến hành việc xác định x i+1.

- Nếu thử tất cả các khả năng mà mà không có khả năng nào được chấp nhận thì ta sẽ lùi lại bước trước để xác định x i-1.

Thông thường ta phân tích quá trình tìm kiếm thành cây tìm kiếm. Không gian tìm kiếm càng lớn hay càng nhiều khả năng tìm kiếm thì cây tìm kiếm càng lớn, càng nhiều nhánh. Vì vậy, hạn chế và bỏ bớt các nhánh vô nghiệm của cây tìm kiếm thì sẽ tiết kiệm được thời gian và bộ nhớ, tránh bị tràn dữ liệu. Quá trình tìm kiếm lời giải theo thuật toán quay lui có thể được mô tả bởi mô hình cây tìm dưới đây:

Cần phải lưu ý là ta phải ghi nhớ tại mỗi bước đã đi qua, những khả năng nào đã thử để tránh trùng lặp. Những thông tin này được lưu trữ theo kiểu dữ liệu ngăn xếp - Stack ( vào sau ra trước) - vì thế nên thuật toán này phù hợp thể hiện bởi thủ tục đệ quy. Ta có thể mô tả bước xác định x i bởi thủ tục đệ quy sau:

Procedure Try (i: integer);

Var j : integer;

Begin

For j:= 1 to ni do

If then

Begin i theo j >

if i = N then

else try(i+1);

End; End;

Trong thủ tục mô tả trên, điều quan trọng nhất là đưa ra được một danh sách các khả năng đề cử và xác định được giá trị của biểu thức logic . Ngoài việc phụ thuộc j, giá trị này còn phụ thuộc vào việc đã chọn các khả năng tại i – 1 bước trước đó. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trìnhsau khi i theo j> và trả lại trạng thái cũ sau lời gọi Try(i+1). Các trạng thái này được ghi nhận nhờ một số biến tổng thể (global), gọi là các biến trạng thái.

Dễ thấy rằng bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng mà không có khả năng nào thoả mãn yêu cầu. Ta nói rằng là đã vét cạn mọi trường hợp. Chú ý rằng là đến một lúc nào đó ta phải lùi liên tiếp nhiều lần.Từ đó suy ra rằng, thông thường bài toán vô nghiệm khi không thể lùi được nữa. Thuật toán này sẽ không có tính khả thi cao bởi dùng thủ tục đệ quy dễ bị lỗi tràn Stack.

II. BÀI TẬP

1. Bài 1: Xếp hậu

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.

Hướng dẫn: Ta xếp n con hậu trên n dòng, Theo nguyên lý nhân ta có nn 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 a1,a2,.....,an với ai = j (j=1,2,...,n) có nghĩa là con hậu thứ i đặt vào cột j. Giả sử ta chọn được i-1 con hậu bằng cách duyệt tất cả các khả năng của nó.

Quan trọng nhất là ta tìm điều kiện chấp nhận j, một con hậu đứng ở một ô trong bàn cờ nó có nhiều nhất bốn hướng đi (đường dọc, đường ngang và hai đường chéo).

Vậy điều kiện chấp nhận thứ i thoả mãn không nằm trên đường đi của tất cả i-1 con hậu đã xếp. Bởi vì n con hậu xếp ở hàng nên đường đi ngang của chúng là không chiếu nhau, do đó khi chọn con hậu thứ i chỉ cần kiểm tra xem trên 2 đường chéo và đường dọc của chúng có chiếu vào những con hậu đã xếp không? Để kiểm tra điều này mỗi đường ta dùng một biến trạng thái.

* Đường dọc kiểm soát bằng biến b[j],(j=1,2,...,n).

* Một đường chéo kiểm soát bằng biến c[i+j],i+j={2,....,2n}.

* Còn đường chéo kia kiểm soát bằng biến d[i-j],i-j={1-n,....,n-1}.

Các biến trạng thái này khởi gán giá trị True trong thủ tục Init. Như vậy con hậu thứ i được chấp nhận xếp vào cột j nếu nó thoả mãn cả ba biến b[j],c[i+j],d[i-j] đều có giá trị True. Các biến này gán giá trị False khi xếp xong con hậu thứ i, và trả lại giá trị true sau khi gọi Result hay Try(i+1). Ta có chương trình Pascal sau :

Program XepHau;

Uses crt;

var

  n : integer;

  a:array[1..30] of integer;

  b:array[1..30] of boolean;

  c:array[2..60]of boolean;

  count,d:word;

Procedure Init;

Var

Uses crt;

0

Uses crt;

1

Uses crt;

2

Uses crt;

3

Uses crt;

4

Uses crt;

5

Uses crt;

6

Uses crt;

7

Uses crt;

8

Uses crt;

9

var

0

Var

Uses crt;

0

Uses crt;

1

var

4

var

5

var

6

var

7

var

8

var

9

  n : integer;

0

  n : integer;

1

  n : integer;

2

  n : integer;

3

  n : integer;

4

  n : integer;

5

  n : integer;

6

Var

  n : integer;

8

Uses crt;

1

  a:array[1..30] of integer;

0

  a:array[1..30] of integer;

1

  a:array[1..30] of integer;

2

  a:array[1..30] of integer;

3

  a:array[1..30] of integer;

4

  a:array[1..30] of integer;

5

  a:array[1..30] of integer;

6

  a:array[1..30] of integer;

7

  a:array[1..30] of integer;

8

  a:array[1..30] of integer;

9

  b:array[1..30] of boolean;

0

  b:array[1..30] of boolean;

1

  b:array[1..30] of boolean;

2

  n : integer;

5

  b:array[1..30] of boolean;

4

  b:array[1..30] of boolean;

5

  b:array[1..30] of boolean;

6

  b:array[1..30] of boolean;

7

  b:array[1..30] of boolean;

8

  b:array[1..30] of boolean;

9

  c:array[2..60]of boolean;

0

2. Bài 2 Hành trình ký tự

Cho tệp văn bản HT_KITU.INP chứa các dòng ký tự chiều dài không quá 32. Hãy lập trình thực hiện các công việc sau: Lần lượt đọc các dòng vào một xâu, sau đó từ xâu xây dựng lưới ô vuông dạng tam giác như sau: ví dụ xâu =’Vinh’, lưới ô vuông có dạng như hình 1. Xuất phát từ ô góc trên trái (chữ V), đi theo các hướng có thể để xây dựng lại xâu đã cho. Với mỗi hành trình thành công hãy in ra số thứ tự của hành trình và chỉ ra hành trình trên lưới, mỗi ký tự của hành trình thay bằng một dấu ’*’.

Ví dụ:

Sau mỗi lời giải phải ấn ENTER để in lời giải tiếp.

Hướng dẫn giải

Tổ chức hai mảng hai chiều F, Kt[1..32,1..32] of Char. Mảng Kt dùng để tạo ra ma trận kí tự dạng tam giác như trên gồm các kí tự từ xâu S đọc từ file dữ liệu. Mảng F dùng để ghi nhận các hành trình thành công, nếu ô (i,j) thuộc hành trình thì F[i,j] = ’*’.

Sau khi xây dựng xong ma trận kí tự, ta dùng thủ tục đệ quy Try(i,j,h: byte) để tìm tất cả các hành trình. Giả sử ta đang ở ô (i,j) nào đó trên hành trình và đã được một xâu kí tự độ dài h ≤ length(S ). Nếu h = length(S )thì ta đã được một hành trình và ta sẽ ghi nhận nó, in ra màn hình hành trình đó. Còn nếu h < length(S ) thì từ ô (i,j) ta sẽ có thể đi theo hai hướng đó là đến ô (i,j+1) hoặclà ô (i+1,j). Từ mỗi ô đó ta lại tiếp tục đến các ô khác để tìm hành trình. Quá trình đó được tiếp tục thực hiện các ô đó cho đến khi duyệt được hết nghiệm của bài toán.

Ban đầu ta xuất phát tại ô (1,1) và độ dài của xâu ta đang có là 1 nên ở chương trình chính ta gọi thủ tục Try(1,1,1). Để ý rằng nếu độ dài xâu S là L thì ta sẽ có tất cả 2L-1 hành trình.

Văn bản chương trình

Program Hanh_trinh_ki_tu; Uses Crt; Const D : Array[1..2] of shortint= (0,1); C : Array[1..2] of shortint= (1,0); Fi = ’HT_KITU.INP’; Var Kt,F : Array[1..32,1..32] of Char; S : string; t : word; dem : longint;

Procedure Init; Var k,i,j : byte; G : Text; Begin Assign(G,Fi); Reset(G); Read(G,S); t:= length(S); Fillchar(F,sizeof(F),’ ’); F[1,1]:=’*’; k:= 0; For i:= 1 to t do begin For j:=1 to t do begin Kt[i,j]:= S[j+k]; If Kt[i,j] =

0 then Kt[i,j]:= ’ ’;

end; inc(k); end; Close(G); End;

Procedure Write_Out; Var i,j : Byte; Begin Inc(dem); TextColor(Red); Writeln(’Hanh trinh thu:’,dem); For i:=1 to t do begin For j:=1 to t do If F[i,j]=’*’ then begin TextColor(White); Write(’* ’) end Else begin TextColor(Green);Write(Kt[i,j],’ ’); end; Writeln; end; Readln; End;

Procedure Try(i,j,h: byte); Var k,x,y: byte; Begin If h = t then Write_Out else begin For k:=1 to 2 do begin x:= i + D[k]; y:= j + C[k]; F[x,y]:=’*’; Try(x,y,h+1); F[x,y]:=’ ’; end; end; End;

BEGIN Clrscr; Init; Try(1,1,1); END.

3. Bài 3: Biểu thức zero

Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và - sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể. Dữ liệu vào: Lấy từ file văn bản ZERO.INP với một dòng ghi số N. Dữ liệu ra: Ghi vào file văn bản có tên ZERO.OUT có cấu trúc như sau:

- Dòng đầu ghi số lượng kết quả tìm được.

- Các dòng sau mỗi dòng ghi một kết quả tìm được.

Ví dụ

Hướng dẫn giải

Áp dụng thuật toán đệ quy quay lui để giải quyết bài toán này, ta sẽ dùng thủ tục đệ quy Try(i). Giả sử ta đã điền các dấu’+’ và ’-’ vào các số từ 1 đến i, bây giờ cần điền các dấu giữa i và i + 1. Ta có thể chọn một trong ba khả năng: hoặc là điền dấu ’+’, hoặc là điền dấu ’-’, hoặc là không điền dấu nào cả. Khi đã chọn một trong ba khả năng trên, ta tiếp tục lựa chọn dấu để điền vào giữa i + 1 và i + 2 bằng cách gọi đệ quy Try(i+1). Ta sẽ lần lượt duyệt tất cả các khả năng đó để tìm tất cả các nghiệm của bài toán, như vậy bài toán sẽ không bị thiếu nghiệm.

Nếu i = N ta sẽ kiểm tra xem cách điền đó có thoả mãn kết quả bằng 0 hay không. Để kiểm tra ta dùng thủ tục Test trong chương trình. Nếu tổng đúng bằng 0 thì cách điền đó là một nghiệm của bài toán, ta ghi nhận nó. Nếu i < N thì tiếp tục gọi Try(i+1). Trong chương trình ta dùng biến dem để đếm các cách điền thoả mãn, còn mảng M kiểu string sẽ ghi nhận mọi cách điền dấu thoả mãn yêu cầu bài toán.

Văn bản chương trình

Program Zero_sum; Type MangStr = array[1..15] of string; Const Fi =’ZERO.INP’; Fo =’ZERO.OUT’; Dau : array[1..3] of string[1] = (’-’,’+’,’’); S : array[1..9] of char =(’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’); ChuSo = [’1’..’9’];

Var N,k,dem: byte; D : array[2..9] of string[1]; F : Text; St : String; M : MangStr;

Procedure Write_out; Var i : byte; Begin Assign(F,Fo); Rewrite(F); Writeln(F,dem); For i:= 1 to dem do writeln(F,M[i],’ = 0’); Close(F); Halt; End;

Procedure Read_inp; Begin Assign(F,Fi); Reset(F); Read(F,N); Close(F); If N < 3 then write_out; End;

Function DocSo(S : String): longint; Var M : longint; t : byte; Begin M:= 0; t:= 0; If S[k] in [’+’,’-’] then begin t:= k; Inc(k); end; While (k<= length(S)) and (s[k] in ChuSo) do begin m:= m*10 + ord(s[k]) - ord(’0’); Inc(k); end; If (t <> 0) and (S[t] = ’-’) then DocSo:= -M else DocSo:= M; End;

Procedure Test; Var St : string; i : byte; T : longint; Begin St:= ’1’; k:= 1; T:= 0; For i:= 2 to N do St:= St + D[i] + S[i]; While k < length(St) + 1 do T:= T + DocSo(St); If T = 0 then begin Inc(dem); M[dem]:= St; end; End;

Procedure Try(i: byte); Var j : byte; Begin For j:= 1 to 3 do begin D[i]:= Dau[j]; If i = N then Test else try(i+1); end; End;

BEGIN Read_inp; Try(2); Write_out; END.

4. Bài 4: Xổ số điện toán

Có N người (đánh số từ 1 đến N) tham gia một đợt xổ số điện toán. Mỗi người nhận được một thẻ gồm M ô (đánh số từ 1 đến M). Người chơi được chọn K ô trong số các ô đã cho bằng cách đánh dấu các ô được chọn. Sau đó các thẻ này được đưa vào máy tính để xử lý.

Máy tính chọn ra K ô ngẫu nhiên (gọi là các ô kết quả) và chấm điểm từng thẻ dựa vào kết quả đã sinh. Cứ mỗi ô chọn đúng với ô kết quả thì thẻ chơi được tính 1 điểm. Giả thiết biết các ô chọn cũng như các điểm tương ứng của từng thẻ chơi, hãy xác định tất cả các kết quả có thể có mà máy sinh ra.

Dữ liệu vào đọc từ file vănbản XOSO.INP gồm:

- Dòng đầu ghi các số N, M, K

- Dòng thứ i trong N dòng tiếp ghi thẻ chơi của người i gồm K+1 số: K số đầu là các số hiệu của các ô chọn, cuối cùng là điểm tương ứng.

Ghi kết quả ra file văn bản XOSO.OUT, mỗi dòng là một kết quả gồm K số ghi số hiệu các ô mà máy đã sinh.

Ghi chú:

- Các số trên cùng một dòng trong các file vào/ ra, được ghi cách nhau ít nhất một dấu trắng.

- Giới hạn kích thước:N ≤ 100, M ≤50, K ≤10.

- Dữ liệu vào trong cáctest là hợp lệ và đảm bảo có ít nhất một đáp án. Ví dụ:

Hướng dẫn giải

Ta nhận thấy rằng mỗi nghiệm của bài toán chính là một cấu hình của tổ hợp chập K của M phần tử. Ta áp dụng thuật toán quay lui để duyệt mọi cấu hình tổ hợp để tìm ra cấu hình thoả mãn. Tuy nhiên để giảm bớt số lần duyệt ta cần phải loại những thẻ mà chúng có tổng điểm bằng 0 và cần đánh dấu những thẻ đã được chọn.

Dùng mảng ok[0..51] of boolean để phân biệt giữa ô có điểm và những ô không có điểm. Nếu ok[i]= false thì cho biết thẻ thứ i không có điểm. Còn logic[i,j] = true cho ta biết người thứ i đánh dấu vào thứ j của thẻ.