CODEWITHSUNDEEP
algorithmmathpermutationn-queens
Freya
Freya

Reputation: 21

Is there a general term formula for 3 queens problem?

The specific question description is: Put 3 queens on a chessboard of M columns and N rows, how to determine the number of ways that no two of them are in attacking positions?

Note that M is not equals to N, and M/N are larger than a Integer in C language so that there is no way to solve this question using classical computer algorithm like DFS/BFS(for time and memory complexity considerations).

I guess this problem can be calculated by the mathematical method of permutation or combination, but I am not good at math, so, please help me.

Upvotes: 0

Views: 860

Answers (3)

xmcp
xmcp

Reputation: 3742

Yes.

Searching for keyword "3 queens" in OEIS gives us A047659, and in the Formula section, Vaclav Kotesovec wrote that:

In general, for m <= n, n >= 3, the number of ways to place 3 nonattacking queens on an m X n board is n^3/6*(m^3 - 3m^2 + 2m) - n^2/2*(3m^3 - 9m^2 + 6m) + n/6(2m^4 + 20m^3 - 77m^2 + 58m) - 1/24*(39m^4 - 82m^3 - 36m^2 + 88m) + 1/16*(2m - 4n + 1)(1 + (-1)^(m+1)) + 1/2(1 + abs(n - 2m + 3) - abs(n - 2m + 4))(1/24((n - 2m + 11)^4 - 42(n - 2m + 11)^3 + 656(n - 2m + 11)^2 - 4518(n - 2m + 11) + 11583) - 1/16(4m - 2n - 1)*(1 + (-1)^(n+1))) [Panos Louridas, idee & form 93/2007, pp. 2936-2938].

This formula can be manually confirmed on small Ns and Ms. A simple Python script for this purpose is shown below:

import fractions # to avoid floating error
m = fractions.Fraction(4)
n = fractions.Fraction(4)
assert m<=n
one = fractions.Fraction(1) 
ans = n**3/6*(m**3 - 3*m**2 + 2*m) - n**2/2*(3*m**3 - 9*m**2 + 6*m) + n/6*(2*m**4 + 20*m**3 - 77*m**2 + 58*m) - one/24*(39*m**4 - 82*m**3 - 36*m**2 + 88*m) + one/16*(2*m - 4*n + 1)*(1 + (-1)**(m+1)) + one/2*(1 + abs(n - 2*m + 3) - abs(n - 2*m + 4))*(one/24*((n - 2*m + 11)**4 - 42*(n - 2*m + 11)**3 + 656*(n - 2*m + 11)**2 - 4518*(n - 2*m + 11) + 11583) - one/16*(4*m - 2*n - 1)*(1 + (-1)**(n+1)))
print(ans)

Unfortunately, I failed to find the proof of this formula ([Panos Louridas, idee & form 93/2007, pp. 2936-2938], as Vaclav Kotesovec cited). The journal idee & form does not seem to be freely accessible. But due to the reputation of Vaclav Kotesovec (the author of Non-attacking chess pieces), I think we should trust this result.

Upvotes: 2

btilly
btilly

Reputation: 46417

The simple answer is inclusion/exclusion.

We start by counting the number of ways to place 3 queens in order. Which is just (n*m) * (n*m - 1) * (n*m - 2).

Now we have overcounted, because we don't want the count of the number of ways to place 3 queens with queens 1,2 attacking. Or queens 1,3. Or queens 2,3. But that is just the sum over rows, columns and diagonals of length l of l * (l-1) * (m*n-2).

But now we have undercounted, because if all 3 queens attack each other then we added them in the first step, subtracted 3x in the second step, and now we need to add them back 2x to get to counting those 0 times. Which is the sum over rows, columns and diagonals of length l of l * (l-1) * (l-2).

But this is the count of ways to place all of the queens in order. But given 3 queens on the board, there are 6 orders we could place them. So divide the whole answer by 6.

This can be turned into a program that is O(n+m) to run. Which should be fast enough for your purposes. If you were willing to do a bunch more analysis, we could actually produce a O(1) formula.

Upvotes: 0

Yuri Ginsburg
Yuri Ginsburg

Reputation: 2601

The field with coordinates (i, j) is vulnerable for the queen locаted at (qi , qj) if

    i == qi || j == qj || abs(i - j) == abs(qi - qj)

This boolean expression should be false for feasible coordinates of each queen. Finding three such fields should not be hard. One cаn try Monte Carlo method which has complexity o(M * N) in worst case.

Upvotes: -1

Related Questions