Algorithm to solve the N Queens Domination puzzle
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.
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.
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... ie 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).
The following is not efficient, but it will work.
Restate the problem as a integer programming problem. Every square on the board is either 0 or 1. For any square the sum of itself and all the attacking squares should be exactly 1. And you want to minimize the total sum.
链接地址: http://www.djcxy.com/p/57380.html上一篇: Android：如何启用/禁用按钮点击选项菜单项？
下一篇: 解决N皇后控制拼图的算法