Bài toán 8 hậu (Đề thi Tin học trẻ)

H . . . . . . .
. . H . . . . .
. . . . H . . .
. . . . . . H .
. H . . . . . .
. . . H . . . .
. . . . . H . .
. . . . H . . .

. H . . . . . .
. . . H . . . .
H . . . . . . .
. . . . H . . .
. . H . . . . .
. . . . . H . .
. . . H . . . .
. H . . . . . .

. . . H . . . .
H . . . . . . .
. . H . . . . .
. . . . . H . .
. H . . . . . .
. . . . H . . .
. . . . . . H .
. . H . . . . .

. . H . . . . .
. H . . . . . .
. . . H . . . .
H . . . . . . .
. . . . H . . .
. . H . . . . .
. . . . . H . .
. H . . . . . .

def is_safe(board, row, col, n):
    """
    Hàm kiểm tra xem có thể đặt quân Hậu vào vị trí (row, col) trên bàn cờ vua hay không
    Args:
        - board (list): Bàn cờ vua (ma trận 2 chiều)
        - row (int): Dòng của vị trí cần kiểm tra
        - col (int): Cột của vị trí cần kiểm tra
        - n (int): Kích thước của bàn cờ vua (n x n)

    Returns:
        - bool: True nếu có thể đặt quân Hậu vào vị trí (row, col), False nếu không
    """
    # Kiểm tra cột trên dòng hiện tại
    for i in range(row):
        if board[i][col] == 1:
            return False

    # Kiểm tra đường chéo chính (trên bên trái)
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1

    # Kiểm tra đường chéo phụ (trên bên phải)
    i, j = row, col
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1

    return True

def solve_n_queens(board, row, n, result):
    """
    Hàm giải bài toán 8 quân Hậu bằng thuật toán quay lui
    Args:
        - board (list): Bàn cờ vua (ma trận 2 chiều)
        - row (int): Dòng hiện tại cần đặt quân Hậu
        - n (int): Kích thước của bàn cờ vua (n x n)
        - result (list): Danh sách chứa tất cả các cách sắp xếp đúng 8 quân Hậu

    Returns:
        None
    """
    if row == n:
        # Nếu đã đặt được 8 quân Hậu, thêm bàn cờ vua vào kết quả
        result.append([row[:] for row in board])
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = 1
            solve_n_queens(board, row + 1, n, result)
            board[row][col] = 0

def solve_n_queens_wrapper(n):
    """
    Hàm gọi giải bài toán 8 quân Hậu
    Args:
        - n (int): Kích thước của bàn cờ vua (n x n)

    Returns:
        - list: Danh sách chứa tất cả các cách sắp xế
        - đúng 8 quân Hậu trên bàn cờ vua
    """
    board = [[0 for _ in range(n)] for _ in range(n)]
    result = []
    solve_n_queens(board, 0, n, result)
    return result

# Test với bàn cờ vua 8x8
n = 8
solutions = solve_n_queens_wrapper(n)

# In tất cả các cách sắp xếp đúng 8 quân Hậu trên bàn cờ vua
print(f"Tổng cộng có {len(solutions)} cách sắp xếp đúng 8 quân Hậu trên bàn cờ vua {n}x{n}:")
for idx, solution in enumerate(solutions):
    print(f"Cách {idx + 1}:")
    for row in solution:
        print(row)
    print("\n")

#include <iostream>
#include <vector>

using namespace std;

void solveNQueens(vector<vector<int>>& board, int row, int n, vector<vector<vector<int>>>& solutions) {
    if (row == n) {
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < n; col++) {
        if (board[row][col] == 0) {
            board[row][col] = 1;

            for (int i = row + 1; i < n; i++) {
                board[i][col] = -1; // Đánh dấu các ô cùng cột với quân hậu đã đặt
                if (col - (i - row) >= 0) {
                    board[i][col - (i - row)] = -1; // Đánh dấu các ô trên đường chéo trái trên
                }
                if (col + (i - row) < n) {
                    board[i][col + (i - row)] = -1; // Đánh dấu các ô trên đường chéo phải trên
                }
            }

            solveNQueens(board, row + 1, n, solutions); // Đệ quy để đặt các quân hậu tiếp theo

            for (int i = row + 1; i < n; i++) {
                board[i][col] = 0; // Xóa đánh dấu các ô cùng cột với quân hậu đã đặt
                if (col - (i - row) >= 0) {
                    board[i][col - (i - row)] = 0; // Xóa đánh dấu các ô trên đường chéo trái trên
                }
                if (col + (i - row) < n) {
                    board[i][col + (i - row)] = 0; // Xóa đánh dấu các ô trên đường chéo phải trên
                }
            }

            board[row][col] = 0; // Quay lại trạng thái trước đó
        }
    }
}

vector<vector<vector<int>>> solveNQueens(int n) {
    vector<vector<int>> board(n, vector<int>(n, 0));
    vector<vector<vector<int>>> solutions;
    solveNQueens(board, 0, n, solutions);
    return solutions;
}

int main() {
    int n = 8;
    vector<vector<vector<int>>> solutions = solveNQueens(n);

    cout << "Tong cong co " << solutions.size() << " cach sap xep dung 8 quan Hau tren ban co vua " << n << "x" << n << ":\n";
    for (int idx = 0; idx < solutions.size(); idx++) {
        cout << "Cach " << idx + 1 << ":\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (solutions[idx][i][j] == 1) {
                    cout << "H ";
                } else {
                    cout << ". ";
                }
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}