Đối với bất kỳ ai chưa quen với câu đố 8 quân hậu, đó là vấn đề đặt tám quân hậu trên một bàn cờ tiêu chuẩn [8x8] sao cho không quân hậu nào ở vị trí có thể tấn công bất kỳ quân hậu nào khác. Bài đăng này sẽ có lời giải cho câu đố, vì vậy nếu bạn muốn tự mình giải nó, bây giờ là thời điểm tốt để ngừng đọc bài đăng này
Lần đầu tiên tôi biết đến sự tồn tại của câu đố này trong một quán rượu vào một buổi tối với một số người bạn. Một người bạn của tôi bắt đầu thử giải câu đố theo cách thủ công và tìm ra lời giải trong khoảng 10 phút. Điều này đã truyền cảm hứng cho tôi cố gắng giải quyết vấn đề bằng Python để xem liệu tôi có thể tìm ra giải pháp nhanh hơn không. Tôi mất khoảng 15 phút để giải câu đố bằng python, nhưng đã tìm thấy 92 lời giải [có 12 lời giải nếu bạn loại bỏ các lời giải liên quan đối xứng]
Đoạn mã gốc mà tôi viết để giải quyết vấn đề trông như thế này
from itertools import permutations, combinations text = input['How big is your chess board?'] n = int[text] x = range[1, n+1] def is_diagonal[point1, point2]: x1 = point1[0] y1 = point1[1] x2 = point2[0] y2 = point2[1] gradient = [y2-y1]/[x2-x1] if gradient == -1 or gradient == 1: return[True] else: return[False] list_of_permutations = [] for permuation in permutations[range[1, n+1]]: y = permuation all_permutations = list[zip[x,y]] list_of_permutations.append[all_permutations] for possible_solution in list_of_permutations: solutions = [] for piece1, piece2 in combinations[possible_solution, 2]: solutions.append[is_diagonal[piece1, piece2]] if True not in solutions: print[possible_solution]
Kể từ đó, tôi đã mở rộng nó để dễ hiểu hơn, trừu tượng hóa một số chức năng hữu ích và thêm một số mã để loại bỏ các giải pháp tương đương và giúp trực quan hóa các giải pháp, nhưng mã ở trên chứa logic chính chạy ở trung tâm của phương pháp mà tôi đã thực hiện. Phiên bản mở rộng của mã có thể được tìm thấy ở đây
Hãy chia nhỏ nó ra một chút để giải thích điều gì đang xảy ra
Chúng tôi biết rằng không có hai nữ hoàng nào có thể tấn công lẫn nhau. Điều này có nghĩa là phải có 1 nữ hoàng trên mỗi hàng. Tương tự, mỗi cột phải có 1 quân hậu. Theo cách tiếp cận này, chúng ta sẽ lấy 8 quân hậu, chỉ định chúng vào các hàng 1-8 và xác định mỗi cột phải ở cột nào để thỏa mãn tiêu chí câu đố. Vì có 8 quân hậu và 8 vị trí cột nên có 40.320 [nPr với n=r=8] cách sắp xếp 8 quân hậu trên một bàn cờ sao cho mỗi hàng có 1 quân hậu và mỗi cột có 1 quân hậu. Vì chúng ta đã biết không quân hậu nào sẽ tấn công quân hậu nào theo chiều ngang hoặc chiều dọc, nên tất cả những gì chúng ta cần làm là kiểm tra từng cách sắp xếp trong số 40.320 cách sắp xếp để xem có quân hậu nào đang đe dọa quân hậu nào theo đường chéo không. Quá trình này mất khoảng một giây để chạy tổng cộng [1. 06 giây trên máy tính để bàn 5 tuổi tầm trung của tôi] cho tất cả 40.320 cách sắp xếp quân hậu có thể và trả về 92 giải pháp phù hợp với tiêu chí không có quân hậu nào tấn công bất kỳ quân hậu nào khác. Một số trong số này sẽ liên quan đối xứng. Ví dụ: đây là 8 giải pháp từ bộ 92 có liên quan với nhau thông qua các phép quay 90 hoặc 180 độ; . e. chúng là hình ảnh phản chiếu ngang, dọc hoặc chéo của nhau]
Khi xóa các giải pháp có liên quan, chúng tôi chỉ còn lại 12 giải pháp duy nhất cho vỏ bảng 8x8, được hiển thị bên dưới