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 > [email protected] > https://lists.jboss.org/mailman/listinfo/rules-users > -- With kind regards, Geoffrey De Smet _______________________________________________ rules-users mailing list [email protected] https://lists.jboss.org/mailman/listinfo/rules-users
