I am given this function which is used to help solve the n-queens problem and to

Question

 I am given this function which is used to help solve the n-queens problem and told to optimize it to be as efficient as possible. Currently, it runs at n^n runtime which is bad for really large input, but I think we could get it to maybe have a runtime of n!. How would I optimize this function? I think the problem lies in the fact that I am interating through a for loop that is 4 levels deep.    bool isAConflict( const Matrix< bool > & board ) {   uint n = board.numrows();    // row and col range over the entire board   for( uint row = 0; row < n; row++ )     for( uint col = 0; col < n; col++ )       // if row and col designate a queen's position, see if it       // conflicts with any other queen        // let tryrow and trycol range over the entire board, looking       // for a conflicting queen       for(uint tryrow = 0; tryrow < n; tryrow++ )         for( uint trycol = 0; trycol < n; trycol++ )         {           // if there's a queen at both row,col and tryrow,trycol           if( board.at(row, col) && board.at(tryrow, trycol) &&               // and it's not the same spot               !(row == tryrow && col == trycol ))           {             // first check if they're in the same column             if( col == trycol )               return false;             // now check if they're in the sam row             if( row == tryrow )               return false;             // now see if they're in the same "up" diagonal             if( n - col + row == n - trycol + tryrow )               return false;             // and finally the same down diag             if( row + col + 1 == tryrow + trycol + 1 )               return false;           }         }   // no two queens conflict   return true; } 

Explanation / Answer

import java.util.Arrays;
public class NQueens {
   static int[] result; // this array will store the result
   public boolean canPlace(int x2, int y2) {//// This function will check if queen can be placed (x2,y2), or we can
       // say that Can queen at x2 row is placed at y2 column.
       // for finding the column for x2 row, we will check all the columns for
       // all the rows till x2-1.
   for (int i = 0; i < x2; i++) {
           //result[i] == y2 => columns are same
           //|i - x2| == |result[i] - y2| => in diagonals.
           if ((result[i] == y2)
                   || (Math.abs(i - x2) == Math.abs(result[i] - y2))) {
               return false;
           }
       }
       return true;
   }
   public void placeQueens(int x, int size) {
       for (int i = 0; i < size; i++) {
           //check if queen at xth row can be placed at i-th column.
           if (canPlace(x, i)) {
               result[x] = i; // place the queen at this position.
               if (x == size - 1) {
                   System.out.println("Order of " + size + " queens"
                           + Arrays.toString(result));
               }
               placeQueens(x + 1, size);
           }
       }
   }
   public static void main(String[] args) {
       int n = 6;
       result = new int[n];
       NQueens i = new NQueens();
       i.placeQueens(0, n);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.