Trình mô phỏng N-Queens

Cách dùng

1. 1 Nhấn Run để đặt quân hậu lần lượt theo từng cột bằng thuật toán backtracking.
2. 2 Ô màu xanh dương là ô đang được thử; ô màu đỏ là ô xung đột với một quân hậu đã đặt.
3. 3 Khi một cột không còn hàng nào an toàn, quá trình tìm kiếm sẽ quay lui về cột trước đó.
4. 4 Dùng Shuffle để đổi kích thước bàn cờ khác, hoặc chạy từng bước để theo dõi quá trình tìm kiếm.

Vì sao dùng công cụ này

• Xem trực quan cách backtracking khám phá các hướng đi, gặp ngõ cụt và hoàn tác lựa chọn của nó.
• Hiểu rõ điều kiện an toàn: không có hai quân hậu nào chung hàng, chung cột hoặc chung đường chéo.
• Một ví dụ kinh điển về bài toán thỏa mãn ràng buộc (constraint satisfaction) và backtracking.
• Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

Câu hỏi thường gặp

Trình mô phỏng N-Queens là gì?

Trình mô phỏng N-Queens minh họa động quá trình tìm kiếm quay lui (backtracking) để đặt n quân hậu lên bàn cờ n×n sao cho không quân nào tấn công được quân khác. Thuật toán thử lần lượt từng hàng trong một cột, đánh dấu xung đột, đệ quy tiếp khi vị trí đặt an toàn, và quay lui khi một cột không còn hàng nào an toàn.

Tính năng

Ví dụ

N = 4

2 distinct solutions (N = 8 has 92)

Trường hợp sử dụng

1. 1

   Học thuật toán quay lui

   Xem cách kiểm tra ràng buộc và quay lui giúp cắt tỉa không gian tìm kiếm.

2. 2

   Bài toán thỏa mãn ràng buộc

   Hiểu một bài toán CSP kinh điển với các ràng buộc hàng/cột/đường chéo.

3. 3

   Đếm số lời giải

   Khám phá cách số lượng lời giải tăng theo N.

Tài liệu tham khảo

• Bài toán tám quân hậu — Wikipedia
• MIT OCW 6.006 — Nhập môn Thuật toán (CLRS) — MIT OpenCourseWare

Công cụ liên quan