The New Sudoku Players' Forum

[denis_berthier]

[post deleted: there was an error in the time computations]

[1to9only]

6:37:38,26 divided by 1:41:17,64 is roughly 3 times faster.
Its ok to calculate that saving about 5 hrs equates to 1%-25% gain.
No need to reply, as you already have your conclusions.

Edit: The program processing times for serate of the same puzzles on the same comp would be about the same.

[denis_berthier]

[Edit]
Total processor time is not the same thing as apparent time. Is is the sum of "user time" and "system time"
When you get a line such as:

Code: Select all

java -jar PGXplainer.jar    11368,39s user 78,88s system 363% cpu 52:28,17 total

"11368,39s user" is the total processor time of the application;
"78,88s system" is the system time related to running the application;
"363% cpu" is the mean number of cores used in parallel;
"52:28,17 total" is only the apparent time (= 3148.17s). it's more or less what you can measure with an outside stopwatch.

The real total processor time for the application is: 11368,39s + 78,88s = 11447.27s
The ratio 11447.27 / 3148.17 = 3.63 is equal to the mean number of cores used in parallel.

See post further on for an application to a real case.

[creint]

Batch difficulty can probably be optimized even further.

Edit: PGExplainer can be >2x times faster with some simple fixes that don't affect the rating.

[denis_berthier]

Batch difficulty can probably be optimized even further.
Edit: PGExplainer can be >2x times faster with some simple fixes that don't affect the rating.

I'm sure everybody here would like to see this fixed version.

[creint]

Take https://github.com/1to9only/PGExplainer

Add file SmallestHintsAccumulator.java (taken and edited from SukakuExplainer)

Hidden Text: Show

Code: Select all

package sudoku;

import java.util.ArrayList;
import java.util.List;

public class SmallestHintsAccumulator implements HintsAccumulator {

    private List<Hint> result;

   // dif is 0.0 at start, and changes to first added rating
    private double totalDif = 0.0;
   private double stepMax = 0.0;

    public SmallestHintsAccumulator() {
        super();
        this.result = new ArrayList<Hint>();
    }

    public void add(Hint hint) throws InterruptedException {
       double newDifficulty = ((Rule)hint).getDifficulty();
      if(stepMax == 0.0) {
         
         if (newDifficulty > totalDif)
         {
            stepMax = newDifficulty;
         }
         else
         {
            stepMax = totalDif;
         }
      } else if(newDifficulty > stepMax) {
         throw new InterruptedException(); // this assumes calls are ordered strictly ascending by difficulty
      } else if(newDifficulty > totalDif) {
         totalDif = newDifficulty;
      }
      result.add(hint);
    }
   
    public void clearStep()
    {
       result.clear();
       if (stepMax > totalDif)
       {
          totalDif = stepMax;
       }
       stepMax = 0.0;
    }
   
    public List<Hint> getHints() {
        return result;
    }

    public boolean hasHints()
    {
       return !result.isEmpty();
    }

} // class SmallestHintsAccumulator


In solver.java add

Hidden Text: Show

In Constructor by the others

Code: Select all

private List<IndirectHintProducer> indirectHintProducersLate;

        indirectHintProducersLate = new ArrayList<IndirectHintProducer>();
        indirectHintProducersLate.add( new Locking(false));
        indirectHintProducersLate.add( new NakedSet(2));
        indirectHintProducersLate.add( new HiddenSet(2, false));
        indirectHintProducersLate.add( new NakedSet(3));
        indirectHintProducersLate.add( new HiddenSet(3, false));
        indirectHintProducersLate.add( new XYWing(false));
        indirectHintProducersLate.add( new XYWing(true));
        indirectHintProducersLate.add( new NakedSet(4));
        indirectHintProducersLate.add( new HiddenSet(4, false));

Hidden Text: Show

Code: Select all

public void getFastDifficulty() {
        difficulty = 0.0;
        pearl = 0.0;
        diamond = 0.0;
        SmallestHintsAccumulator accu = new SmallestHintsAccumulator();
        while (!isSolved()) {
            try {
                for (HintProducer producer : directHintProducers)
                    producer.getHints(grid, accu);
                if (accu.hasHints()) throw new InterruptedException();
               
                if (difficulty < 9.0)
                {
                   for (IndirectHintProducer producer : indirectHintProducers)
                      producer.getHints(grid, accu);
                   if (accu.hasHints()) throw new InterruptedException();
                }
                else
                {
                   for (IndirectHintProducer producer : indirectHintProducersLate)
                      producer.getHints(grid, accu);   
                   if (accu.hasHints()) throw new InterruptedException();
                }
                if (difficulty < 10.0)
                {
                   for (IndirectHintProducer producer : chainingHintProducers)
                      producer.getHints(grid, accu);
                   if (accu.hasHints()) throw new InterruptedException();
               }
                for (IndirectHintProducer producer : chainingHintProducers2)
                    producer.getHints(grid, accu);
                if (accu.hasHints()) throw new InterruptedException();
                for (IndirectHintProducer producer : advancedHintProducers)
                    producer.getHints(grid, accu);
                if (accu.hasHints()) throw new InterruptedException();
                for (IndirectHintProducer producer : experimentalHintProducers)
                    producer.getHints(grid, accu);
            } catch (InterruptedException willHappen) {}
            List<Hint> hints = accu.getHints();
            if (hints.isEmpty()) {
                break;
            }
           
            for (Hint hint : hints)
            {
               Rule rule = (Rule)hint;
               double ruleDiff = rule.getDifficulty();
                if (ruleDiff > difficulty)
                    difficulty = ruleDiff;
               
                if (pearl == 0.0) {
                    if (diamond == 0.0)
                        diamond = difficulty;
                    if (hint.getCell() != null) {
                        pearl = difficulty;
                    }
                }
               
                hint.apply(grid);
            }
           
            accu.clearStep();
        }
    }

In serate.java replace the solver.getDifficulty(); with solver.getFastDifficulty();

With an hardest SE 11.90 it goes from ~13 minutes to ~6.

[denis_berthier]

Thanks.

It would be better to start from PGXplainer: https://github.com/1to9only/PGXplainer so as to have some bug fixes.

[denis_berthier]

.
I could make the changes and compile the result.

Using the following 11.7 puzzle as an example (1st in ph2010) and with nothing running at the same time:

Code: Select all

98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.

(RAM is the largest size reached during the process).


For SER:
time java -jar SudokuExplainer.jar diuf.sudoku.test.serate 98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
1.95 GB
java -cp SudokuExplainer.jar diuf.sudoku.test.serate --format=%r 1540,65s user 21,72s system 104% cpu 24:50,43 total
Real total processor time: 1540,65s + user 21,72s system = 1561.93 s

For PGX:
time java -jar PGXplainer.jar 98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
6.24 GB
java -jar PGXplainer.jar 1508,03s user 19,59s system 404% cpu 6:17,43 total
Real total processor time: 1508,03s user + 19,59s system = 1527.62 s

For your modif of PGE:
time java -jar modif-PGEplainer.jar 98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
5.98 GB
java -jar PGExplainer.jar 574,52s user 13,67s system 308% cpu 3:10,59 total
Real total processor time: 574,52s user + 13,67s system = 588.19

On this example, it seems that your modifications really reduce computation time.

For a software on GitHub, the standard procedure for you would be to make a pull request to 1to9only. Let's see what he does with it.


Now, for people involved in looking for the "hardest" puzzles and in order to compare also with the computations for the BpB classification, using the SHC (this puzzle is in B6B):
time java -jar SHC.jar BpB -puzzle 98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
2.08 GB
java -jar SHC.jar BpB -puzzle 13,40s user 0,94s system 97% cpu 14,730 total
Real total processor time: 13,40s user + 0,94s system = 14.34 s

[1to9only]

PGE is a faster SE meant for the Patterns Game, which is now dead! So I dont expect any changes to PGE/PGX.
You can clone PGE/PGX from Github and make changes to suit your projects.

[denis_berthier]

.
Without being a java programmer, I could include creint's changes into PGXplainer (instead of PGExplainer). Indeed, the two changes are independent and you can make the above ones given by creint directly into PGXplainer instead of PGExplainer.


For the same puzzle as before:
java -jar PGXplainer.jar 571,75s user 13,05s system 319% cpu 3:03,08 total
Real total processor time: 571,75s user + 13,05s system = 584.8s = [b]584.8s/b]
Same gain as with the PGE modified version

Of course, this would require much more extensive testing, but I have no time for this right now.

If anyone wants the resulting version of PGX, PM me.
[Edit]: after someone asked, I created a link:
https://drive.google.com/file/d/1vxl21CkrY_r6Vv5Cbc8DIHmgo_F2S02_/view?usp=share_link
.

[1to9only]

FWIW,
SE, PGE, PGX, rate Loki as ED=11.9/1.2/1.2
skfr, my own mods of lksudoku's batch, creint's batch mods, rate Loki as ED=11.8/1.2/1.2

[creint]

Then there is probably a bug:

Code: Select all

....5..........7....34.6.8..23....8...34.6...1.3..............9123......1.3..6....234.6..9.234....9..34.6..9.23.5.7....34567..1.3.5.7.9..345....12....7.........8..234.6.8.1..........34.6.89.2....78...3456.....3.....9..345.7...23.5.7....3.567....3...7.9..3.5...91.............6..........8...3.5.7....3.5.7.....4......2.........34.67....345......34.67..1..........3.5.7...2..............8...3.5.7..........9..3...78...3.5..8..2.........3.5.7..........9...4.....1.............6.....3.5.7..1.34...89..34...89..345.7.9..3.5.7...2............6.....3.5.7.........891...5....1.3...........6.....3.5.7..........9..3.5.7.........8..2.......1.3.5.7.....4......23...789.23....89..3.5.789...4.....1..........3.5.7.......6..........89..3.5.7..

PGX gives possibility: 11.8 -8r3c1 -8r9c3

PGX 11.8 -9r2c6:

Code: Select all

....5..........7....34.6.8..23....8...34.6...1.3..............9123......1.3..6....234.6..9.234....9..34.6..9.23.5.7....34567..1.3.5.7....345....12....7.........8..234.6.8.1..........34.6.89.2....78...3456.....3.....9..345.7...23.5.7....3.567....3...7.9..3.5...91.............6..........8...3.5.7....3.5.7.....4......2.........34.67....345......34.67..1..........3.5.7...2..............8...3.5.7..........9..3...78...3.5..8..2.........3.5.7..........9...4.....1.............6.....3.5.7..1.34...89..34...89..345.7.9..3.5.7...2............6.....3.5.7.........891...5....1.3...........6.....3.5.7..........9..3.5.7.........8..2.......1.3.5.7.....4......23...789.23....89..3.5.789...4.....1..........3.5.7.......6..........89..3.5.7..

PGX does Single 9r3c6 -9r3c3:

Code: Select all

....5..........7....34.6.8..23....8...34.6...1.3..............9123......1.3..6....234.6..9.234....9..34.6..9.23.5.7....34567..1.3.5.7....345....12....7.........8..234.6.8.1..........34.6.8..2....78...3456...........9..345.7...23.5.7....3.567....3...7.9..3.5...91.............6..........8...3.5.7....3.5.7.....4......2.........34.67....345......34.67..1..........3.5.7...2..............8...3.5.7..........9..3...78...3.5..8..2.........3.5.7..........9...4.....1.............6.....3.5.7..1.34...89..34...89..345.7.9..3.5.7...2............6.....3.5.7.........891...5....1.3...........6.....3.5.7..........9..3.5.7.........8..2.......1.3.5.7.....4......23...789.23....89..3.5.789...4.....1..........3.5.7.......6..........89..3.5.7..

PGX then gives possibility: 11.9 -8r3c1 -8r9c3

So removing candidates makes it harder?

[denis_berthier]

.
The bug is the old conceptual bug in SER: the use of uniqueness. Try to use it without uniqueness (with the -M option].

[creint]

Uniqueness is not the problem.
Removing otherRules.add(new Fisherman(2)); in chaining.java getAdvancedPotentials will give the 2 11.8 instead of the 5 11.9 when that code is in place.

[denis_berthier]

Uniqueness is not the problem.
Removing otherRules.add(new Fisherman(2)); in chaining.java getAdvancedPotentials will give the 2 11.8 instead of the 5 11.9 when that code is in place.

OK, I see.
This kind of problem is generally due to uniqueness.
In the present case, it must be due to another conceptual problem with SER: the non-confluence property of the "rules" defining the various levels of SER. If you change the order in which rules are applied (which you do by deleting one rule), you get a different resolution path.