Untitled

 avatar
unknown
csharp
15 days ago
2.6 kB
3
Indexable
using System;

public class BaiTap68
{
    const int KICH_THUOC_BAN_CO = 8;
    static int[] viTriQuanHau = new int[KICH_THUOC_BAN_CO]; // viTriQuanHau[cot] = hang
    static int demGiaiPhap = 0;

    static bool LaViTriAnToan(int hang, int cot)
    {
        // Kiểm tra các cột trước đó
        for (int cotTruoc = 0; cotTruoc < cot; cotTruoc++)
        {
            // Kiểm tra cùng hàng hoặc cùng đường chéo
            if (viTriQuanHau[cotTruoc] == hang ||
                Math.Abs(viTriQuanHau[cotTruoc] - hang) == Math.Abs(cotTruoc - cot))
            {
                return false;
            }
        }
        return true;
    }

    // Hàm in một giải pháp tìm được
    static void InGiaiPhap()
    {
        demGiaiPhap++;
        Console.WriteLine($"\nGiải pháp {demGiaiPhap}:");
        for (int i = 0; i < KICH_THUOC_BAN_CO; i++)
        {
            for (int j = 0; j < KICH_THUOC_BAN_CO; j++)
            {
                if (viTriQuanHau[j] == i)
                {
                    Console.Write(" Q "); // Quân hậu
                }
                else
                {
                    Console.Write(" . "); // Ô trống
                }
            }
            Console.WriteLine();
        }
    }

    // Hàm đệ quy để đặt quân hậu
    static void DatHau(int cot)
    {
        // Điều kiện dừng: Đã đặt hết quân hậu cho tất cả các cột
        if (cot == KICH_THUOC_BAN_CO)
        {
            InGiaiPhap();
            return;
        }

        // Thử đặt quân hậu vào từng hàng của cột hiện tại
        for (int hang = 0; hang < KICH_THUOC_BAN_CO; hang++)
        {
            if (LaViTriAnToan(hang, cot))
            {
                viTriQuanHau[cot] = hang; // Đặt quân hậu
                DatHau(cot + 1); // Gọi đệ quy cho cột tiếp theo
            }
        }
    }

    public static void Main(string[] args)
    {
        Console.OutputEncoding = System.Text.Encoding.UTF8;
        Console.InputEncoding = System.Text.Encoding.UTF8;

        Console.WriteLine("Bài toán 8 quân hậu bằng đệ quy");

        for (int i = 0; i < KICH_THUOC_BAN_CO; i++)
        {
            viTriQuanHau[i] = -1;
        }

        DatHau(0); // Bắt đầu đặt từ cột 0

        if (demGiaiPhap == 0)
        {
            Console.WriteLine("\nKhông tìm thấy giải pháp nào (Lỗi logic?).");
        }
        else
        {
             Console.WriteLine($"\nTổng cộng tìm thấy {demGiaiPhap} giải pháp.");
        }
    }
}
Editor is loading...
Leave a Comment