Khóa học CTDL và GT

Bài 12.2. Bài toán N-queens và các ứng dụng của Quay lui

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ lặn sâu vào một bài toán kinh điển trong thế giới khoa học máy tính, đó là Bài toán N-queens, và cùng khám phá một kỹ thuật giải thuật vô cùng mạnh mẽ và linh hoạt đi kèm với nó: Kỹ thuật Quay lui (Backtracking).

Tại sao bài toán N-queens lại nổi tiếng đến vậy? Bởi vì nó là một ví dụ hoàn hảo để minh họa cho cách hoạt động của quay lui – một phương pháp giải quyết các bài toán ràng buộc (constraint satisfaction problems) bằng cách thử và sai một cách có hệ thống. Không chỉ dừng lại ở cờ vua, kỹ thuật này còn là nền tảng cho việc giải quyết hàng loạt các vấn đề thực tế khác, từ giải Sudoku cho đến tìm đường đi trong mê cung hay tối ưu hóa các vấn đề phức tạp.

Hãy cùng bắt đầu hành trình khám phá sức mạnh của quay lui thông qua bài toán N-queens đầy thách thức nhé!

Bài toán N-queens là gì?

Bài toán N-queens được phát biểu như sau: Cho một bàn cờ vua kích thước N x N. Nhiệm vụ của chúng ta là đặt N con hậu lên bàn cờ sao cho không có bất kỳ hai con hậu nào đe dọa lẫn nhau.

Nhắc lại luật đi quân của cờ hậu trong cờ vua: một con hậu có thể tấn công bất kỳ quân cờ nào nằm cùng hàng, cùng cột hoặc cùng đường chéo với nó. Do đó, điều kiện để N con hậu không đe dọa lẫn nhau chính là:

• Không có hai con hậu nào nằm trên cùng một hàng.
• Không có hai con hậu nào nằm trên cùng một cột.
• Không có hai con hậu nào nằm trên cùng một đường chéo (cả hai loại đường chéo: chính và phụ).

Dễ thấy rằng, nếu chúng ta đặt N con hậu lên bàn cờ N x N mà không có hai con nào cùng hàng, thì hiển nhiên mỗi con hậu sẽ chiếm đúng một hàng và đúng một cột duy nhất. Như vậy, bài toán thực chất quy về việc tìm cách đặt N con hậu vào N hàng khác nhau sao cho không có hai con nào cùng cột hoặc cùng đường chéo.

Ví dụ với N = 4, một cấu hình hợp lệ sẽ trông như thế này (Q là Hậu, . là ô trống):

. Q . .
. . . Q
Q . . .
. . Q .

Ở đây, không có hai quân Hậu nào cùng hàng, cùng cột hay cùng đường chéo.

Bài toán trở nên khó khăn khi N tăng lên. Số lượng cách đặt N quân hậu lên N x N ô là rất lớn (chọn N ô trong N^2 ô). Ngay cả khi ta biết mỗi con phải ở một hàng riêng (chỉ cần chọn N cột cho N hàng), số lượng hoán vị cột vẫn là N!. Với N=8, N! = 40,320. Với N=10, N! = 3,628,800. Việc kiểm tra tất cả các hoán vị này có thể khả thi cho N nhỏ, nhưng với N lớn hơn nữa, nó trở nên quá chậm. Đây là lúc chúng ta cần một phương pháp thông minh hơn, và quay lui chính là câu trả lời.

Kỹ thuật Quay lui (Backtracking)

Quay lui là một kỹ thuật giải thuật tổng quát dùng để tìm kiếm giải pháp cho các bài toán bằng cách xây dựng các giải pháp tiềm năng từng bước một, và loại bỏ (prune) những giải pháp không thỏa mãn điều kiện ngay khi có thể. Nếu tại một bước nào đó, giải pháp đang được xây dựng không còn khả năng dẫn đến một giải pháp hợp lệ cuối cùng, thuật toán sẽ quay lui (undo) lại bước trước đó và thử một lựa chọn khác.

Hãy hình dung bạn đang đi trong một mê cung để tìm đường ra. Bạn đi theo một lối rẽ. Nếu đi đến cuối đường mà không thấy lối ra (đi vào ngõ cụt), bạn phải quay ngược lại điểm rẽ trước đó và thử một lối đi khác. Quay lui hoạt động tương tự:

1. Thử một lựa chọn: Tại trạng thái hiện tại, chọn một trong các lựa chọn khả thi tiếp theo.
2. Kiểm tra ràng buộc: Ngay sau khi thực hiện lựa chọn, kiểm tra xem giải pháp đang xây dựng (bao gồm cả lựa chọn mới) có còn khả năng dẫn đến giải pháp cuối cùng hợp lệ hay không.
3. Tiếp tục hoặc Quay lui:
   • Nếu vẫn khả thi (chưa vi phạm ràng buộc), tiếp tục xây dựng giải pháp bằng cách lặp lại bước 1 cho trạng thái mới. Đây thường là một lời gọi đệ quy (recursive call).
   • Nếu không còn khả thi (đã vi phạm ràng buộc), bỏ qua lựa chọn hiện tại này và quay lui về trạng thái trước đó. Hoàn tác lại lựa chọn vừa thực hiện để "lấy lại" trạng thái ban đầu trước khi thử lựa chọn đó. Sau đó, thử lựa chọn khác nếu còn.
4. Điều kiện dừng: Nếu giải pháp được xây dựng hoàn chỉnh và thỏa mãn tất cả ràng buộc, chúng ta đã tìm thấy một giải pháp (hoặc tất cả các giải pháp, tùy bài toán). Nếu đã thử hết tất cả các lựa chọn tại một bước mà không có lựa chọn nào dẫn đến giải pháp, thì không có giải pháp nào từ trạng thái hiện tại, và chúng ta cũng quay lui về bước trước đó nữa.

Quay lui thường được hiện thực thông qua đệ quy. Mỗi lời gọi đệ quy thường tương ứng với việc đưa ra một quyết định cho một bước trong quá trình xây dựng giải pháp.

Áp dụng Quay lui giải Bài toán N-queens

Chúng ta sẽ giải bài toán N-queens bằng cách đặt từng con hậu vào từng hàng, bắt đầu từ hàng 0. Với mỗi hàng, chúng ta sẽ thử đặt con hậu vào từng cột một.

1. Trạng thái: Trạng thái hiện tại có thể được định nghĩa bởi số hàng mà chúng ta đang xem xét để đặt hậu.
2. Lựa chọn: Tại hàng hiện tại (row), chúng ta có N lựa chọn: đặt con hậu vào cột 0, cột 1, ..., cột N-1.
3. Kiểm tra ràng buộc: Sau khi chọn đặt con hậu vào cột col tại hàng row, chúng ta cần kiểm tra xem vị trí này có an toàn không. An toàn nghĩa là vị trí (row, col) không bị đe dọa bởi bất kỳ con hậu nào đã được đặt ở các hàng trước đó (0 đến row-1).
4. Đệ quy: Nếu vị trí (row, col) an toàn, chúng ta đánh dấu rằng đã đặt một con hậu tại đó (cập nhật trạng thái bàn cờ) và chuyển sang giải quyết bài toán con: đặt các con hậu vào các hàng còn lại (bắt đầu từ hàng row + 1). Chúng ta thực hiện điều này bằng một lời gọi đệ quy tới hàm giải với tham số row + 1.
5. Quay lui: Nếu lời gọi đệ quy trả về rằng việc đặt hậu ở vị trí hiện tại không dẫn đến giải pháp (hoặc nếu chúng ta muốn tìm tất cả các giải pháp, sau khi lời gọi đệ quy kết thúc), chúng ta cần hoàn tác việc đặt con hậu tại (row, col). Điều này cho phép chúng ta thử các cột khác cho hàng row. Nếu vị trí (row, col) ngay từ đầu đã không an toàn, chúng ta bỏ qua vị trí này và thử cột tiếp theo.
6. Điều kiện dừng (Base Case): Khi chúng ta đã đặt thành công N con hậu (tức là hàm đệ quy được gọi với row == N), điều đó có nghĩa là chúng ta đã tìm thấy một cấu hình hợp lệ. Chúng ta có thể in cấu hình này ra và quay lui để tìm kiếm các giải pháp khác (nếu có).

Cài đặt bằng C++

Chúng ta sẽ cần một hàm kiểm tra tính an toàn isSafe(board, row, col) và một hàm đệ quy chính solveNQueensUtil(board, row, N). Bàn cờ có thể được biểu diễn bằng một vector<vector<string>> hoặc đơn giản hơn là một vector<int> lưu trữ vị trí cột của con hậu trên mỗi hàng. Để dễ hiểu và trực quan khi in ra, ta dùng vector<vector<string>>.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Hàm kiểm tra xem có an toàn khi đặt hậu tại board[row][col] hay không
// Chúng ta chỉ cần kiểm tra các hàng phía trên, vì chúng ta đặt hậu từ trên xuống
bool isSafe(const vector<vector<string>>& board, int row, int col, int N) {
    // 1. Kiểm tra cột trên
    // Duyệt từ hàng 0 đến hàng row-1 trong cùng cột col
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == "Q") {
            return false; // Có hậu ở hàng trên cùng cột
        }
    }

    // 2. Kiểm tra đường chéo trên bên trái
    // Duyệt từ vị trí hiện tại lên trên và sang trái
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == "Q") {
            return false; // Có hậu trên đường chéo trên bên trái
        }
    }

    // 3. Kiểm tra đường chéo trên bên phải
    // Duyệt từ vị trí hiện tại lên trên và sang phải
    for (int i = row, j = col; i >= 0 && j < N; --i, ++j) {
        if (board[i][j] == "Q") {
            return false; // Có hậu trên đường chéo trên bên phải
        }
    }

    // Nếu vượt qua cả 3 kiểm tra, vị trí này an toàn
    return true;
}

// Hàm in ra một cấu hình giải pháp
void printSolution(const vector<vector<string>>& board) {
    cout << "--- Solution ---" << endl;
    for (const auto& row : board) {
        for (const string& cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }
    cout << "----------------" << endl;
}

// Hàm đệ quy chính giải bài toán N-queens
// current_row: hàng hiện tại đang xem xét để đặt hậu
// N: kích thước bàn cờ
void solveNQueensUtil(vector<vector<string>>& board, int current_row, int N) {
    // Điều kiện dừng đệ quy (Base Case):
    // Nếu đã đặt thành công hậu cho tất cả các hàng (từ 0 đến N-1)
    if (current_row >= N) {
        // Tìm thấy một giải pháp, in ra
        printSolution(board);
        return; // Quay lui để tìm các giải pháp khác
    }

    // Bước đệ quy: Thử đặt hậu vào từng cột của hàng current_row
    for (int col = 0; col < N; ++col) {
        // Kiểm tra xem có an toàn khi đặt hậu ở board[current_row][col] không
        if (isSafe(board, current_row, col, N)) {
            // Nếu an toàn, đặt hậu tại vị trí này (LỰA CHỌN)
            board[current_row][col] = "Q";

            // Gọi đệ quy để giải quyết bài toán cho hàng tiếp theo (HÀNH ĐỘNG TIẾP THEO)
            solveNQueensUtil(board, current_row + 1, N);

            // QUAY LUI (BACKTRACK):
            // Sau khi lời gọi đệ quy kết thúc (dù nó tìm được giải pháp hay không),
            // chúng ta cần hoàn tác lại việc đặt hậu tại board[current_row][col]
            // để có thể thử các cột khác cho hàng current_row.
            board[current_row][col] = ".";
        }
    }
}

// Hàm khởi tạo và gọi hàm giải N-queens
void solveNQueens(int N) {
    // Khởi tạo bàn cờ N x N với tất cả các ô trống "."
    vector<vector<string>> board(N, vector<string>(N, "."));

    // Bắt đầu giải bài toán từ hàng 0
    solveNQueensUtil(board, 0, N);
}

int main() {
    int N = 4; // Ví dụ với N = 4
    cout << "Tim cac cau hinh cho bai toan " << N << "-queens:" << endl;
    solveNQueens(N);

    N = 8; // Ví dụ với N = 8
    cout << "\nTim cac cau hinh cho bai toan " << N << "-queens:" << endl;
    // solveNQueens(N); // Bỏ comment dòng này nếu muốn chạy thử N=8, có thể hơi lâu để in hết

    return 0;
}

Giải thích Code N-queens

• isSafe(board, row, col, N): Hàm này nhận vào trạng thái bàn cờ hiện tại (board), tọa độ ô đang xét (row, col), và kích thước bàn cờ (N). Nó kiểm tra xem có con hậu nào đã được đặt ở các hàng 0 đến row-1 mà lại cùng cột col, cùng đường chéo trên bên trái, hoặc cùng đường chéo trên bên phải với ô (row, col) hay không. Nếu có, trả về false (không an toàn). Ngược lại, trả về true. Chúng ta chỉ cần kiểm tra các hàng phía trên vì các hàng từ row trở xuống chưa có hậu nào được đặt.
• printSolution(board): Hàm đơn giản này dùng để in ra trạng thái của bàn cờ khi tìm được một giải pháp hợp lệ.
• solveNQueensUtil(board, current_row, N): Đây là trái tim của giải thuật quay lui.
  • Điều kiện dừng: if (current_row >= N): Nếu current_row bằng N, tức là chúng ta đã thành công trong việc đặt hậu cho các hàng 0 đến N-1. Một giải pháp đã được tìm thấy, chúng ta in nó ra.
  • Bước đệ quy: for (int col = 0; col < N; ++col): Vòng lặp này duyệt qua tất cả các cột có thể đặt hậu trong hàng current_row.
  • if (isSafe(board, current_row, col, N)): Trước khi đặt hậu, chúng ta kiểm tra ràng buộc: vị trí (current_row, col) có an toàn không?
  • board[current_row][col] = "Q";: Nếu an toàn, chúng ta thử đặt hậu vào vị trí này. Đây là việc thực hiện một lựa chọn.
  • solveNQueensUtil(board, current_row + 1, N);: Chúng ta gọi đệ quy để tiếp tục quá trình đặt hậu cho hàng tiếp theo (current_row + 1).
  • board[current_row][col] = ".";: Đây chính là bước QUAY LUI. Sau khi lời gọi đệ quy solveNQueensUtil(board, current_row + 1, N) hoàn thành (dù nó tìm được giải pháp hay không), chúng ta cần hoàn tác lại quyết định đặt hậu ở cột col của hàng current_row. Điều này là cần thiết để vòng lặp for có thể tiếp tục thử các cột khác (col + 1, col + 2, ...) cho cùng hàng current_row. Nếu không có bước này, chúng ta sẽ chỉ tìm được giải pháp đầu tiên mà thuật toán tìm thấy trên một nhánh duy nhất. Bằng cách quay lui, chúng ta khám phá tất cả các nhánh có thể và do đó tìm tất cả các giải pháp.
• solveNQueens(N): Hàm này chỉ có nhiệm vụ khởi tạo bàn cờ trống và gọi hàm đệ quy bắt đầu từ hàng 0.
• main(): Đơn giản là nơi thiết lập giá trị N và gọi hàm solveNQueens.

Ưu điểm của cách tiếp cận quay lui này là nó không cần phải sinh ra và kiểm tra tất cả N! hoán vị cột. Ngay khi phát hiện một vị trí không an toàn, nó sẽ dừng việc khám phá nhánh đó và quay lui, giúp giảm đáng kể không gian tìm kiếm so với phương pháp brute force thuần túy.

Các ứng dụng khác của Quay lui

Kỹ thuật quay lui không chỉ giới hạn ở bài toán N-queens. Nó là một công cụ mạnh mẽ cho nhiều loại bài toán đòi hỏi phải thử các kết hợp hoặc hoán vị để tìm giải pháp thỏa mãn các ràng buộc. Một số ứng dụng phổ biến khác bao gồm:

• Giải Sudoku: Điền các số vào ô trống sao cho thỏa mãn luật Sudoku.
• Bài toán mã đi tuần (Knight's Tour Problem): Tìm một đường đi của quân mã trên bàn cờ sao cho nó đi qua mỗi ô đúng một lần.
• Tìm tất cả các hoán vị của một tập hợp: Liệt kê mọi cách sắp xếp các phần tử.
• Tìm tất cả các tập con thỏa mãn điều kiện (Subset Sum Problem): Tìm một tập con của một tập hợp các số sao cho tổng của chúng bằng một giá trị cho trước.
• Bài toán Tô màu đồ thị (Graph Coloring Problem): Gán màu cho các đỉnh của đồ thị sao cho hai đỉnh kề nhau không có cùng màu, với số màu tối thiểu.
• Giải mê cung: Tìm đường đi từ điểm bắt đầu đến điểm kết thúc.

Hãy cùng xem một ví dụ khác về ứng dụng của quay lui: Giải Sudoku.

Áp dụng Quay lui giải Sudoku

Bài toán Sudoku là điền các số từ 1 đến 9 vào các ô trống trong một lưới 9x9 sao cho mỗi hàng, mỗi cột và mỗi khối 3x3 đều chứa các số từ 1 đến 9 mà không lặp lại.

Cách tiếp cận quay lui cho Sudoku:

1. Tìm ô trống: Tìm ô trống đầu tiên trên lưới (có giá trị 0).
2. Điều kiện dừng: Nếu không còn ô trống nào, lưới Sudoku đã được giải.
3. Thử các giá trị: Nếu có ô trống tại (row, col), thử điền các số từ 1 đến 9 vào ô đó.
4. Kiểm tra ràng buộc: Với mỗi số đang thử (num), kiểm tra xem việc đặt num vào ô (row, col) có hợp lệ theo luật Sudoku hay không (kiểm tra hàng, cột và khối 3x3 tương ứng).
5. Đệ quy: Nếu num hợp lệ, đặt num vào ô (row, col) và gọi đệ quy để giải phần còn lại của lưới.
6. Quay lui:
   • Nếu lời gọi đệ quy trả về true (nghĩa là nó tìm được giải pháp), thì chúng ta cũng trả về true.
   • Nếu lời gọi đệ quy trả về false (nghĩa là việc đặt num ở đây không dẫn đến giải pháp), chúng ta hoàn tác việc đặt số (board[row][col] = 0) và thử số tiếp theo cho ô (row, col).
7. Không có giải pháp: Nếu đã thử hết các số từ 1 đến 9 cho ô (row, col) mà không có số nào dẫn đến giải pháp, trả về false.

Cài đặt Sudoku Solver bằng C++

#include <iostream>
#include <vector>

using namespace std;

// Kích thước lưới Sudoku
const int GRID_SIZE = 9;

// Hàm in lưới Sudoku
void printGrid(const vector<vector<int>>& grid) {
    for (int row = 0; row < GRID_SIZE; ++row) {
        if (row % 3 == 0 && row != 0) {
            cout << "----------------------" << endl;
        }
        for (int col = 0; col < GRID_SIZE; ++col) {
            if (col % 3 == 0 && col != 0) {
                cout << " | ";
            }
            cout << grid[row][col] << " ";
        }
        cout << endl;
    }
}

// Hàm kiểm tra xem một số có hợp lệ tại vị trí (row, col) hay không
bool isValid(const vector<vector<int>>& grid, int row, int col, int num) {
    // 1. Kiểm tra hàng: xem num đã tồn tại trong hàng này chưa
    for (int c = 0; c < GRID_SIZE; ++c) {
        if (grid[row][c] == num) {
            return false; // Đã tồn tại trong hàng
        }
    }

    // 2. Kiểm tra cột: xem num đã tồn tại trong cột này chưa
    for (int r = 0; r < GRID_SIZE; ++r) {
        if (grid[r][col] == num) {
            return false; // Đã tồn tại trong cột
        }
    }

    // 3. Kiểm tra khối 3x3: xem num đã tồn tại trong khối này chưa
    // Xác định tọa độ góc trên bên trái của khối 3x3 chứa (row, col)
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (grid[r + startRow][c + startCol] == num) {
                return false; // Đã tồn tại trong khối 3x3
            }
        }
    }

    // Nếu vượt qua cả 3 kiểm tra, số num hợp lệ tại vị trí (row, col)
    return true;
}

// Hàm tìm ô trống (có giá trị 0) tiếp theo
// Trả về true nếu tìm thấy, false nếu không còn ô trống
bool findEmptyLocation(const vector<vector<int>>& grid, int& row, int& col) {
    for (row = 0; row < GRID_SIZE; ++row) {
        for (col = 0; col < GRID_SIZE; ++col) {
            if (grid[row][col] == 0) {
                return true; // Tìm thấy ô trống tại (row, col)
            }
        }
    }
    return false; // Không còn ô trống nào trên lưới
}

// Hàm đệ quy chính giải Sudoku
bool solveSudoku(vector<vector<int>>& grid) {
    int row, col;

    // 1. Điều kiện dừng đệ quy (Base Case):
    // Nếu không tìm thấy ô trống nào nữa, lưới đã được giải thành công
    if (!findEmptyLocation(grid, row, col)) {
        return true; // Lưới đã giải xong
    }

    // 2. Bước đệ quy: Có ô trống tại (row, col), thử điền các số từ 1 đến 9
    for (int num = 1; num <= 9; ++num) {
        // Kiểm tra xem số num có hợp lệ tại vị trí (row, col) hay không (KIỂM TRA RÀNG BUỘC)
        if (isValid(grid, row, col, num)) {
            // Nếu hợp lệ, đặt số num vào ô này (LỰA CHỌN)
            grid[row][col] = num;

            // Gọi đệ quy để giải phần còn lại của lưới (HÀNH ĐỘNG TIẾP THEO)
            // Nếu lời gọi đệ quy trả về true (nghĩa là tìm được giải pháp từ trạng thái này)
            if (solveSudoku(grid)) {
                return true; // Truyền kết quả thành công lên các tầng đệ quy trên
            }

            // QUAY LUI (BACKTRACK):
            // Nếu lời gọi đệ quy trả về false (nghĩa là việc đặt số num không dẫn đến giải pháp),
            // chúng ta cần hoàn tác lại việc đặt số num
            // để vòng lặp for có thể thử số tiếp theo cho ô (row, col).
            grid[row][col] = 0;
        }
    }

    // Nếu đã thử hết các số từ 1 đến 9 cho ô (row, col) mà không có số nào dẫn đến giải pháp
    // thì không có giải pháp nào từ trạng thái hiện tại.
    return false; // Báo hiệu không tìm được giải pháp, cần quay lui ở tầng trên
}

int main() {
    // Lưới Sudoku ví dụ (0 biểu thị ô trống)
    vector<vector<int>> grid = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    cout << "Lưới Sudoku ban đầu:" << endl;
    printGrid(grid);
    cout << "\nĐang giải..." << endl;

    if (solveSudoku(grid)) {
        cout << "\nLưới Sudoku đã giải:" << endl;
        printGrid(grid);
    } else {
        cout << "\nKhông tìm thấy giải pháp cho lưới Sudoku này." << endl;
    }

    return 0;
}

Giải thích Code Sudoku Solver

• GRID_SIZE: Hằng số xác định kích thước lưới (9).
• printGrid: Hàm helper để in lưới Sudoku một cách dễ đọc hơn.
• isValid(grid, row, col, num): Hàm kiểm tra xem việc đặt số num vào ô (row, col) có hợp lệ hay không. Nó kiểm tra ba điều kiện:
  1. Số num đã tồn tại trong hàng row chưa.
  2. Số num đã tồn tại trong cột col chưa.
  3. Số num đã tồn tại trong khối 3x3 chứa ô (row, col) chưa. Để kiểm tra khối 3x3, chúng ta tính tọa độ góc trên bên trái của khối đó bằng row - row % 3 và col - col % 3.
• findEmptyLocation(grid, row, col): Hàm này duyệt qua lưới để tìm ô trống đầu tiên (giá trị 0). Nó trả về true và cập nhật tham chiếu row, col nếu tìm thấy, ngược lại trả về false.
• solveSudoku(grid): Hàm đệ quy chính.
  • Điều kiện dừng: if (!findEmptyLocation(grid, row, col)): Nếu không tìm thấy ô trống nào, lưới đã đầy và vì chúng ta luôn đảm bảo tính hợp lệ từng bước, lưới đã được giải đúng. Trả về true.
  • Bước đệ quy: for (int num = 1; num <= 9; ++num): Vòng lặp này thử điền tất cả các số từ 1 đến 9 vào ô trống tìm được tại (row, col).
  • if (isValid(grid, row, col, num)): Kiểm tra tính hợp lệ của số num tại vị trí này.
  • grid[row][col] = num;: Nếu hợp lệ, thử đặt số num.
  • if (solveSudoku(grid)) return true;: Gọi đệ quy để giải phần còn lại. Nếu lời gọi này trả về true, nghĩa là nhánh này dẫn đến một giải pháp hoàn chỉnh, chúng ta không cần thử các số khác cho ô hiện tại nữa và có thể trả về true ngay lập tức để báo hiệu thành công. (Phiên bản này chỉ tìm một giải pháp).
  • grid[row][col] = 0;: Đây là bước QUAY LUI. Nếu lời gọi đệ quy solveSudoku(grid) ở trên trả về false (nghĩa là việc đặt num tại (row, col) không thể hoàn thành lưới một cách hợp lệ), chúng ta phải hoàn tác việc đặt số num này (xóa nó đi, trả về 0) để vòng lặp for có thể tiếp tục thử số num + 1.
  • return false;: Nếu vòng lặp for kết thúc mà không có số nào từ 1 đến 9 dẫn đến giải pháp (tất cả các nhánh từ ô (row, col) đều thất bại), thì không có giải pháp nào từ trạng thái lưới hiện tại. Trả về false để báo hiệu cho tầng đệ quy gọi nó rằng cần quay lui.
• main(): Khởi tạo một lưới Sudoku ví dụ và gọi solveSudoku. Dựa vào kết quả trả về để in lưới đã giải hoặc thông báo không có giải pháp.

So với bài toán N-queens (thường tìm tất cả các giải pháp), Sudoku Solver này chỉ tìm một giải pháp đầu tiên nó gặp được. Sự khác biệt nằm ở cách xử lý kết quả của lời gọi đệ quy: trong N-queens, chúng ta luôn quay lui sau lời gọi đệ quy để tìm giải pháp khác; trong Sudoku (phiên bản tìm một giải pháp), chúng ta chỉ quay lui nếu lời gọi đệ quy thất bại.

Tổng kết về Quay lui

Qua hai ví dụ N-queens và Sudoku, chúng ta thấy được sức mạnh và tính linh hoạt của kỹ thuật quay lui. Các thành phần cốt lõi luôn là:

• Xây dựng giải pháp từng bước: Thường được hiện thực bằng đệ quy, mỗi tầng đệ quy đưa ra một quyết định cho một phần của bài toán.
• Kiểm tra ràng buộc sớm: Tại mỗi bước, kiểm tra xem quyết định hiện tại có vi phạm ràng buộc nào khiến giải pháp không thể hoàn thành hay không. Việc này giúp loại bỏ (prune) các nhánh tìm kiếm không tiềm năng sớm nhất có thể.
• Hoàn tác (Backtrack): Nếu một nhánh tìm kiếm không thành công (hoặc để tìm các giải pháp khác), hoàn tác lại quyết định gần nhất để thử các lựa chọn khác.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Sinh hoán vị.

Cho số nguyên dương N. Nhiệm vụ của bạn là hãy liệt kê tất cả các hoán vị của 1, 2, .., N. Ví dụ với N = 3 ta có kết quả: 123, 132, 213, 231, 312, 321.

Input Format

Dòng đầu tiên đưa vào số lượng test T. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một số tự nhiên N được viết trên một dòng. T, n thỏa mãn ràng buộc: 1≤T, N≤10.

Constraints

.

Output Format

Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ:

Dữ liệu vào

2
2
4

Dữ liệu ra

12 21
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

Ok, đây là hướng dẫn ngắn gọn để giải bài toán "Sinh hoán vị" bằng C++:

1. Ý tưởng chính: Ta sẽ bắt đầu với hoán vị có thứ tự từ điển nhỏ nhất (1, 2, ..., N) và sau đó liên tục sinh ra hoán vị kế tiếp theo thứ tự từ điển cho đến khi không còn hoán vị nào nữa.
2. Sử dụng thư viện chuẩn: C++ cung cấp sẵn một hàm rất tiện lợi trong thư viện <algorithm> là std::next_permutation. Hàm này nhận vào hai iterator (thường là begin() và end() của một container như std::vector hoặc một mảng) và biến đổi container đó thành hoán vị kế tiếp. Nếu có hoán vị kế tiếp, nó trả về true; nếu không, nó trả về false.
3. Các bước thực hiện:
   • Đọc số N.
   • Tạo một std::vector (hoặc mảng) chứa các số từ 1 đến N theo thứ tự tăng dần (ví dụ: vector<int> p(N); for(int i=0; i<N; ++i) p[i] = i+1;). Đây là hoán vị đầu tiên.
   • Sử dụng vòng lặp do...while.
     • Bên trong vòng lặp: In ra các phần tử của vector p (hoán vị hiện tại), cách nhau bởi dấu cách.
     • Điều kiện lặp: Gọi std::next_permutation(p.begin(), p.end()). Vòng lặp sẽ tiếp tục chừng nào hàm này còn trả về true.
   • Sau khi vòng lặp kết thúc, in ký tự xuống dòng để chuẩn bị cho test case tiếp theo.
4. Include cần thiết: <iostream>, <vector>, <algorithm>.

Làm thêm nhiều bài tập miễn phí tại đây