Why run -time of N-Queens using backtracking algorithm fluctuates?
Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-ideal behaviours. The running time of an experiment can vary based on lots of factors, and will be different from run-to-run.

You should repeat the experiment a number of times, and take the average running time of those runs to get a reliable reading. You could also compute the standard deviation of the running time, so you can get a good idea of whether the observed difference is statistically significant.

I implemented a straightforward backtracking approach to enumerate all solutions to the $n$-queens problem. The running time, taken as an average over 10,000 runs, was 0.045&nbsp;ms for $n=7$, and 0.22&nbsp;ms for $n=8$. This nicely fits with the fact that the number of (partial) solutions explored was 552 for $n=7$, and 2057 for $n=8$ (we have that $\frac{2057}{552}\times0.045\times\frac{8}{7}=0.19\approx 0.22$). So, based on my data, there is nothing that suggests $n=8$ is faster than $n=7$ -- if we want to enumerate all solutions.

Keep in mind that it is really hard to measure very low running times. There are other processes running at the same time, and how these are scheduled may affect the running time of your process. Your operating system may preempt your process for a while to run another process. For best accuracy, you should measure CPU time rather than "wall time", so that the time that your process is preempted is not taken into account.

If you're doing only a single run, the 0.773 or 0.492 (seconds?) you are measuring probably isn't the time required to do the backtracking (since that takes less than a millisecond), it's the time required to launch the process and load the executable from disk. The magnitude of the thing you're measuring is very small compared to the magnitude of the noise.

For completeness, here are my results for $n=1$ to $14$, giving the total number of valid partial solutions, the number of valid complete solutions (with $n$ queens), the first time (i.e., after how many partial solutions) a complete solution was found, average running time in ms, number of runs the average was taken over and the minimum/maximum number of timer ticks for a single run (to show how wide the spread in measured running times is).

n=1     total: 2        valid: 1        first: 2        0,0003ms        runs: 10000     min/max: 0/868
n=2     total: 3        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/55
n=3     total: 6        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/45
n=4     total: 17       valid: 2        first: 9        0,0009ms        runs: 10000     min/max: 1/96
n=5     total: 54       valid: 10       first: 6        0,0018ms        runs: 10000     min/max: 3/167
n=6     total: 153      valid: 4        first: 32       0,0071ms        runs: 10000     min/max: 15/286
n=7     total: 552      valid: 40       first: 10       0,0492ms        runs: 10000     min/max: 131/765
n=8     total: 2057     valid: 92       first: 114      0,2412ms        runs: 10000     min/max: 703/3107
n=9     total: 8394     valid: 352      first: 42       1,1385ms        runs: 2635      min/max: 3393/7416
n=10    total: 35539    valid: 724      first: 103      5,5285ms        runs: 543       min/max: 16869/29597
n=11    total: 166926   valid: 2680     first: 53       30,03 ms        runs: 100       min/max: 91033/116218
n=12    total: 856189   valid: 14200    first: 262      172,61ms        runs: 18        min/max: 543521/593573
n=13    total: 4674890  valid: 73712    first: 112      1037,2ms        runs: 10        min/max: 3379429/3490449
n=14    total: 27358553 valid: 365596   first: 1900     6736,1ms        runs: 10        min/max: 21845050/23117728


If we consider purely the time until finding the first solution, then the running time no longer is strictly increasing, but certain $n$'s are ``easier'' to solve in the sense that the backtracking strategy used happens to come across a valid solution earlier:

n=1     total: 2        0,0005ms        runs: 10000     min/max: 0/1199
n=2     total: 3        0,0005ms        runs: 10000     min/max: 0/50
n=3     total: 6        0,0004ms        runs: 10000     min/max: 0/50
n=4     total: 9        0,0004ms        runs: 10000     min/max: 0/56
n=5     total: 6        0,0004ms        runs: 10000     min/max: 0/44
n=6     total: 32       0,0016ms        runs: 10000     min/max: 2/64
n=7     total: 10       0,0006ms        runs: 10000     min/max: 1/54
n=8     total: 114      0,0089ms        runs: 10000     min/max: 21/232
n=9     total: 42       0,0033ms        runs: 10000     min/max: 7/199
n=10    total: 103      0,0107ms        runs: 10000     min/max: 29/140
n=11    total: 53       0,0052ms        runs: 10000     min/max: 14/77
n=12    total: 262      0,0533ms        runs: 10000     min/max: 138/2867
n=13    total: 112      0,0192ms        runs: 10000     min/max: 51/228
n=14    total: 1900     0,4925ms        runs: 6091      min/max: 1375/3820
n=15    total: 1360     0,3772ms        runs: 7953      min/max: 1072/3057
n=16    total: 10053    3,1402ms        runs: 956       min/max: 8997/17103
n=17    total: 5375     1,7544ms        runs: 1710      min/max: 5040/13332
n=18    total: 41300    14,813ms        runs: 203       min/max: 45021/60028
n=19    total: 2546     0,9637ms        runs: 3113      min/max: 2753/8341
n=20    total: 199636   83,5  ms        runs: 36        min/max: 264863/288246
n=21    total: 8563     3,9   ms        runs: 770       min/max: 11193/18734
n=22    total: 1737189  953,3 ms        runs: 10        min/max: 2900112/3477819
n=23    total: 25429    15,342ms        runs: 196       min/max: 41098/116394
n=24    total: 411609   251,833ms       runs: 12        min/max: 803905/970462
n=25    total: 48684    31,6211ms       runs: 95        min/max: 92880/133684


The total column reports the number of partial solutions considered before a valid complete solution is found (or the total number of partial solutions considered if there do not exist valid complete solutions). You can see that (for instance) when $n$ goes from 20 to 21 there is a large drop in number of solutions that need to be considered (and consequently a large drop in running time).

In this case, my backtracking algorithm (which uses the most obvious approach of starting at the top left, recursing, and moving the queen in each row from left to right), contrary to yours, takes longer to find a solution for $n=8$ than it does for $n=7$. However, the spread in running times (even though the algorithm is completely deterministic) is large: the fastest $n=8$ solution is more than twice as fast as the slowest $n=7$ solution.

It is difficult to quantify why a certain $n$ is more ``lucky'' than another, because this requires a deep understanding of the structure of the search space and how it interacts with a particular backtracking strategy.

One interesting fact is that if $n$ is odd, there always exists a solution placing a queen in the top left corner. This leads to the observation that the time to find the first solution for $2n+1$ is always much faster than that for $2n$, because the algorithm's guess (in the $2n+1$ case) for the first queen (top left corner) is always correct and the problem then reduces to solving a restricted version for the $2n$ case where no queens can be placed on the diagonal.