Timing out randomized algorithm

Question

I have a randomized recursive backtracking algorithm to generate Sudoku puzzles (see here). It works fast enough on average, but the worst-case runtime is unacceptably slow. Here is a histogram of the runtime in milliseconds for 100 trials (the "More" is about 200,000 ms!):

I would like to improve the algorithm by simply timing it out after t ms, and restarting with a new random seed. To prevent this from repeating infinitely, I would either stop after n tries or increase t after each failed try. If t is much larger than the median, there's a good chance of getting a much faster run on a subsequent try.

Questions:

1. How can I adjust the timeout period t for different processors? Is there a fast, reliable way to benchmark processor performance prior to each run? Alternatively, should I adapt to the processor over several runs, for instance using the mean runtime of all previous runs? I am running this on Android, if that's relevant.
2. Is there a better strategy entirely to avoid the long tail in the distribution of the runtimes?

Answer 1

Since your algorithm is recurisve, why not establish a maximum recursion depth? If the particular random seed leads to a recursion depth that you have empirically established to be high enough that you will hit the long tail, abort at that point.

By visual approximation, it looks like after 4500ms you will not get significant returns on your investment for the given seed. Rerun that benchmark also tracking recursion depth, and see what that number is. I would run more than 100 samples, though.

That solution is CPU speed independent.

Answer 2

1. Yes there is, it is called confidence interval. By running the algorithm several time in pre-processing (or on the fly), you can determine with x% confidence (where x is a parameter) what is the interval where the median of running time lays in.
   You can reduce the interval size by decreasing x or increasing the number of times the algorithm runs.
   
   Of course if you cannot really run the algorithm itself, you can try to benchmark it on some machine and find the confidence interval (let it be I), and create some function f(I,s) that given a timing of a different algorithm (the timing of it is s) on a different machine (M), predicts what should be the interval for the machine M.
   finding s is done in a similar manner - using confidence interval.

2. Your approach seems fine, I'd probably do the same - I will first set up a small factor, and increase it after each failing attempt. Note that this is somehow similar to the congestion control in the TCP protocol (from the field of networks) to find the accepted rate of transfer of packages over the net.