Too Many Pawns on a Chessboard

The main idea behind my code is the following observation:

Color the squares white and blue and consider them separately. Let's look at the blue.

Lemma: if you place a white pawn on a blue square, then all the blue squares above or at the two blue diagonals from the white pawn are also white.

Imgur

Proof: if one of the blue squares above had a black pawn, then it would attack the white pawns adjacent to it.

With this observation, we see that to count the number of ways to cover the blue squares white, we just have to draw a jagged line dividing the board into two pieces:

Imgur

(the 0 and 1 rows are there if there are no white pawns in that respective column) Note that we can represent this jagged line with an integer sequence of length 8, with consecutive elements have difference exactly one. In the above scenario, this sequence is $45456545$ Now we want to count the number of white pawns per sequence, so we need to enumerate all sequences. This can be done by first picking a start point of either $0, 2, 4, 6, 8$ then choosing either to go diagonal up or diagonal down by looping through all binary numbers $0000000\to 1111111$ and getting rid of ones that go over the edge.

Finally, after we find how many pawns per sequence, we plug them in an array holding the generating function for the number of ways to place $n$ white pawns, then multiply this with itself (to account for white and blue squares) and finding the coefficient of $x^{32}$ , corresponding to $32$ white pawns total.

My Java code (terminates in 14 ms):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

public static void main(String[] args){
    int[] gfCoef = new int[33]; // Generating Function Coefficients
    for(int i = 0; i < 5; i++){ // Starting positions of sequence
        for(int j = 0; j < 128; j++){ // Looping through 7-bit binary sequence
            boolean outofbounds = false; // Checks if sequence is out of bounds
            String bin = toBinaryString(j);
            int elem = 2*i;
            String seq = Integer.toString(elem);
            for(int k = 0; k < 7; k++){
                if(bin.charAt(k) == '1'){
                    elem++; // next term in sequence up one if meet "1"
                }
                else{
                    elem--; // next term in sequence down one if meet "0"
                }
                if(elem < 0 || elem > 9){ // Check if out of bounds
                    outofbounds = true;
                    break;
                }
                else{
                    seq += Integer.toString(elem);
                }
            }
            if(outofbounds == false){
// If sequence is valid calculate the 
//number of squares it encapsulates 
//and add it to the corresponding part 
//of the Generating function array
                gfCoef[countSquares(seq)]++; 
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < gfCoef.length; i++){ // Find the coefficient of x^32 in the generating function f(x) squared
        ans += gfCoef[i]*gfCoef[gfCoef.length - 1 - i];
    }
    System.out.println(ans);
}
public static String toBinaryString(int x){ // Changes integer to 7 bit binary string
    String output = "";
    for(int i = 6; i>= 0; i--){
        output += (int)Math.floor(x/Math.pow(2, i));
        x -= Math.pow(2, i)*Math.floor(x/Math.pow(2, i));
    }
    return output;
}
public static int countSquares(String str){ // Given  a sequence, find the total number of squares it encapsulates
    int output = 0;
    for(int i = 0; i < str.length(); i++){
        if(str.charAt(i) == '2' || str.charAt(i) == '3'){
            output++;
        }
        if(str.charAt(i) == '4' || str.charAt(i) == '5'){
            output+=2;
        }
        if(str.charAt(i) == '6' || str.charAt(i) == '7'){
            output+=3;
        }
        if(str.charAt(i) == '8' || str.charAt(i) == '9'){
            output+=4;
        }
    }
    return output;
} 

My python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

"""
solution of:
    https://brilliant.org/practice/trees-level-3-challenges/?p=3
"""

def find_all_configurations(board_width, board_height, black_max_num, white_max_num):
    """
    finds all configurations of given number of white and black pawns
    on a given chessboard such that no pawn attack another

    the element of a solutions at index 0 represents the upper left corner of the chessboard
    black pawns move down
    white pawns move up
    """
    assert board_width > 0
    assert board_height > 0
    assert black_max_num > 0
    assert white_max_num > 0
    empty_max_num = board_width*board_height-black_max_num-white_max_num
    assert empty_max_num >= 0

    sol_set = set()
    def check_pos_white(in_data):
        new_pos = len(in_data)
        res = True
        if (new_pos+1)%board_width != 0:
            tmp_pos = new_pos-board_width+1
            if tmp_pos >= 0 and in_data[tmp_pos] == 'B':
                res = False
        if res and (new_pos)%board_width != 0:
            tmp_pos = new_pos-board_width-1
            if tmp_pos >= 0 and in_data[tmp_pos] == 'B':
                res = False
        return res

    def inner(cur_data, black_left, white_left, empty_left):
        if black_left == 0 and white_left == 0 and empty_left == 0:
            sol_set.add(cur_data)
        else:
            if empty_left > 0:
                inner(cur_data+' ', black_left, white_left, empty_left-1)
            if black_left > 0:
                inner(cur_data+'B', black_left-1, white_left, empty_left)
            if white_left > 0 and check_pos_white(cur_data):
                inner(cur_data+'W', black_left, white_left-1, empty_left)
    inner('', black_max_num, white_max_num, empty_max_num)
    return sol_set

def sol_to_printable(sol_data, board_width):
    """
    splits given solution string into lines
    """
    assert len(sol_data)%board_width == 0
    res_str = ''
    for (pos, char) in enumerate(sol_data):
        res_str += char
        if (pos+1)%board_width == 0:
            res_str += '\n'
    return res_str

assert len(find_all_configurations(2, 2, 2, 2)) == 3
assert len(find_all_configurations(4, 4, 8, 8)) == 30

SOL_SET = find_all_configurations(8, 8, 32, 32)
for _ in SOL_SET:
    print(sol_to_printable(_, 8))

print(f"number of configurations: {len(SOL_SET)}")

I used DP Bitmask to solve this problem

In my code, there are 4 DP states. x and y represent position, z represents the number of white pawns left.

The DP calculate the number of way to put a white pawn and a black pawn on current position. If a white pawn had been placed on diagonally backward, then you should only calculate the number of way to put a white pawn.

My code in C++ : http://ideone.com/qlVEWQ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<cstdio>
#include<cstring>

int n;
int dp[1<<4][1<<4][1<<6][1<<10];

int f(int x, int y, int z, int state) {
    if (z < 0) return 0;
    if (y < 0) return f(x-1, n-1, z, state >> 1);
    if (x < 0) return (z == 0);

    int &ret = dp[x][y][z][state];
    if (ret != -1) return ret;

    ret = f(x, y-1, z-1, state | (1 << (y+1)));
    if ( ((state >> (y-1)) & 1) | ((state >> (y+1)) & 1) ) return ret;
    return ret += f(x, y-1, z, state);
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    printf("%d\n", f(n-1, n-1, (n*n) >> 1, 0));
    return 0;
}

Run in time complexity : $O( N^4 2^N )$