Bàn luận về bài toán “8 hậu”

[real_time]

tư tưởng của thuật toán dùng hoán vị là bạn sẽ đặt 8 quân hậu đó lên bàn cờ 8x8 và tìm tất cả hoán vị của tất cả những vị trí của những quân hậu đó lên bàn cờ thế thoả mãn điều kiện ko ăn nhau là được t hôi. và như vậy liệt kê hết tất cả các trường hợp của bài toán là 8! với bàn cờ nxn thì cũng chỉ có n! nhanh hơn thử sai và quay lui!

[btkiet]

Ứng dụng hoán vị để giải bài toán tám hậu quả nhiên là một phương pháp hay nhưng không thể nhanh hơn quay lui đâu. Độ phức tạp của thuật toán hoán vị là n! còn của quay lui là n*n thôi.

[lovely]

Tiện cho mình hỏi "mã đi tuần " là gì vậy ?
Có ai có chương trình (đò họa) minh hoạ cho bàn cờ n*n ô không ?

[C'est la vie]

Một quân mã xuất phát từ một ô đi qua tất cả các ô còn lại mỗi ô 1 lần và trở lại vị trí ban đầu.

[The_Wall]

cái bài này ta dùng vét cạn là được hà. Có nhiều sách nói về bài này lắm

[btkiet]

Bài mã đi tuần vét cạn cũng được nhưng không hiệu quả lắm, nên đưa về đồ thị rồi tìm chu trình Hamilton là tốt nhất.

[lovely]

Bạn có thể nói cụ thể hơn được không ? Hamilton là gì vậy ?

[btkiet]

Không thể nói rỏ vấn đề trong khuôn khổ bài viết này được. Bạn đã học lý thuyết đồ thị chưa.
- Nếu chưa thì bạn sẽ khó mà hiểu được, hãy kiếm sách về lý thuyết đồ thị hoặc đọc trong cuốn Toán rời rạc cũng được.
- Nếu đã học rồi thì hãy xem lại. Chu trình Hamilton chính là chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ đi qua duy nhất một lần.

[lovely]

Ồ ! Nhưng tôi chưa học toán rời rạc , bạn có bản demo nào gửi cho tôi nhé

[del_gate]

Bạn nên tìm sách thì hơn vì đây toàn là thuật toán cơ bản thôi.
Sách nói về vấn đề này nhiều lắm.