Re: Why is solving a partial puzzle much slower than generating one from scratch?
Geoffrey De Smet <ge0ffrey.spam <at> gmail.com>
2012-02-01 14:27:54 GMT
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.
> It gets *stuck* here forever.
> 12:59:31.398 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4265), time spend (74003), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 5,Column 7) block code[12] =>
> Row 3).
> 12:59:31.429 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4266), time spend (74034), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 3,Column 4) block code[11] =>
> Row 5).
> 12:59:31.444 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4267), time spend (74049), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 5,Column 4) block code[11] =>
> Row 3).
> 12:59:31.459 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4268), time spend (74064), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 3,Column 7) block code[12] =>
> Row 5).
> 12:59:31.474 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4269), time spend (74079), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 5,Column 7) block code[12] =>
> Row 3).
> 12:59:31.493 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4270), time spend (74098), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 3,Column 4) block code[11] =>
> Row 5).
> 12:59:31.508 [main] DEBUG o.d.p.c.l.DefaultLocalSearchSolverPhase - Step
> index (4271), time spend (74113), score (-3), best score (-3), accepted
> move size (520) for picked step (Digit:7 (Row 5,Column 4) block code[11] =>
> Row 3).
If you're using <propertyTabu>7 or higher, this is probably a score trap
(look for "score trap" in the manual).
But go for the constr. heuristic first.
>
> *Case*: reducing predefined digits down to 6
> 13:02:31.093 [main] INFO o.d.p.c.l.DefaultLocalSearchSolverPhase - Phase
> local search finished: step total (554), time spend (12849), best score (0).
> 13:02:31.094 [main] INFO o.d.p.core.solver.DefaultSolver - Solved: time
> spend (12850), best score (0), average calculate count per second (25229)
>
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-slower-than-generating-one-from-scratch-tp3703622p3705805.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> rules-users <at> lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
--
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users <at> lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
RSS Feed