Optimización del algoritmo de seguimiento genérico para N Queens

Para mi solucionador de problemas de N Queens, actualmente estoy usando backtracking y estoy alcanzando un promedio de 7 ms en tiempo de ejecución. Sin embargo, estoy buscando optimizar aún más mi retroceso para que tenga una mejor complejidad de tiempo.

 public boolean solveQueen( int col) { 
         if(col == qColumn) {
             solveQueen(col +1);
         }
         if(col >= board.length) {  
             printBoard();
             System.out.println();
             return true; 

         }

         for(int i = 0; i < board.length; i++)

             if(notUnderAttack(i,col)) 
             {

                 placeQ(i,col);
                 solveQueen(col +1);

                 removeQ(i, col);  


             }

         return false;         
     }

As well from what I read, N queens backtracking has a time complexity of O(N!) but with my backtracking, I'm skipping a column since I'm placing a queen down first so shouldn't it be O(N!-1)?

Will appreciate any feedback that comes my way ^^