Bài toán 8 quân hậu (8-queens)

Giới thiệu

Bài toán 8 quân hậu là một bài toán kinh điển trong lĩnh vực lý thuyết tổ hợp và giải thuật. Mục tiêu là đặt 8 quân hậu trên bàn cờ 8×8 sao cho không có hai quân hậu nào có thể tấn công lẫn nhau (theo hàng ngang, hàng dọc, hoặc chéo).

Ý tưởng:

Thuật toán quay lui sẽ thử đặt quân hậu lên từng hàng một, từ hàng đầu tiên đến hàng cuối cùng. Với mỗi hàng, thuật toán sẽ thử đặt quân hậu vào từng cột một, kiểm tra xem vị trí đó có an toàn không (không bị các quân hậu đã đặt trước đó tấn công). Nếu an toàn, thuật toán sẽ tiếp tục thử đặt quân hậu vào hàng tiếp theo. Nếu vị trí đặt quân hậu không an toàn, thuật toán sẽ bỏ qua vị trí đó và thử vị trí tiếp theo.

Khởi tạo:

• Tạo mảng board kích thước 8, trong đó board[i] đại diện cho cột mà quân hậu được đặt ở hàng i.
• Khởi tạo tất cả các phần tử của board bằng giá trị -1 (chưa đặt quân hậu).

Hàm Kiểm tra An toàn (isSafe):

• Với mỗi vị trí (row, col) cần kiểm tra:
  • Không có quân hậu nào khác trên cùng cột col.
  • Không có quân hậu nào khác trên các đường chéo tính từ vị trí (row, col) (kiểm tra đường chéo trái và đường chéo phải).

Hàm Đặt Quân Hậu (Try):

• Nếu đã đặt thành công quân hậu ở hàng cuối cùng (hàng thứ 8), lưu lại lời giải và dừng.
• Nếu chưa đạt hàng cuối, thực hiện:
  • Duyệt qua các cột từ 0 đến 7.
  • Với mỗi cột, nếu vị trí (row, col) an toàn (sử dụng hàm isSafe), đặt quân hậu tại đó.
  • Gọi đệ quy hàm Try để thử đặt quân hậu ở hàng tiếp theo.
  • Nếu không tìm được lời giải tiếp theo, bỏ quân hậu khỏi vị trí (row, col) (quay lui) và thử cột khác.

Kết thúc:

• Khi tất cả các hàng đều đã được xử lý, kết quả là tất cả các cách đặt 8 quân hậu trên bàn cờ sao cho chúng không tấn công lẫn nhau đã được tìm thấy.

Cài đặt

Dưới đây là mã nguồn C++ để sinh ra các phương án của bài toán 8 quân hậu bằng phương pháp quay lui (backtracking):

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 8;
vector<int> board(N, -1);  // Bảng cờ, mỗi phần tử lưu vị trí quân hậu theo cột của hàng tương ứng
int solutionCount = 0;

bool isSafe(int row, int col) {
    for (int prevRow = 0; prevRow < row; prevRow++) {
        int prevCol = board[prevRow];
        // Kiểm tra nếu có quân hậu nào khác tấn công vị trí này
        if (prevCol == col || abs(prevCol - col) == abs(prevRow - row)) {
            return false;
        }
    }
    return true;
}

void Try(int row) {
    if (row == N) {
        solutionCount++;
        // In ra một lời giải
        cout << "Solution " << solutionCount << ":\n";
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i] == j)
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << endl;
        }
        cout << endl;
    } else {
        for (int col = 0; col < N; col++) {
            if (isSafe(row, col)) {
                board[row] = col;
                Try(row + 1);  // Thử đặt quân hậu tiếp theo
                // Quay lui: bỏ đi quân hậu khỏi hàng này để thử vị trí khác
                board[row] = -1;
            }
        }
    }
}

int main() {
    Try(0);  // Bắt đầu giải từ hàng đầu tiên
    cout << "Total solutions: " << solutionCount << endl;
    return 0;
}

Giải thích mã nguồn:

• board: Mảng board được sử dụng để lưu vị trí của các quân hậu trên bàn cờ. Mỗi phần tử của mảng lưu giá trị cột của quân hậu tại hàng tương ứng.
• isSafe: Hàm này kiểm tra liệu việc đặt một quân hậu tại vị trí (row, col) có an toàn hay không (không bị tấn công bởi quân hậu khác).
• Try: Hàm này thực hiện giải bài toán bằng cách thử đặt quân hậu vào từng hàng một và quay lui nếu cần.
• main: Hàm chính để bắt đầu quá trình tìm kiếm giải pháp.

Chạy chương trình này sẽ liệt kê tất cả các cách đặt 8 quân hậu trên bàn cờ 8×8 sao cho chúng không tấn công lẫn nhau và đếm tổng số lời giải.

Play with

Bạn có thể sử dụng công cụ sau để thử đặt quân hậu từng bước: Eight Queens Problem by Y. Daniel Liang (pearsoncmg.com)