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.

CodePudding user response：

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.

CodePudding user response：

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.