Thuật toán quay lui (backtracking) là một kỹ thuật giải quyết các bài toán liên quan đến tìm kiếm tất cả các giải pháp có thể của một bài toán. Thường được sử dụng trong các bài toán về tối ưu hoặc những bài toán có thể phân loại bằng cách duyệt toàn bộ tập hợp các giải pháp có thể.
Dưới đây là một ví dụ về thuật toán quay lui trong Pascal để tìm kiếm tất cả các cách sắp xếp một tập hợp gồm n phần tử:
program Backtracking;
const
n=3; { số phần tử cần sắp xếp }
var
a: array[1..n] of integer;
b: array[1..n] of boolean;
procedure Try(i: integer);
var
j: integer;
begin
for j:=1 to n do
if not b[j] then
begin
a[i]:=j;
b[j]:=true;
if i=n then
begin
{ in ra cách sắp xếp }
for j:=1 to n do write(a[j],' ');
writeln;
end
else Try(i+1);
b[j]:=false;
end;
end;
begin
Try(1);
end.
Trong ví dụ trên, chúng ta duyệt tất cả các cách sắp xếp có thể của tập hợp gồm n
phần tử. Tuy nhiên, trong một số bài toán, chúng ta có thể thực hiện một số kiểm tra để cắt tỉa những nhánh không cần thiết của cây tìm kiếm, giúp tăng tốc độ thực hiện thuật toán. Chẳng hạn, trong bài toán TSP (Traveling Salesman Problem), chúng ta có thể kiểm tra số lượng các đỉnh đã duyệt, nếu đã duyệt tất cả các đỉnh nhưng đường đi hiện tại chưa tối ưu hơn đường đi tốt nhất đã tìm được, chúng ta có thể dừng quá trình duyệt tại nhánh hiện tại.
Ngoài ra, thuật toán quay lui còn được áp dụng trong nhiều lĩnh vực khác nhau như: tìm kiếm từ điển, xếp hình, giải Sudoku, giải cờ vua, … Tuy nhiên, việc sử dụng thuật toán quay lui đòi hỏi phải tìm ra được phương pháp cắt tỉa phù hợp để giảm thiểu số lượng trường hợp phải duyệt.
Dưới đây là một ví dụ cụ thể về thuật toán quay lui để giải bài toán Sudoku. Bài toán này yêu cầu điền các số từ 1 đến 9 vào các ô trống trên một bảng 9×9 sao cho mỗi hàng, mỗi cột và mỗi khối 3×3 đều chứa đủ các số từ 1 đến 9.
program SudokuSolver;
const
N = 9;
type
TBoard = array[1..N, 1..N] of Integer;
var
Board: TBoard;
function IsValid(Board: TBoard; Row, Col, Num: Integer): Boolean;
var
i, j, Row0, Col0: Integer;
begin
{ kiểm tra hàng và cột }
for i := 1 to N do
if (Board[Row, i] = Num) or (Board[i, Col] = Num) then
Exit(False);
{ kiểm tra khối 3x3 }
Row0 := 3 * ((Row - 1) div 3) + 1;
Col0 := 3 * ((Col - 1) div 3) + 1;
for i := Row0 to Row0 + 2 do
for j := Col0 to Col0 + 2 do
if Board[i, j] = Num then
Exit(False);
Result := True;
end;
procedure PrintBoard(Board: TBoard);
var
i, j: Integer;
begin
for i := 1 to N do
begin
for j := 1 to N do
Write(Board[i, j], ' ');
Writeln;
end;
end;
procedure SolveSudoku(Board: TBoard; Row, Col: Integer; var Found: Boolean);
var
i, j, Num: Integer;
begin
if Row > N then
begin
{ tìm được một giải pháp }
PrintBoard(Board);
Found := True;
Exit;
end;
if Board[Row, Col] <> 0 then
begin
{ ô này đã được điền số }
if Col = N then
SolveSudoku(Board, Row + 1, 1, Found)
else
SolveSudoku(Board, Row, Col + 1, Found);
Exit;
end;
{ duyệt các số từ 1 đến 9 }
for Num := 1 to N do
begin
if IsValid(Board, Row, Col, Num) then
begin
Board[Row, Col] := Num;
if Col = N then
SolveSudoku(Board, Row + 1, 1, Found)
else
SolveSudoku(Board, Row, Col + 1, Found);
if Found then
Exit;
Board[Row, Col] := 0;
end;
end;
end;
begin
{ đọc bảng Sudoku từ file }
{ ... }
{ giải bài toán }
SolveSudoku(Board, 1, 1, Found);
end.