[rules-users] Why is solving a partial puzzle much slower than generating one from scratch?

[Geoffrey De Smet]

Op 01-02-12 15:27, Geoffrey De Smet schreef:
>
> Op 01-02-12 08:37, aitchnyu schreef:
>> Sorry if I called it by a misleading name (3x3) . It means a regular sudoku
>> like http://www.sudoku-solutions.com/ .
>>
>> And I hacked on NQueens to make it. Only the row is the planning entity.
>> Each digit has a value, row, column and a fixed status. A fixed digit has
>> row, column and value assigned and fixed status set to true (you must not
>> reassign row of this). An unsolved digit has a null row, with column and
>> value assigned and fixed status set to false.
>>
>> I included three cases. It solves a completely blank grid, it doesnt solve a
>> 24-digit problem (it gets stuck at a step, see included log snippet), it
>> solves an easier 8-digit version of same problem in *much longer time*.
>>
>> *Case*: Output of solving a completely blank grid
>> 12:42:33.977 [main] INFO  o.d.p.c.l.DefaultLocalSearchSolverPhase - Phase
>> local search finished: step total (148), time spend (5491), best score (0).
>> 12:42:33.977 [main] INFO  o.d.p.core.solver.DefaultSolver - Solved: time
>> spend (5491), best score (0), average calculate count per second (17598).
>>
>> *Case*: solving problem 1: 24 digits of
>> http://puzzles.about.com/library/sudoku/blprsudokux01.htm
>> 12:51:34.279 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase -     Step
>> index (10530), time spend (164914), score (-3),     best score (-3),
>> accepted move size (456) for picked step (Digit:4 (Row 5,Column 2) block
>> code[10]  =>   Row 3)
>>
> I don't see a construction heuristic at work here. Have you tried
> running a construction heuristic before the local search?
> It's not hard, just add 3 lines (use FIRST FIT). Take a look 5.4.0.Beta2
> version of nqueensSolverConfig.xml.
> <constructionHeuristic>
> <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
> <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType><!--
> for speed -->
> </constructionHeuristic>
> <localSearch>
>         ...
>
> I wouldn't be surprised that a construction heuristic solves the 24 clue
> sudoku immediately,
> without having to resort to local search even.
Correction: If the score function adds a positive soft constraint
when 2 digits are on the same row, column or block and don't clash,
only then I wouldn't be surprised that a construction heuristic solves 
the 24 clue sudoku immediately.
Also, remove the FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING line (as 
that's not good if there are positive constraints).

Sudoku probably isn't really a straightforward, good example for Planner.