The New Sudoku Players' Forum

[1to9only]

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]

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.

[dobrichev]

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.

[1to9only]

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...

[dobrichev]

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

[1to9only]

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]

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.

[tarek]

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

tarek

[tarek]

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

[1to9only]

And I've wasted so much time on sudoku sukaku, and I don't even solve them!

[1to9only]

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 ...

[dobrichev]

It took 3 days and 8 hours for SukakuExplainerNOAE to fail on the 4th tarek's puzzle.
Ctrl-C followed.

[1to9only]

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.

[dobrichev]

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.

[tarek]

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