Help With Sudoku Explainer

Interactive on-site game threads go here

Re: Help With Sudoku Explainer

Postby 1to9only » Fri Aug 02, 2019 7:47 pm

Thanks for code fix - earlier I just set [countOnes] to [curCountOnesLow], as it's always going to be 2.

In my earlier post P128(2,9) produces the same sequence as the existing P(2,9) - that's good, but for the exception at the end which still occurs, so will need looking into. So P128(n,k) where k<=64 look ok, but will need some testing against the same P(n,k) for k<=64.

For P128(2,74), it's giving erroneous results. I was expecting 74x73/2 = 2701 pairs, eg. 0,1 - 0,2 ... 72,73.

It's producing more pairs than expected:
Code: Select all
Permutations128( 2, 74);
 0: 0, 1
 1: 0, 2
...
92736: 0, 64
...
92800: 0, 64 <- repeated many times
92864: 0, 64
92928: 0, 65
92992: 0, 64
...
93184: 0, 64
93248: 0, 65
93312: 0, 66
...
100624: 70, 71

To be dubugged.
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby 1to9only » Fri Aug 02, 2019 8:44 pm

Still trying to figure out P128 code, some possible fixes in the P128 initialser:

curCountOnesLow = countOnes >= 64 ? 64 : countOnes;
countBitsLow = countBits >= 64 ? 64 : countBits;
countBitsHigh = countBits - countBitsLow;
maxCountOnesHigh = countOnes >= countBitsHigh ? countBitsHigh : countOnes;
curCountOnesHigh = countOnes - curCountOnesLow;
permLow = new Permutations(curCountOnesLow, countBitsLow);
if(countBitsHigh != 0) {
permHigh = new Permutations(curCountOnesHigh, countBitsHigh);
}

maxCountOnesHigh also looks incorrect to me.
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby dobrichev » Sat Aug 03, 2019 6:46 am

In the initialization
Code: Select all
curCountOnesHigh = countOnes - countBitsLow; <== WRONG, should be
curCountOnesHigh = countOnes - curCountOnesLow;


Below are 2 examples for the logic
Hidden Text: Show
Code: Select all
3210987654321098765432109876543210987654321098765432109876543210 3210987654321098765432109876543210987654321098765432109876543210
................................................................ ................................................................


Consider case countOnes = 2 out of countBits = 70 bits:
..........................................................HHHHHH LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
curCountOnesLow = countOnes >= 64 ? 64 : countOnes; <== starts from 2 bits in L part
countBitsLow = countBits >= 64 ? 64 : countBits; <== L is const 64
countBitsHigh = countBits - countBitsLow; <== H is const 70 - 64 = 6
maxCountOnesHigh = countOnes >= countBitsHigh ? countBitsHigh : countOnes; <== 2
curCountOnesHigh = countOnes - countBitsLow; <== WRONG, should be
curCountOnesHigh = countOnes - curCountOnesLow; <== starts with 0 bits in H part
permLow = new Permutations(curCountOnesLow, countBitsLow);
if(curCountOnesHigh != 0) { <== initially we don't use permHigh instance
   permHigh = new Permutations(curCountOnesHigh, countBitsHigh);
}
nextHigh = 0;

Expected results:
................................................................ ..............................................................11
................................................................ .............................................................1.1
................................................................ .............................................................11.
later
................................................................ 11..............................................................
at this point permLow exhausted, we are starting permHigh(1, 6) and restarting permLow(1, 64)
...............................................................1 ...............................................................1
...............................................................1 ..............................................................1.
later
...............................................................1 1...............................................................
at this point permLow exhausted again, we are restarting permHigh(2, 6) and stop using permLow
..............................................................11 ................................................................
.............................................................1.1 ................................................................
.............................................................11. ................................................................
up to
..........................................................11.... ................................................................
done

Consider case countOnes = 3 out of countBits = again 70 bits:
..........................................................HHHHHH LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
first
................................................................ .............................................................111
later
................................................................ 111.............................................................
start using permHigh(1, 6) and restart permLow(2, 64)
...............................................................1 ..............................................................11
later
...............................................................1 11..............................................................
advance permHigh and restart permLow(2, 64)
..............................................................1. ..............................................................11
later
..........................................................1..... 11..............................................................
restart permHigh(2, 6) and restart permLow(1, 64)
..............................................................11 ...............................................................1
later
..........................................................11.... 1...............................................................
restart permHigh(3, 6) and stop using permLow
.............................................................111 ................................................................
up to
..........................................................111... ................................................................
done


Maybe it is worth trying BigInteger by replacing long to BigInteger and >>>2 to /4 in a clone of the original Permutations.java.

Meanwhile the first of the Tarek's hardest puzzles finished with this pencilmark state
Hidden Text: Show
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 35678     13456789  12346789  | 23456789  46789     12456789  | 2346789   3456789   4789      |
| 2356789   37        23457     | 2389      2346789   248       | 23689     1         2345789   |
| 12346789  1234567   1234678   | 12345689  123456789 12345678  | 23689     234569    2346789   |
+-------------------------------+-------------------------------+-------------------------------+
| 23456789  46789     12456789  | 1356789   13456789  145789    | 23456789  46789     12456789  |
| 23689     12346789  123456789 | 12356789  1379      12345789  | 12356789  2346789   12478     |
| 12345689  12346     123456789 | 123569    12345679  12347     | 12345689  2346      12345678  |
+-------------------------------+-------------------------------+-------------------------------+
| 12346789  156789    1246789   | 123456789 12345678  1245678   | 236789    3456789   12346789  |
| 12356789  179       1245789   | 123689    12346789  12478     | 2356789   379       12345789  |
| 12369     12345679  12346789  | 12345689  12346     12345678  | 12346789  2345679   12347     |
+-------------------------------+-------------------------------+-------------------------------+
................1................................................................ 9.2, Double Forcing Chain: I2.5 on & off ==> A1.5 off
+-------------------------------+-------------------------------+-------------------------------+
| 3678      13456789  12346789  | 23456789  46789     12456789  | 2346789   3456789   4789      |
| 2356789   37        23457     | 2389      2346789   248       | 23689     1         2345789   |
| 12346789  1234567   1234678   | 12345689  123456789 12345678  | 23689     234569    2346789   |
+-------------------------------+-------------------------------+-------------------------------+
| 23456789  46789     12456789  | 1356789   13456789  145789    | 23456789  46789     12456789  |
| 23689     12346789  123456789 | 12356789  1379      12345789  | 12356789  2346789   12478     |
| 12345689  12346     123456789 | 123569    12345679  12347     | 12345689  2346      12345678  |
+-------------------------------+-------------------------------+-------------------------------+
| 12346789  156789    1246789   | 123456789 12345678  1245678   | 236789    3456789   12346789  |
| 12356789  179       1245789   | 123689    12346789  12478     | 2356789   379       12345789  |
| 12369     12345679  12346789  | 12345689  12346     12345678  | 12346789  2345679   12347     |
+-------------------------------+-------------------------------+-------------------------------+
ED=20.0/2.3/2.3

The second one is still in processing, taking more time than first.
The older SukakuExplainerNOAE gave 20.0 for the second and third puzzles.
dobrichev
2016 Supporter
 
Posts: 1734
Joined: 24 May 2010

Re: Help With Sudoku Explainer

Postby 1to9only » Sat Aug 03, 2019 1:47 pm

In AlignedExclusion.java:
Code: Select all
Permutations cellSetPerm2 = new Permutations(2, candidateList.size());

In AlignedPairExclusion.java:
Code: Select all
Permutations cellSetPerm2 = new Permutations(2, cellExcluders.size());

I've already spent too much time on this AE problem!

I written some custom code for the specific AE cases above, P(n,k) for n=2 and k<=81, to generate the permutations in the same order, sample code is below.
Code: Select all
Init: n1 = 0; n2 = n1 + 1;
nextBitNums: n1, n2
next: n1++; if ( n1 == n2 ) { n1 = 0; n2++; }
hasNext: isLast = (n2 == countBits);

The code for P(n,k) for all n<=k<=81 would be nice, but this will be very low priority for me.

Also in AlignedExclusion.java, but I don't think these need changing:
Code: Select all
Permutations tailSetPerm = new Permutations(degree - 2, tailCells.size());
Permutations perm = new Permutations(2, degree);

I should have a new sukaku solver release soon...
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby dobrichev » Sat Aug 03, 2019 2:01 pm

Hi again,

Finally I managed to compile java on my machine.

The SE sources from this post by rjamil compiled after replacing in 2 places
Code: Select all
            if (result == RES_WARN) // warning
                return new ErrorMessage(WARNING_MSG, false);
            else // error
                return new ErrorMessage(ERROR_MSG, true);

to
Code: Select all
            if (result == RES_WARN) // warning
                return new ErrorMessage(WARNING_MSG, false, null);
            else // error
                return new ErrorMessage(ERROR_MSG, true, null);


A careful reading of the last few pages of this thread suggests that latest Sukaku clone by 1to9only can be assembled by taking the zip source from this post, and then incrementally apply the updates posted later.
@1to9only: Should this work?

If this works, I could do these minor suggested adjustments myself and post the results here instead of asking you trivial questions...

Thanks,
MD
dobrichev
2016 Supporter
 
Posts: 1734
Joined: 24 May 2010

Re: Help With Sudoku Explainer

Postby 1to9only » Sat Aug 03, 2019 2:37 pm

dobrichev wrote:A careful reading of the last few pages of this thread suggests that latest Sukaku clone by 1to9only can be assembled by taking the zip source from this post, ...

This should work, the SukakuExplainer will have the AE issue.
Some later updates were to address the AE problem, are not needed if the AE code is fixed (see Twomutations.java below).
The code for pencilmarks will need adding to Solver.java.

This is my current Twomutations.java for P(n,k) where n=2 and k<=81:
Hidden Text: Show
Code: Select all
package diuf.sudoku.tools;

/**
 * Generator of binary permutations.
 * <p>
 * Given a length <tt>countBits</tt> and a
 * degree <tt>countOnes</tt> with
 * <tt>countOnes <= countBits</tt>, this class will compute
 * all binary numbers of length <tt>countBits</tt> that have
 * exactly <tt>countOnes</tt> bits equal to <tt>1</tt>.
 * <p>
 * The binary numbers are generated in increasing order.
 * <p>
 * Example: with <tt>countBits = 5</tt> and <tt>countOnes = 3</tt>
 * the following binary numbers are generated:
 * <ul>
 * <li>00111
 * <li>01011
 * <li>01101
 * <li>01110
 * <li>10011
 * <li>10101
 * <li>10110
 * <li>11001
 * <li>11010
 * <li>11100
 * </ul>
 * Code adapted from "Hacker's Delight" by Henry S. Warren,
 * ISBN 0-201-91465-4
 */
public class Twomutations {

    private final int countBits;
    private final int countOnes;

    private int n1;
    private int n2;

    private boolean isLast;

    /**
     * Create a new binary permutations generator.
     * <p>
     * The maximum supported value for <code>countBits</code>
     * is 64. <code>countOnes</code> must be equal or less than
     * <code>countBits</code>.
     * @param countOnes the number of bits equal to one
     * @param countBits the length of the binary numbers in bits
     */
    public Twomutations(int countOnes, int countBits) {
        if (countOnes < 0)
            throw new IllegalArgumentException("countOnes < 0");
        if (countBits < 0)
            throw new IllegalArgumentException("countBits < 0");
        if (countOnes > countBits)
            throw new IllegalArgumentException("countOnes > countBits");
        if (countBits > 81)
            throw new IllegalArgumentException("countBits > 81");
        this.countBits = countBits;
        this.countOnes = countOnes;
        this.n1 = 0;
        this.n2 = 1;
        this.isLast = (countBits == n2);
    }

    /**
     * Test if there are more permutations available
     * @return whether there are more permutations available
     */
    public boolean hasNext() {
        return !isLast;
    }

    /**
     * Get the next binary permutation.
     * @return the next binary permutation
     */
    public void next() {
        n1++;
        if ( n1 == n2 )
        {
           n1 = 0;
           n2++;
        }
        isLast = (countBits == n2);
    }

    /**
     * Get the next binary permutation as an array
     * of bit indexes.
     * @return the 0-based indexes of the bits that are set
     * to one.
     */
    public int[] nextBitNums() {
        int[] result = new int[countOnes];
        result[ 0] = n1;
        result[ 1] = n2;
        next();
        return result;
    }

}

Put this in diuf\sudoku\tools. And amend the two lines in
In AlignedExclusion.java:
Code: Select all
Twomutations cellSetPerm2 = new Twomutations(2, candidateList.size());

In AlignedPairExclusion.java:
Code: Select all
Twomutations cellSetPerm2 = new Twomutations(2, cellExcluders.size());
1to9only
 
Posts: 1093
Joined: 04 April 2018

updated SukakuExplainer

Postby 1to9only » Mon Aug 05, 2019 8:00 am

This is an updated version of SukakuExplainer with changes listed below.

Changes (from earlier version):
1. The GUI Load... dialog (which opened 'My Documents') now opens the 'current working directory'.
2. Implemented my APE/ATE fix, discussed in the last few posts.
3. Speed improvements, (to be) described here.
4. Output of pencilmarks.

Usage: unchanged, described here.

To display explainer pencilmarks (output is to screen, redirect to file if needed):
Code: Select all
java.exe -Xrs -Xmx500m -cp SukakuExplainer.jar diuf.sudoku.test.pencilmarks --input=puzzle.txt

SukakuExplainer.jar: [dead link]
302,858 bytes, MD5: 282d100fcc7ed46688a96e56c9ebaa30

SukakuExplainer-src.zip: [dead link]
52,517 bytes, MD5: cb032a8fec6eafc4d90cb6b858a842fd

[Edit 9 Oct]
There is an updated version of the 5 Aug release here.
There is an improved (faster) version of SukakuExplainer here.
Last edited by 1to9only on Wed Oct 09, 2019 3:21 pm, edited 2 times in total.
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby tarek » Mon Aug 05, 2019 9:13 am

Apologies for not participating as I should in this work which I have interest in. Thanks for all who have put some time into this which I'm sure came out of your personal time. I hope that you are like me (I've wasted so much time on sudoku & related stuff over the past 14 years) in enjoying every single bit of it :D

tarek
User avatar
tarek
 
Posts: 3080
Joined: 05 January 2006

Re: Help With Sudoku Explainer

Postby tarek » Mon Aug 05, 2019 9:18 am

dobrichev wrote:The second one is still in processing, taking more time than first.
The older SukakuExplainerNOAE gave 20.0 for the second and third puzzles.
I knew that the sukaku will stretch the SE logic to the extreme. I'm sure more and more would appear.

tarek
User avatar
tarek
 
Posts: 3080
Joined: 05 January 2006

Re: Help With Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:31 am

And I've wasted so much time on sudoku sukaku, and I don't even solve them! :lol:
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:34 am

tarek wrote:
dobrichev wrote:The second one is still in processing, taking more time than first.
The older SukakuExplainerNOAE gave 20.0 for the second and third puzzles.
I knew that the sukaku will stretch the SE logic to the extreme. I'm sure more and more would appear.
tarek

I tested the updated SukakuExplainer with the 1st of tarek's 11, I Ctrl-C'ed out after a few hours, so I think it will still come out a 20.0 ...
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby dobrichev » Mon Aug 05, 2019 4:27 pm

It took 3 days and 8 hours for SukakuExplainerNOAE to fail on the 4th tarek's puzzle.
Ctrl-C followed.
dobrichev
2016 Supporter
 
Posts: 1734
Joined: 24 May 2010

Re: Help With Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 6:58 pm

In Ruud's Pencilmark only Sudoku thread, he posted here a sukaku that 'scores 70070 in SudoCue, which needs 221 solving rounds, including 70 tabling steps and 1 guess'. It is SE rated as ED=11.2/9.4/2.8.

It might be worth (a try!) throwing tarek's 11 sukakus at Ruud's Sudocue. Probably been done already.
1to9only
 
Posts: 1093
Joined: 04 April 2018

Re: Help With Sudoku Explainer

Postby dobrichev » Tue Aug 06, 2019 12:23 am

For Tarek's hardest puzzle 4 I modified in SE code for chains level 5, file diuf/sudoku/solver/rules/chaining/Chaining.java
Code: Select all
    private Collection<Potential> getAdvancedPotentials(final Grid grid, final Grid source,
            final LinkedSet<Potential> offPotentials) {
        final Collection<Potential> result = new ArrayList<Potential>();
        if (otherRules == null) {
            otherRules = new ArrayList<IndirectHintProducer>();
            otherRules.add(new Locking(false));
            otherRules.add(new HiddenSet(2, false));
            otherRules.add(new NakedSet(2));
            otherRules.add(new Fisherman(2));
            if (level < 4) {
                if (level >= 2)
                    otherRules.add(new Chaining(false, false, false, 0)); // Forcing chains
                if (level >= 3)
                    otherRules.add(new Chaining(true, false, false, 0)); // Multiple forcing chains
            } else {
                // Dynamic Forcing Chains already cover Simple and Multiple Forcing Chains
                if (level >= 4)
                    otherRules.add(new Chaining(true, true, false, 0)); // Dynamic FC
//                if (level >= 5)
//                    otherRules.add(new Chaining(true, true, false, level - 3));
                if (level >= 5)
                    otherRules.add(new Chaining(true, true, false, level - 1));
            }
        }
....

With this modification, after processing the first 2 grid cells at level 5, the following hints appeared
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 3678      13456789  12346789  | 23456789  46789     12456789  | 2346789   3456789   4789      |
| 23456789  37        2347      | 289       234689    248       | 23689     1         2345789   |
| 12346789  1234567   1234678   | 12345689  123456789 123456789 | 23689     2345689   2346789   |
+-------------------------------+-------------------------------+-------------------------------+
| 23456789  146789    12456789  | 356789    13456789  145789    | 23456789  46789     12456789  |
| 23689     12346789  123456789 | 12356789  1379      12345789  | 12356789  2346789   12478     |
| 12345689  12346     123456789 | 123569    12345679  123457    | 12345689  2346      12345678  |
+-------------------------------+-------------------------------+-------------------------------+
| 12346789  156789    1246789   | 23456789  12345678  1245678   | 236789    3456789   12346789  |
| 12356789  179       1245789   | 23689     12346789  12478     | 2356789   379       12345789  |
| 123689    12345679  12346789  | 12345689  12346     12345678  | 12346789  2345679   12347     |
+-------------------------------+-------------------------------+-------------------------------+
ER=14.1   Contradiction Forcing Chain: A1.7 on ==> G3.9 both on & off
ER=13.2   Region Forcing Chains: 4 in row ==> C1.7 off
ER=13.8   Contradiction Forcing Chain: B1.7 on ==> D3.4 both on & off

The idea was to include all Level 4 NestedChains in the Level 5 NestedChains w/o changing the base ratings. Even if this approach is wrong, it doesn't change ruud's puzzle rating of ER=11.2/9.4/2.8.

P.S. For the hint ER=13.2 method toHtml() dumps 480 chains, ~1MB. From the explanation follows that setting 4 in any cell in row 1 leads to exclusion of candidate 7 in r1c3.
dobrichev
2016 Supporter
 
Posts: 1734
Joined: 24 May 2010

Re: Help With Sudoku Explainer

Postby tarek » Thu Aug 08, 2019 9:30 pm

No idea what I'm doing on GitHub but here goes nothing …

I've just created the repository

https://github.com/SudokuMonster/SukakuExplainer

Everything is still on default and is public. I didn't even add a Read.me file yet.

Haven't managed a project like this before but I guess we have to start somewhere!!

PM email or GitHub username to add collaborators.

I'll add something at some stage to the Readme file for proper attributions and links

tarek
User avatar
tarek
 
Posts: 3080
Joined: 05 January 2006

PreviousNext

Return to Interactive games