Number of ways to place kings on chess board

Question

You have an N x N chessboard and you wish to place N kings on it. Each row and column should contain exactly one king, and no two kings should attack each other (two kings attack each other if they are present in squares which share a corner).

The kings in the first K rows of the board have already been placed. You are given the positions of these kings as an array pos[ ]. pos[i] is the column in which the king in the ith row has already been placed. All indices are 0-indexed. In how many ways can the remaining kings be placed?

Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains N and K on the first line, followed by a line having K integers, denoting the array pos[ ] as described above.

Output:
Output the number of ways to place kings in the remaining rows satisfying the above conditions. Output all numbers modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 16
0 <= K <= N
0 <= pos_i < N
The kings specified in the input will be in different columns and not attack each other.

Sample Input:
5
4 1
2
3 0

5 2
1 3
4 4
1 3 0 2
6 1
2

Sample Output:
1
0
2
1
18

Explanation: For the first example, there is a king already placed at row 0 and column 2. The king in the second row must belong to column 0. The king in the third row must belong to column 3, and the last king must beong to column 1. Thus there is only 1 valid placement.

For the second example, there is no valid placement.

How should i approach this problem

Answer 1

The question is essentially asking us to count permutations of 1 2 ... N such that i and i+1 are not adjacent for 1 <= i <= N-1.

Additionally, we have a prefix constraint. We should count only those permutations which start with pos_1 pos_2 ... pos_k.

If it were not for the prefix constraint, you can find the answer in O(N) time using the formula from OEIS. That is if N is not too large. The number of digits in the answer grows as Θ(N log N), so multiplication and addition would incur additional overhead. Or you could compute the answer modulo some number. This question was asked in the Egyptian Olympiad in Informatics (2009).

With the prefix constraint, I have an O(N²) dynamic programming solution. However, since N is as small as 16, using a polynomial time algorithm is overkill. There exists an easier dynamic programming solution running in time O(2^NN²). Although this algorithm would probably take longer to code than the previous solution, its much faster to think of. The backtracking solution would, however, take somewhere between 20 to 100 hours (on an ordinary desktop/laptop) to run in the worst case. There are 2806878055610 solutions alone to visit for N = 16. In addition to that, there would probably be a heavy cost of visiting non-solution dead-ends.

O(2^NN²) Solution

This solution can be generalized to finding the number of Hamiltonian paths in a graph.

Our state would be a pair (S, i); where S is a subset of {1,2...N} and i is an element of S. Let the cardinality of S be M.

Define F(S,i) to be the number of ways to place the the elements 1, 2, ..., M in the positions specified in S; respecting the constraint that k and k+1 never appear together; and the element M being placed in position i.

The base case is F(P,pos_k) = 1 where P = {pos_1, pos_2 ... pos_k}. It is straightforward to compute F(S,i) for all S and i in time O(2^NN²).

The final answer is F([N],1) + F([N],2) + ... + F([N],N) where [N] = {1,2...N}.

C++ code follows. Bitmasks were used to represent subsets of {1,2...N}.

const int MAXN = 18;
long long DP[1 << MAXN][MAXN];

void solve() {
    int n, k;
    cin >> n >> k;
    
    int pmask = 0, p;
    for(int i = 0; i < k; i++){
        cin >> p;
        pmask |= (1<<p);
    }

    // base cases
    if(k > 0) {
        DP[pmask][p] = 1;
    }
    else {
        for(int i = 0; i < n; i++) 
            DP[1<<i][i] = 1;
    }

    long long ans = 0;
    for(int bitmask = pmask; bitmask < (1<<n); bitmask++) { 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if((bitmask & (1<<j)) or abs(i-j) == 1) 
                    continue;
                DP[bitmask | (1<<j)][j] += DP[bitmask][i]; 
            }
            if(bitmask == ((1<<n) - 1)) 
                ans += DP[bitmask][i];
        }
    }

    cout << ans << endl;
}

O(N²) Solution

This solution is pretty difficult to think of if you have not come across the idea before.

First, let's tackle the problem without the prefixes.

The idea is to 'build' all valid permutations by placing the elements 1, 2 .. N one by one.

Let's start with an illustration. Suppose we are building a permutation, of say, 1 2 .. 5. First, we place 1. After placing 1, we also insert a placeholder element to be filled in by later numbers. More precisely, each state is a class of permutations where the placeholder x is replaced by a non-empty sequence of elements.

Our permutation, after inserting 1, looks like one of the 3 cases:

• 1 x - 1 is the first element. The placeholder x would contain all the elements 2,3,4,5 in some order.
• x 1 - 1 is the last element.
• x 1 x - 1 is neither the first element or last element.

Next, we place 2. It has to belong to one of the placeholders in one of the previous 3 classes.

• Suppose it belongs to the only placeholder in 1 x. Since 2 cannot be adjacent to 1, after placing 2 we must insert another placeholder between them. This results in the state 1 x 2. Additionally, we need to account for the permutations when 2 isn't the last element. We also spawn a state 1 x 2 x.

• For x 1, we analogously create states 2 x 1 and x 2 x 1.

• For x 1 x, we have two choices of placeholders to place 2 in. Like the previous cases, we create states 2 x 1 x, x 2 x 1 x, x 1 x 2, x 1 x 2 x. But notice, for example, in x 2 x 1 x the last placeholder is different from the other two - in that 3 can occur in it without a need to create another barrier! We record this by using a different symbol for the placeholder. That is we use x 2 x 1 o and o 1 x 2 x states instead.

Suppose next, we are inserting 3 in x 2 x 1 o. If we place 3 in an x, like before, we have to create a barrier placeholder. But, we do have a choice between creating or omitting a placeholder in the direction opposite to the barrier placeholder. If we place 3 in an o placeholder, we have choices between creating or omitting placeholders in both directions.

Additionally, we must also 'promote' the x placeholders that are not used to o placeholders. This is because, the old x placeholders do not offer a constraint for the next element, 4, like they did for 3.

We can already start guessing the developing pattern. In the general case, while inserting i:

• First of all, we have to choose in which placeholder to place i.

• Next, suppose we place i in an x placeholder. We must build a barrier placeholder. And we have a choice whether to build a placeholder in the other direction.

• If we are using an o placeholder, we have choices to build additional placeholders in both directions. That is, a total of 4 choices.

• We must update the x placeholders we did not use, to o placeholders.

The final observation that turns this idea into an efficient algorithm is that we can bunch together permutation classes that have the same number of placed elements and the same number of x and o placeholders. This is because, for two different classes sharing all three of these parameters, the number of permutations they represent are equal.

To prove this claim rigorously, it is enough to observe that the classes we are enumerating are exhaustive and non-overlapping.

Prefixes

A little thought reveals that in the prefix problem, we just have to count permutations which begin with a certain element, (call this b); and some of the constraints between i and i+1 are not applicable anymore.

The second modification is easy to fix: If the constraint between i-1 and i are not applicable, then before inserting i, update all the x placeholders to o placeholders.

For the first modification, we should ensure that there is always a placeholder at the beginning until b is placed. While placing b we cheerfully place it into the beginning placeholder, and don't add any placeholder before it.

Implementation

Let DP[i][no][nx] be the number of ways to build the class where the first i elements have been placed, and there are no and nx placeholders of type o and x respectively. At any state, the number of x placeholders is between 0 and 2. So the state space is O(N^2). State transitions are constant time, exactly as described above.

O(N) solution for the problem without the prefix constraint

According to OEIS, A_n = (n+1)A_n-1 - (n-2)A_n-2 - (n-5)A_n-3 + (n-3)A_n-4; where A_n is the number of permutations where i and i+1 are never consecutive.

We can compute the sequence A_n in O(n). (That is, assuming we compute A_n modulo a reasonably small number.)

Here is a derivation of the formula:

Define auxiliary sequences:

• B_n = Number of permutations of 1 2 ... N such that exactly one of the N-1 adjacency constraint is violated.

• C_n = Number of permutations of 1 2 ... N such that only the adjacency constraint involving the element N is violated. That is N-1 and N would be adjacent to each other in these permutation; and all other adjacency constraints are satisfied.

We now look for recurrences for the sequences A, B and C.

Recurrence for A_n

Suppose we remove the element n from a valid permutation P, where i and i+1 are never adjacent. The resulting permutation Q of 1 .. n-1 must satisfy exactly one of the following two cases:

• No adjacent numbers from 1 ... n-1 are adjacent in Q. That is, Q is one of the permutations accounted for in A_n-1.

• Exactly one pair (i,i+1) appear consecutively in Q, and i+1 =/= n-1. That is, Q is a permutation from B_n-1 - C_n-1.

In the first case, element n can be inserted in exactly n - 2 positions. Two of the positions are blocked by the element n - 1. In the second case, there is only one choice for the position of n - between the consecutive elements.

We get the recurrence: A_n = (n - 2)A_n-1 + B_n-1 - C_n-1.

Recurrence for B_n

Let B_n,k be the number of permutations where k and k+1 occur consecutively. We can coalesce k and k+1 together to a single element, and consider a permutation Q of n-1 elements, preserving the relative ordering.

• If neither k-1 and k+2 (original labels) appear next to the coalesced (k,k+1) element, then Q contributes 2 permutations to B_n,k - they correspond to the arrangements k k+1 and k+1 k within the coalesced element. The number of such Q is A_n-1.

• If one of k-1 or k+2 appear next to the (k,k+1) element, then Q contributes 1 permutation. The number of such Q is B_n-1,k-1 + B_n-1,k.

• If both k-1 and k+2 appear next to the (k,k+1) element, then Q contributes 1 permutation. The number of such Q is B_n-2,k-1.

We have B_n,k = 2A_n-1 + B_n-1,k-1 + B_n-1,k + B_n-2,k-1. (Some terms vanish when k = 1 and k = n-1).

Summing over k, we get the recurrence: B_n = 2(n-1)A_n-1 + 2B_n-1 + B_n-2.

Recurrence for C_n

Well, C_n is just B_n,n-1. From the previous results, it follows that C_n = 2A_n-1 + C_n-1.

Putting it all together

We should be able to eliminate B and C to get a recurrence in A alone. It is left as an exercise. :-)