Đệ quy – Quay lui

Giới thiệu:

Nằm trong nhóm các thuật toán sử dụng kỹ thuật ĐỆ QUY. Kỹ thuật QUAY LUI là một kỹ thuật quan trọng mà người lập trình cần nắm để ứng dụng trong việc giải quyết các bài toán cần phải “Thử nhiều phương án khác nhau” và sau mỗi lần thử ta phải trở lại (quay lui) lại trạng thái trước đó để thử cho trạng thái mới.

Mô hình chung khi cài đặt ĐỆ QUY QUAY LUI:

function Try(Trạng thái thứ K)
{	
    // Trường hợp cơ sở
    if (<Đạt tới trạng thái đầy đủ>)
    {
        <output/lưu lại phương án đã xây dựng nếu thoả điều kiện>
        return; // Quay lui
    }
	
    //Phần đệ quy
    for (<xét tất cả các trạng thái i tiếp theo có thể ở K>)
    {
        Nếu trạng thái i hợp lệ{
            <Ghi dấu trạng thái i/thêm i vào tập đang xét>
            Try(K + 1); // Thử với trạng thái tiếp theo
            <xoá bỏ giá trị i khỏi tập đang xét>
        }
    }
}

Một số bài toán ví dụ minh họa Đệ quy – Quay lui:

Bài toán 8 quân hậu:

Tóm tắt bài toán:

Chương trình mẫu rút gọn [Mã nguồn đầy đủ]

int n, m, countSolution = 0; 
bool PrintSolution = false; // Tùy chọn có in phương án hay không
bool check(vector < int > a, int x, int y) {
  // kiểm tra tất cả các quân đã đặt trong a có ăn quân đặt ở ô x, y
  for (int i = 0; i < a.size(); i++) {
    if ((a[i] != -1) && ((y == a[i]) || (i == x) || (i + a[i] == x + y) || (i - a[i] == x - y)))
      return false;
  }
  return true;
}
void Try(int k, vector < int > a) {
  // điểm dừng
  if (a.back() != -1) { // khi đã đặt đủ quân hậu --> mảng a được đánh dấu hết
    if (PrintSolution) { // Tùy chọn có in phương án hay không
      cout << "Found " << endl;
      for (int i = 0; i < n; i++) cout << i << " " << a[i] << endl;
      cout << "----------" << endl;
    }
    countSolution++; // Đếm số lượng phương án đã xác định được
    return;
  };
  // Gọi đệ quy
  for (int i = 0; i < m; i++) {
    if (check(a, k, i)) { // kiểm tra xem đặt được vào cột i hay không
      a[k] = i; // đặt thử lên cột i trên hàng k
      Try(k + 1, a);
      a[k] = -1; // hủy cách đặt tại cột i
    }
  }
  return;
}

Mở rộng bài toán, người ta sẽ nhập vào kích thước bàn cờ là cặp số m, n tùy ý và thêm một số ràng buộc về ô cấm, không được đặt quân hậu vào …

Bài toán mã đi tuần:

📌 Bài toán:

Bài toán Mã đi tuần (Knight’s Tour) là một bài toán cổ điển trong lập trình và toán học, xuất phát từ cách di chuyển của quân mã (knight) trong cờ vua.

Yêu cầu:
Cho một bàn cờ kích thước n x n và vị trí xuất phát ban đầu, hãy tìm một hành trình của quân mã sao cho nó đi qua tất cả các ô của bàn cờ đúng một lần duy nhất.

⚙️ Di chuyển của quân mã:

Quân mã trong cờ vua có 8 kiểu di chuyển hình chữ “L”, mỗi nước đi gồm:

• 2 ô theo một hướng (ngang hoặc dọc), sau đó 1 ô vuông góc.

Ý tưởng giải bằng đệ quy quay lui:

• Duyệt tất cả các nước đi hợp lệ.
• Đánh dấu ô đã đi.
• Gọi đệ quy sang bước tiếp theo.
• Nếu không đi được nữa → quay lui (backtrack).
• Nếu đã đi qua đúng \(n^2\) ô → in lời giải.

Chương trình minh họa

const int N = 8;  // Kích thước bàn cờ NxN
int board[N][N];  // Ma trận lưu trạng thái ô đã đi
int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

// In lời giải
void printBoard() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << setw(2) << board[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

// Hàm kiểm tra ô hợp lệ
bool isValid(int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
}

// Đệ quy quay lui giải mã đi tuần
bool knightTour(int x, int y, int moveCount) {
    if (moveCount == N * N) {
        printBoard();  // In ra lời giải đầu tiên
        return true;
    }

    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny)) {
            board[nx][ny] = moveCount;
            if (knightTour(nx, ny, moveCount + 1))
                return true;  // Dừng ở lời giải đầu tiên
            board[nx][ny] = -1;  // Quay lui
        }
    }

    return false;
}

int main() {
    // Khởi tạo bàn cờ: -1 nghĩa là chưa đi
    memset(board, -1, sizeof(board));

    int startX = 0, startY = 0;  // Vị trí bắt đầu
    board[startX][startY] = 0;

    if (!knightTour(startX, startY, 1))
        cout << "Không tìm được lời giải!" << endl;

    return 0;
}

Bài toán liệt kê dãy ngoặc:

Bài toán Liệt kê các xâu ký tự có độ dài K theo thứ tự từ điển