4:12 p.m.
I am making a 3x3 Sudoku solver with Drools planner. The planning entities
are the digits. The problem facts are the rows (planning variable) and
columns.
When I set Drools Planner to solve a problem where no digit is initialized,
it gives a perfect solution in ~15 secs. But when I set a few digits as
initialized, it never finds a solution. It always lists 8 hard constraints
broken on termination.
I implemented the moves as:
if(digit.getFixed()==false){
moveList.add(new RowChangeMove(digit, toRow));
}
If the digit is fixed, dont make a move object for it.
Earlier, I implemented it in isMoveDoable: if the digit.getFixed() is true,
it returns false. Both do not work.
20:31:13.442 [main] INFO o.d.p.c.l.DefaultLocalSearchSolverPhase - Phase
local search finished: step total (978), time spend (60061), best score
(-8).
20:31:13.442 [main] INFO o.d.p.core.solver.DefaultSolver - Solved: time
spend (60061), best score (-8), average calculate count per second (7433).
--
View this message in context:
http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
4:19 p.m.
Op 31-01-12 16:12, aitchnyu schreef:
I am making a 3x3 Sudoku solver with Drools planner. The planning
entities
are the digits. The problem facts are the rows (planning variable) and
columns.
When I set Drools Planner to solve a problem where no digit is initialized,
it gives a perfect solution in ~15 secs. But when I set a few digits as
initialized, it never finds a solution. It always lists 8 hard constraints
broken on termination.
I implemented the moves as:
if(digit.getFixed()==false){
moveList.add(new RowChangeMove(digit, toRow));
Presuming that your 3x3 looks
like this
row1, col1 | row1, col2 | row 1 col3
row2, col1 | row2, col2 | row 2 col3
row3, col1 | row3, col2 | row 3 col3
So when digit 4 starts on row1, col1
it can only move to row2, col1 and row3, col1
but never any of the 6 other points in col2 and col3?
}
If the digit is fixed, dont make a move object for it.
Earlier, I implemented it in isMoveDoable: if the digit.getFixed() is true,
it returns false. Both do not work.
20:31:13.442 [main] INFO o.d.p.c.l.DefaultLocalSearchSolverPhase - Phase
local search finished: step total (978), time spend (60061), best score
(-8).
20:31:13.442 [main] INFO o.d.p.core.solver.DefaultSolver - Solved: time
spend (60061), best score (-8), average calculate count per second (7433).
--
View this message in context:
http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
8:37 a.m.
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)
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).
*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-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
3:27 p.m.
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-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
3:37 p.m.
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.
7:19 a.m.
Here is the complete config I used (simulated annealing). I also tried it
with Solution tabu. Simulated annealing gets to the stuck state faster :-)
I am moving on to my main timetabling project; I got deadlines to meet. But
I feel a bit bad about leaving this unsolved. I would like to *send you* the
repo containing my working 2x2 sudoku solver that generates and solves
sudokus, and 3x3 solver that generates well and solves just a few problems.
Hopefully it will make a good standalone (no Swing, AbstractApp,
AbstractPersistable, Xstream and other hoops) *quickstart* for Drools
Planner, at ~500 lines of code that you can include in your documentation.
If heavy-duty constraint satisfaction isnt a strong point for (heuristics
and) Drools, it seems an example worth covering, right?
I, in turn will learn where my approach went wrong.
</constructionHeuristic> -->
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
</constructionHeuristic>
<localSearch>
<selector>
<moveFactoryClass>in.co.technovia.sudoku.solution.RowChangeMoveFactory</moveFactoryClass>
</selector>
<acceptor>
<simulatedAnnealingStartingTemperature>8</simulatedAnnealingStartingTemperature>
</acceptor>
<forager>
<minimalAcceptedSelection>20</minimalAcceptedSelection>
</forager>
</localSearch>
*For Tabu*
<acceptor>
<solutionTabuSize>1000</solutionTabuSize>
</acceptor>
--
View this message in context:
http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
9:21 a.m.
Op 02-02-12 07:19, aitchnyu schreef:
Here is the complete config I used (simulated annealing). I also
tried it
with Solution tabu. Simulated annealing gets to the stuck state faster :-)
I am moving on to my main timetabling project; I got deadlines to meet. But
I feel a bit bad about leaving this unsolved. I would like to *send you* the
repo containing my working 2x2 sudoku solver that generates and solves
sudokus, and 3x3 solver that generates well and solves just a few problems.
Hopefully it will make a good standalone (no Swing, AbstractApp,
AbstractPersistable, Xstream and other hoops) *quickstart* for Drools
Planner, at ~500 lines of code that you can include in your documentation.
If heavy-duty constraint satisfaction isnt a strong point for (heuristics
and) Drools, it seems an example worth covering, right?
All examples in Planner
inflict a certain maintenance cost: they need to
be refactored along, high-quality (because users copy them) and be
checked before every release.
There are already 2 toy examples (NQueens, Manners2009): that's enough.
Additional high-quality real-world examples with real-world data are
welcome though (for example airplane routing, job shop scheduling, ...).
That being said, do publish your repo on github, maybe someone else on
this list wants to take a shot at fixing it :)
I, in turn will learn where my approach went wrong.
</constructionHeuristic> -->
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
</constructionHeuristic>
<localSearch>
<selector>
<moveFactoryClass>in.co.technovia.sudoku.solution.RowChangeMoveFactory</moveFactoryClass>
</selector>
<acceptor>
<simulatedAnnealingStartingTemperature>8</simulatedAnnealingStartingTemperature>
</acceptor>
<forager>
<minimalAcceptedSelection>20</minimalAcceptedSelection>
</forager>
</localSearch>
*For Tabu*
<acceptor>
<solutionTabuSize>1000</solutionTabuSize>
</acceptor>
--
View this message in context:
http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
6:28 p.m.
Hello aitchnyu,
Can you share your source code about the Planner implementation on sudoku
game?
To train myself on Planner, I tried to implement a sudoku solver based on
Planner, but I didn't manage to go through.
Thank you in advance,
Quentin
--
View this message in context:
http://drools.46999.n3.nabble.com/Why-is-solving-a-partial-puzzle-much-sl...
Sent from the Drools: User forum mailing list archive at Nabble.com.
4368
days inactive
4468
days old
7 comments
3 participants
participants (3)
-
aitchnyu -
Geoffrey De Smet -
Qchevalier