Re: Solving sudoku using SQL

=?UTF-8?B?SmFuIFVyYmHFhHNraQ==?= <wulczer(at)wulczer(dot)org> writes:
> On 08/12/10 21:18, Tom Lane wrote:
>> Hmmm ... "runs forever" is a bit scary.

> With SA you start with a temperature that's linearily dependant on the
> size of the query, and back off exponentially. Each step means work tha
> also depends on the size of the query, so big queries can mean expensive
> steps. With q=0.9 and initial temperature=<very-big> it takes too much
> time to plan.

> The good thing is that it's trivial to implement a hard cut-off value,
> which will stop annealing after a fixed number of steps (regardless of
> the current temperature) that would serve as a safety valve.

Well, let's wait and see whether experience says we need that. A
hard-wired cutoff risks returning a pretty bad plan, and we have no
experience yet with how fail-soft SA is.

Something that might be more useful is an escape that quits as soon as
the best plan's estimated cost is less than something-or-other. There's
no point in expending more planner time to improve the plan than you can
hope to recoup at execution.

regards, tom lane