Menu
I have solved the more generic N Queens problem, but now I am looking for an algorithm to solve the N Queens Domination problem.
"Given an n×n board, find the domination number, which is the minimum number of queens (or other pieces) needed to attack or occupy every square. For the 8×8 board, the queen's domination number is 5." - Wikipedia
I have searched extensively and cannot find anything but scholarly papers on this problem, nothing remotely understandable.
My first thoughts are to just place a Queen down and then place the next Queen in the place that can attack the most other squares, and so on. However, while this may generate a solution, I cannot figure out a way to guarantee that that solution is the minimal solution.
Any help would be appreciated, thanks.
203
Abstract--In this paper a Meta-heuristic approach for solving the N-Queens Problem is introduced to find the best possible solution in a reasonable amount of time. Genetic Algorithm is used with a novel fitness function as the Meta-heuristic.
N-Queens Problem. N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no queens attack each other by being in the same row, column or diagonal. It can be seen that for n =1, the problem has a trivial solution, and no solution exists for n =2 and n =3.
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century.
Using your algorithm, you can generate all possible combinations and take minimum from it. Hints: Use recursion for this and don't process similar conditions (or cache it) like symmetric placement, the same order and so on.
64
In the spirit of this being a homework question, I won't provide a solution, but rather a series of questions that lead to a solution. The following is a way to answer "can you dominate the board with n queens?" You can then find the domination number by testing n=1, n=2, ...
1) By placing a queen in position 1*, can you then dominate all remaining positions not reached by queen 1 by placing (n - 1) queens in (n - 1) positions chosen from (2,3,...)?
2) If not, can you place a queen in position 2, and then dominate all remaining positions not reached by queen 1 by placing (n - 1) queens in (n - 1) positions chosen from (3,4,...)?
3) an so on... i.e. place first queen in position 3, then position 4, etc.
Note that this solution is recursive - at each recursion, "remaining positions to add a queen" and "positions not yet reachable by any queen" are passed as arguments. When "positions not yet reachable by any queen" is empty, you've found a solution.
* order all the board positions in some way, for instance left to right, top to bottom. So that the 64 positions on an 8x8 board can be referred to just by an index (1..64).
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
