Why run -time of N-Queens using backtracking algorithm fluctuates?

Question

I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is 0ドル.773$, but for $N=8$, the run time is 0ドル.492$.

I think the run time should grow exponentially with the size of $N$. Why is the algorithm slower for 7ドル$ than for 8ドル$? This case also happens between 20ドル$ and 21ドル$ ,28ドル$ and 29ドル$. This is my pseudocode.

Function BACKTRACKING-SEARCH(csp)returns a solution,or failure return BACKTRACK({},csp) Function BACKTRACK(assignment, csp) returns a solution, or failure begin if assignment is complete then return assignment var = SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp) for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do if value is consistent with assignment then add {var = value} to assignment Result ←BACKTRACK(assignment,csp) If Result ≠ failure then return Result Remove {var=value} and inferences from assignment End if End for Return failure end

• Juho: How are SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES implemented? Their inner working will have a massive effect on performance.
• Cecelia: I implemented in default order none heuristics.

Answer 1

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 ms for $n=7$, and 0.22 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 2ドルn+1$ is always much faster than that for 2ドルn$, because the algorithm's guess (in the 2ドルn+1$ case) for the first queen (top left corner) is always correct and the problem then reduces to solving a restricted version for the 2ドルn$ case where no queens can be placed on the diagonal.

• gnasher729: How many attempts until the first solution would depend entirely on your algorithm. In your case, finding the first solution would likely be faster with n=9 or n=11 than n=8, the same behaviour that surprised OP, just at a different point (most likely your algorithm tries solutions in a different order).
• Tom van der Zanden: @gnasher729 I'm suspicious of the running times reported in the question. If they are getting a reading of 0.77 (presumably either seconds or milliseconds, the units aren't specified) for something that should only take 0.05ms, there might be something wrong.
• Discrete lizard: I think this question is not about enumeration, but just finding a single solution. Given that you also see strong monotone behaviour in the single solution finding part, I don't think that the experimental setup completely explains what is going on, so you may want to update your intro a bit.
• Tom van der Zanden: This post is the report.
• Juho: @ThuriyaThwin Some effort is required from your side as well. We are not a homework or report writing service.

Answer 2

The exponential running time of backtracking for the$N$-queens problem is an upper bound, which means that the algorithm may do better sometimes. If the algorithm is 'lucky' and tries good positions for the queens first, it can find a solution with doing less backtracking compared when trying bad positions first.

Whether the algorithm is lucky or not depends both on how the position for a new queen is chosen and on the input instance. Likely, your algorithm is lucky for $N=8$, but not so lucky for $N=7$.

• Cecelia: Could you explain me a little deep?I have to benchmark result and prove this condition in documentation.
• Discrete lizard: @ThuriyaThwin Probably, what is it that is unclear? Or what do you want to know in more detail?
• Cecelia: I want to describe the luckiness of algorithm in formal way because I have to argument that run time increases with size.Please explain me something like math or academic .
• Discrete lizard: @ThuriyaThwin Well, as your experiment shows, the running time does not monotonically increase with respect to N. I'm not sure why you want to have an argument for something that is false. As for the 'luckiness', that is essentially the number of times the backtracking algorithm has to backtrack until it gets a solution. This depends on both the selection strategy of your algorithm and the problem instance.
• gnasher729: @ThuriyaThwin You can obviously measure the time to find all solutions and find the average time, then you know if you're lucky or not. Find 100 solutions in 200 seconds -> average 2.0 seconds per solution. You still may find the first one in 0.01 seconds by luck. And I wonder what algorithm you are using where the time for finding the first N=8 solution is long enough to be measured.