Thuật toán để giải quyết câu đố N Queens Domination

Question

Tôi đã giải quyết vấn đề N Queens chung hơn, nhưng bây giờ tôi đang tìm kiếm một thuật toán để giải quyết vấn đề N Queens Domination.

"Cho một n × board n, tìm số thống trị, đó là số lượng tối thiểu của các nữ hoàng (hoặc phần khác) cần thiết để tấn công hoặc chiếm mỗi vuông. Đối với hội đồng quản trị 8 × 8, của nữ hoàng số thống trị là 5. " - Wikipedia

Tôi đã tìm kiếm rộng rãi và không thể tìm thấy bất kỳ điều gì ngoài các tài liệu học thuật về vấn đề này, không có gì dễ hiểu từ xa.

Suy nghĩ đầu tiên của tôi là đặt một Nữ hoàng xuống và sau đó đặt Nữ hoàng tiếp theo ở nơi có thể tấn công hầu hết các ô vuông khác, v.v. Tuy nhiên, trong khi điều này có thể tạo ra một giải pháp, tôi không thể tìm ra một cách để đảm bảo rằng giải pháp đó là giải pháp tối thiểu.

Bất kỳ trợ giúp nào sẽ được đánh giá cao, cảm ơn.

Answer 1

Sử dụng thuật toán của bạn, bạn có thể tạo tất cả các kết hợp có thể và tối thiểu hóa từ đó. Gợi ý: Sử dụng đệ quy cho điều này và không xử lý các điều kiện tương tự (hoặc lưu vào bộ nhớ cache) như vị trí đối xứng, cùng thứ tự và cứ như vậy.

Answer 2

Sau đây là không hiệu quả, nhưng nó sẽ hoạt động.

Khôi phục sự cố dưới dạng sự cố lập trình số nguyên. Mỗi ô vuông trên bảng là 0 hoặc 1. Đối với bất kỳ ô nào, tổng của chính nó và tất cả các hình vuông tấn công phải chính xác 1. Và bạn muốn thu nhỏ tổng số tiền.

Answer 3

Với tinh thần của việc này là câu hỏi về bài tập về nhà, tôi sẽ không cung cấp giải pháp, mà là một loạt câu hỏi dẫn đến giải pháp. Sau đây là một cách để trả lời "bạn có thể thống trị bảng với n nữ hoàng?" Sau đó bạn có thể tìm số thống trị bằng cách thử n = 1, n = 2, ...

1) Bằng cách đặt một vị trí nữ hoàng 1 *, bạn có thể thống trị tất cả các vị trí còn lại mà nữ hoàng không đạt được bằng cách đặt (n - 1) queens trong (n - 1) vị trí được lựa chọn từ (2,3, ...)?

2) Nếu không, bạn có thể đặt nữ hoàng ở vị trí thứ 2 và sau đó thống trị tất cả các vị trí còn lại không đạt được bởi nữ hoàng 1 bằng cách đặt (n - 1) queens ở (n - 1) vị trí được chọn từ (3,4 , ...)?

3) vv ... tức là nơi nữ hoàng đầu tiên ở vị trí 3, sau đó vị trí thứ 4, vv

Lưu ý rằng giải pháp này là đệ quy - tại mỗi đệ quy, "vị trí còn lại để thêm một nữ hoàng" và "các vị trí chưa thể truy cập được bởi bất kỳ nữ hoàng" nào được chuyển thành các đối số. Khi "vị trí chưa được truy cập bởi bất kỳ nữ hoàng" nào trống, bạn đã tìm thấy giải pháp.

* sắp xếp tất cả các vị trí của bảng theo một cách nào đó, ví dụ từ trái sang phải, từ trên xuống dưới. Vì vậy, 64 vị trí trên một bảng 8x8 có thể được gọi chỉ bằng một chỉ mục (1..64).

Answer 4

int count; 

int safetyOfThisPosition(int col,int row,int *x) 

{ 

     int iterator; 
     for(iterator=0;iterator<col;iterator++) 
     { 
     if(row==x[iterator] || abs(col-iterator)==abs(row-x[iterator])) 
      return 0; 
     } 
     return 1; 
} 

void Nqueen(int col){ 

     int row,iterator; 
     static int x[N]; 
     for(row=0;row<N;row++) 
     { 
      if(safetyOfThisPosition(col,row,x)) 
      { 
       x[col]=row; 
       if(col==N-1) 
       { 
        for(iterator=0;iterator<=col;iterator++) 
       printf("%d ",x[iterator]); 
        printf("\n"); 
       } 
       else 
        Nqueen(col+1); 
      } 
     } 

    } 

int main(){ 

     Nqueen(0); 
     return 0; 
    }