Subtask 1

Quay lui, thử mọi tổ hợp xếp quân vua.

Độ phức tạp: \(O(2^{N^2})\).

Subtask 2,3

Sử dụng quy hoạch động và mặt nạ bit AKA bitmask. Thay vì quy hoạch động 2 chiều theo bàn cờ, hay gì đó tương tự, thì ta sẽ xem xét các hàng xếp quân vua theo dãy nhị phân, với 1 là xếp vua và 0 là không. Ví dụ:

000010100

Thì ta có thể đặt một dãy bit khác sao cho không con vua nào tấn công nhau, ví dụ:

000010100
101000001

Đầu tiên ta quay lui và nhét tất cả các dãy bit thỏa mãn (không con vua nào trên dãy đó ăn nhau) vào một vector hay mảng, gọi mask số lượng dãy bit đó.

Xét dp[i][j][k] với \(i\) là hàng thứ \(i\), \(j\) là dãy bit thứ \(j\) sẽ được sử dụng, và \(k\) là tổng số quân vua được sử dụng. Ta có công thức truy hồi như sau:

for(int i=2;i<=n;++i)
for(int j=0;j