0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How are SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES implemented? Their inner working will have a massive effect on performance. $\endgroup$ – Juho May 22 at 14:41
  • $\begingroup$ I implemented in default order none heuristics. $\endgroup$ – Thuriya Thwin May 22 at 14:43
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – gnasher729 May 22 at 8:34
  • $\begingroup$ @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. $\endgroup$ – Tom van der Zanden May 22 at 9:14
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard May 22 at 12:44
  • 1
    $\begingroup$ This post is the report. $\endgroup$ – Tom van der Zanden May 22 at 14:18
  • 2
    $\begingroup$ @ThuriyaThwin Some effort is required from your side as well. We are not a homework or report writing service. $\endgroup$ – Juho May 22 at 14:39
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you explain me a little deep?I have to benchmark result and prove this condition in documentation. $\endgroup$ – Thuriya Thwin May 22 at 6:46
  • $\begingroup$ @ThuriyaThwin Probably, what is it that is unclear? Or what do you want to know in more detail? $\endgroup$ – Discrete lizard May 22 at 6:52
  • $\begingroup$ 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 . $\endgroup$ – Thuriya Thwin May 22 at 6:57
  • $\begingroup$ @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. $\endgroup$ – Discrete lizard May 22 at 7:35
  • $\begingroup$ @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. $\endgroup$ – gnasher729 May 22 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.