Thuật toán 8 quân hậu trong C#

Thuật toán 8 quân hậu là một bài toán nổi tiếng trong lĩnh vực trí tuệ nhân tạo và tính toán. Với một bàn cờ có kích thước 8×8, ta cần đặt 8 quân hậu trên bàn cờ sao cho không có quân hậu nào có thể tấn công được quân hậu khác.

Dưới đây là một ví dụ về cách triển khai thuật toán 8 quân hậu bằng ngôn ngữ lập trình C#:

using System;

class QueensProblem
{
    const int BOARD_SIZE = 8;
    static bool[,] board = new bool[BOARD_SIZE, BOARD_SIZE];

    static void Main()
    {
        Solve(0);
    }

    static void Solve(int row)
    {
        if (row == BOARD_SIZE)
        {
            PrintBoard();
            return;
        }

        for (int col = 0; col < BOARD_SIZE; col++)
        {
            if (IsValidMove(row, col))
            {
                board[row, col] = true;
                Solve(row + 1);
                board[row, col] = false;
            }
        }
    }

    static bool IsValidMove(int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (board[i, col])
                return false;

            int colDistance = Math.Abs(col - i);
            if (colDistance == 0) // same column
                return false;

            int rowDistance = row - i;
            if (col - colDistance >= 0 && board[i, col - colDistance])
                return false;

            if (col + colDistance < BOARD_SIZE && board[i, col + colDistance])
                return false;
        }

        return true;
    }

    static void PrintBoard()
    {
        for (int i = 0; i < BOARD_SIZE; i++)
        {
            for (int j = 0; j < BOARD_SIZE; j++)
            {
                Console.Write(board[i, j] ? "Q " : "- ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}

Ở đây, chúng ta sử dụng một ma trận boolean để đại diện cho bàn cờ, với giá trị true ở mỗi ô tương ứng với quân hậu. Hàm Solve được đệ quy để thử đặt quân hậu ở từng hàng trên bàn cờ. Mỗi lần thử đặt quân hậu, chúng ta kiểm tra xem nó có bị tấn công bởi các quân hậu khác hay không bằng cách sử dụng hàm IsValidMove. Nếu việc đặt quân hậu ở hàng hiện tại thành công, chúng ta tiếp tục đệ quy đến hàng tiếp theo. Nếu tất cả các hàng đã được đặt quân hậu, chúng ta in ra bàn cờ bằng cách sử dụng hàm PrintBoard.

Hàm IsValidMove được sử dụng để kiểm tra xem quân hậu có thể được đặt ở vị trí (row, col) trên bàn cờ hay không. Nó kiểm tra các quân hậu đã được đặt trước đó (nằm ở các hàng từ 0 đến row-1) và kiểm tra xem chúng có tấn công được quân hậu ở vị trí (row, col) không. Nếu không có quân hậu nào có thể tấn công được quân hậu ở vị trí này, hàm trả về true, ngược lại trả về false.

Hàm PrintBoard được sử dụng để in ra bàn cờ sau khi tìm được một cách đặt quân hậu hợp lệ. Nó duyệt qua các ô trên bàn cờ và in ra kí hiệu “Q” ở các ô có quân hậu và in ra “-” ở các ô còn lại.

Với cách triển khai này, chương trình sẽ tìm tất cả các cách đặt 8 quân hậu hợp lệ trên bàn cờ và in ra kết quả trên màn hình. Tuy nhiên, với kích thước bàn cờ lớn hơn, thuật toán này sẽ trở nên chậm do phải thử nhiều cách đặt quân hậu. Để tối ưu hóa thuật toán, có thể sử dụng các phương pháp như “backtracking” hoặc “pruning” để loại bỏ các trường hợp không cần thiết và giảm thiểu số lượng trường hợp phải thử.