CareerCup

Complex problem, backtracking is the algorithm technique that needs to be used though. Modifications to the solution of the standard problem should work.

Correct me if I am wrong but is this even possible to achieve. I tried placing 2 queens on 2X2 but no equilibrium, I tried placing 3 queens on 3X3 board still no equilibrium, I tried few other combinations where M was less than 15 for a MXM board but no equilibrium. If someone understands this problem correctly please present an example. Thanks!

Isnt it like the safe zone will change depending on M?

This is technically not possible or else I got it totally wrong. Because in a two dimensional matrix a single Queen at least will cover 1 full row and 1 full column. After that there will not be any single cell whose row or column does not intersect with either the first Queens row or column.
So two Queens can not be placed in such way in any chase board.

This is not possible to do. Lets say for starters we are not placing the queens but only the castles which means that m castles are placed such that each castle occupies a row in mxm matrix. Now if you take (i,j) as one co-ordinate, because of the restrictions in placing them these no i and j value are equal for any two of the castles if they are they either fall in the same row or in same column. This would only mean that the (i,j) values of all these castles have to increase simultaneously, which puts them all on a diagonal and now if these castles were given the powers of bishops (now they are queens) they end up being in the attack zones of each other. Irrespective of the knight powers you can't place m queens on mxm board

Not possible. However it can be achieved if special queen does not have the power of knight but in that case too M should be greater than 3 i.e M>3

This problem is a variant of a long-standing math problem known as the "N-Queens problem." This version in which the queens also can move like a knight is sometimes called "superqueens." The problem, in general, is computationally very complex and requires just a lot of searching and iterating; there isn't any one best way to do it and therefore a good answer is one that's efficient in CPU time.

I found a discussion of the general problem at a Web site by Jeff Somers (I'm not allowed to include the URL here). A couple of noteworthy comments I found there:
{
There is no quick and easy way to calculate the total number of N queen solutions for an N x N board.
}
and

{
The backtracking algorithm used to solve this problem
We place a queen in the top row, then note the column and diagonals it occupies. We then place a queen in the next row down, taking care not to place it in the same column or diagonal. We then keep track of the occupied columns and diagonals and move on to the next row. If no position is open in the next row, we back track to the previous row and move the queen over to the next available spot in its row and the process starts over again.
}

Got that? It's an iterative, row-by-row search of possible solutions, terminating each branch when it gets stuck, or when a solution is found.

Is such a search too slow? Our problem states that we only need to search up to a 14x14 board. If we place each queen on a different row, and each queen must be in a column not already used, then an upper bound on the number of arrangements is 14! = over 81 billion. But each queen actually has fewer legal spots than that since it can't be within 2 columns of the queens in the 2 rows above it; therefore the number of choices to search is bounded (I'm being approximate since it gets more complicated when some queens are near an edge) by 14x11x8x8x8x8x8! = 25.4 billion. This is not an optimal solution but it indicates that such a search is doable on any current-generation PC. According to Somers (above), the largest board for which the regular n-queens problem had been solved at his time of writing was 23x23.


You could do such a search either with an iterative loop, or a recursion formula. Since the maximum depth of recursion is only 14 levels, there's no risk of a stack overflow.

Permutation and then remove other illegal solutions

i) iterate over all possible placement spots for a queen, placing one at each possible spot at each iteration
ii) delete all spots she can go to from set of possible placement spots
iii) place another queen
iv) and so on until the map is filled
v) this continues until the outer loop (which runs over the entire board) finishes

From considerations of symmetry we only really have to do about half the board on the outermost iteration (above and including the main "diagonal").

There should be other possible optimizations. Either way, it's a problem that demands an expensive solution. Not sure if there is an approach better than brute force.