Bài toán N-Queens¶
Question
Theo luật chơi cờ vua, một quân hậu có thể tấn công bất kỳ quân cờ nào nằm trên cùng một hàng, cột hoặc đường chéo. Cho \(n\) quân hậu và một bàn cờ kích thước \(n \times n\), hãy tìm một cách sắp xếp sao cho không có hai quân hậu nào có thể tấn công lẫn nhau.
Như được hiển thị trong hình dưới đây, khi \(n = 4\), có hai lời giải có thể tìm thấy. Dưới góc độ của thuật toán quay lui, bàn cờ kích thước \(n \times n\) có \(n^2\) ô vuông, cung cấp tất cả các lựa chọn choices. Trong quá trình đặt từng quân hậu một, trạng thái của bàn cờ liên tục thay đổi, và bàn cờ tại mỗi thời điểm đại diện cho trạng thái state.
Hình dưới đây minh họa ba ràng buộc của bài toán này: nhiều quân hậu không thể nằm trên cùng một hàng, cùng một cột hoặc trên cùng một đường chéo. Đáng chú ý là đường chéo được chia thành hai loại: đường chéo chính \ và đường chéo phụ /.
Chiến lược đặt quân hậu theo từng hàng¶
Vì cả số lượng quân hậu và số lượng hàng trên bàn cờ đều là \(n\), chúng ta có thể dễ dàng rút ra kết luận: mỗi hàng của bàn cờ chỉ cho phép đặt một và chỉ một quân hậu.
Điều này có nghĩa là chúng ta có thể áp dụng chiến lược đặt từng hàng: bắt đầu từ hàng đầu tiên, đặt một quân hậu ở mỗi hàng cho đến khi hoàn thành hàng cuối cùng.
Hình dưới đây hiển thị quá trình đặt từng hàng cho bài toán 4 quân hậu. Do giới hạn về không gian, hình vẽ chỉ triển khai một nhánh tìm kiếm của hàng đầu tiên, và tất cả các phương án vi phạm ràng buộc cột hoặc đường chéo đều bị cắt tỉa.
Về mặt bản chất, chiến lược đặt quân hậu theo từng hàng đóng vai trò như một phép cắt tỉa, vì nó tránh được tất cả các nhánh tìm kiếm mà ở đó nhiều quân hậu xuất hiện trên cùng một hàng.
Cắt tỉa cột và đường chéo¶
Để đáp ứng ràng buộc về cột, chúng ta có thể sử dụng một mảng boolean cols có độ dài \(n\) để ghi lại xem mỗi cột đã có quân hậu hay chưa. Trước mỗi quyết định đặt quân, chúng ta sử dụng cols để cắt tỉa các cột đã có quân hậu, và cập nhật động trạng thái của cols trong quá trình quay lui.
Tip
Lưu ý rằng gốc của ma trận nằm ở góc trên bên trái, nơi chỉ số hàng tăng dần từ trên xuống dưới, và chỉ số cột tăng dần từ trái qua phải.
Vậy làm thế nào để xử lý các ràng buộc đường chéo? Xét một ô vuông trên bàn cờ có chỉ số hàng và cột là \((row, col)\). Nếu chúng ta chọn một đường chéo chính cụ thể trong ma trận, chúng ta sẽ thấy rằng tất cả các ô vuông trên đường chéo đó đều có cùng hiệu số giữa chỉ số hàng và cột, nghĩa là hiệu \(row - col\) là một hằng số đối với mọi ô vuông trên cùng một đường chéo chính.
Nói cách khác, nếu hai ô vuông thỏa mãn \(row_1 - col_1 = row_2 - col_2\), chúng chắc chắn nằm trên cùng một đường chéo chính. Sử dụng quy luật này, chúng ta có thể dùng mảng diags1 như hình dưới đây để ghi lại xem có quân hậu nào trên mỗi đường chéo chính hay không.
Tương tự, đối với tất cả các ô vuông trên một đường chéo phụ, tổng \(row + col\) là một hằng số. Chúng ta cũng có thể sử dụng mảng diags2 theo cách tương tự để xử lý các ràng buộc đường chéo phụ.
Cài đặt mã nguồn¶
Lưu ý rằng trong một ma trận vuông \(n \times n\), phạm vi của hiệu \(row - col\) là \([-n + 1, n - 1]\), và phạm vi của tổng \(row + col\) là \([0, 2n - 2]\). Do đó, số lượng cả đường chéo chính và đường chéo phụ đều là \(2n - 1\), nghĩa là chiều dài của cả hai mảng diags1 và diags2 là \(2n - 1\).
Đặt \(n\) quân hậu theo từng hàng, xem xét ràng buộc cột, từ hàng đầu tiên đến hàng cuối cùng sẽ có lần lượt \(n\), \(n-1\), \(\dots\), \(2\), \(1\) lựa chọn, sử dụng thời gian \(O(n!)\). Khi ghi lại lời giải, cần sao chép ma trận state và thêm vào res, thao tác sao chép này mất thời gian \(O(n^2)\). Do đó, độ phức tạp thời gian tổng thể là \(O(n! \cdot n^2)\). Trên thực tế, việc cắt tỉa dựa trên các ràng buộc đường chéo cũng có thể làm giảm đáng kể không gian tìm kiếm, vì vậy hiệu suất tìm kiếm thực tế thường tốt hơn nhiều so với độ phức tạp thời gian nêu trên.
Mảng state sử dụng không gian \(O(n^2)\), và các mảng cols, diags1, cùng diags2 mỗi mảng sử dụng không gian \(O(n)\). Độ sâu đệ quy tối đa là \(n\), sử dụng không gian ngăn xếp (stack frame) \(O(n)\). Do đó, độ phức tạp không gian là \(O(n^2)\).