CODEWITHSUNDEEP
algorithmpuzzlechess
Michael Robinson
Michael Robinson

Reputation: 2127

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.

Upvotes: 8

Views: 4303

Answers (4)

Jijo Varghese
Jijo Varghese

Reputation: 69

int count;

int safetyOfThisPosition(int col,int row,int *x)

{

       int iterator;
       for(iterator=0;iterator<col;iterator++)
       {
        if(row==x[iterator] || abs(col-iterator)==abs(row-x[iterator]))
           return 0;
       }
       return 1;
}

void Nqueen(int col){

       int row,iterator;
       static int x[N];  
       for(row=0;row<N;row++)  
       {
           if(safetyOfThisPosition(col,row,x))
           {
               x[col]=row;
               if(col==N-1)
               {
                   for(iterator=0;iterator<=col;iterator++)
               printf("%d  ",x[iterator]);
                   printf("\n");
               }
               else
                   Nqueen(col+1);
           }
       }

   }

int main(){

       Nqueen(0);
       return 0;
   }

Upvotes: 0

gcbenison
gcbenison

Reputation: 11963

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).

Upvotes: 1

wye.bee
wye.bee

Reputation: 716

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.

Upvotes: 0

mishadoff
mishadoff

Reputation: 10789

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.

Upvotes: 3

Related Questions