Galloping Queens #4

I just go through every possible combination of $4$ positions on the board, check if they are non-attacking and count them.

 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

from itertools import *
def is_attacking( piece1 , piece2 ): 
   '''Checks if two galloping queens attack each other'''
    x , y , x1 , y1 = pice1 + piece2
    if x == x1 or y == y1:  #same row or column
        return True    
    if abs((x-x1)/float(y-y1)) == 1: #same diagonal
        return True    
    for a , b  in [(1,2),(1,-2),(-1,2),(-1,-2), 
                   (2,1),(2,-1),(-2,1),(-2,-1)]:
        if (x + a , y + b) == (x1 , y1): #checks fork situation
            return True
    return False

def is_valid( L ): 
 '''checks if a given list  of queens,"L" are non attacking'''
    for x,y in combinations(L,2):
        if is_attacking(x,y):
            return False
    return True

count = 0
for a,b,c,d in combinations(product(range(8),repeat=2),4):
    if is_valid((a,b,c,d)):
        count += 1
print count

First of all we define a safe function that takes a list of queens and checks if they are attacking each other. The function generates all the squares that are under attack by a queen $q_i$ and then checks if $q_{i+1}$ is standing on such a square. The following iteration it will add the squares from $q_{i+1}$ and check $q_{i+2}$ . Since all the moves are symmetric we don't have to check if $q_{i}$ is attacking $q_{i-1}$ since $q_{i}$ would already be under attack.

In this solution all positions are tested, even stacked queens but stacked queens always result in a attack.

The order of the queens doesn't matter but it's easier to double count and the remove duplicates. Since there are 4 queens we can arrange them in $4! = 24$ ways and thus divide by 24 at the end.

 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

import itertools

def safe(queens):
    attackPoints = [];

    for j in range(0, len(queens)-1):

        q = queens[j]
        x = q[0]
        y = q[1]

        for i in range(0,8):
            attackPoints.append( (i,y) )            # Along x
            attackPoints.append( (x,i) )            # Along y


        for i in range(1, min(7-x, 7-y)+1 ):
            attackPoints.append( (x+i, y+i) )   # Diagonal down right

        for i in range(1, min(7-x, y)+1 ):
            attackPoints.append( (x+i, y-i) )   # Diagonal up right         

        for i in range(1, min(x, 7-y)+1 ):
            attackPoints.append( (x-i, y+i) )   # Diagonal down left        

        for i in range(1, min(x, y)+1 ):
            attackPoints.append( (x-i, y-i) )   # Diagonal up left      


        attackPoints.append( (x-2,y+1) )        # Knight, These might be outside the board
        attackPoints.append( (x-2,y-1) )        # but it doesn't matter.

        attackPoints.append( (x+2,y+1) )
        attackPoints.append( (x+2,y-1) )

        attackPoints.append( (x+1,y+2) )
        attackPoints.append( (x-1,y+2) )

        attackPoints.append( (x+1,y-2) )
        attackPoints.append( (x-1,y-2) )

        #Here we check if q_j+1 is under attack
        #from any of q_0 ... q_j
        if( queens[j+1] in attackPoints ):
            return 0

    return 1

test = []
for x in range (0,8):
    for y in range (0,8):
        test.append( (x,y) )

safes = 0;
for element in itertools.product(test,test,test,test):
    if( safe(element) ):
        safes += 1

print (safes/24)

Awesome problem, thanks!