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

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.