Hi 1to9only,
Thanks to your SE modification for pencilmark-only puzzles, a possibly new hardest record can be proven.
Rating first of the Tarek's puzzles of backdoor 6 in singles in batch mode after 47 hours gave ED=20.0/2.3/2.3 which to my knowledge is indication of error.
In GUI mode, after the first few 2.3, series of 2 x 9.1 and about 10-15 x 9.2, the process hangs by repeatedly giving an "empty" next hint.
I would be glad if you manage to do following in the batch processing
- dump the pencilmarks at the time the process identifies its inability to continue and returns ER=20.0;
- possibly extend the hardest technique if it is simply matter of one more recursion or so.
Cheers,
MD
Help With Sudoku Explainer
SukakuExplainerNOAE
by dobrichev » Tue Jul 30, 2019 4:37 pm
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by 1to9only » Tue Jul 30, 2019 9:45 pm
it's been a while since i looked at the SE sukaku code - i'll run it thru the tarek 11 original puzzles with a view to output the pencilmartks after each SE step. it may take a little while to come up with something, as the debugging will be slow - the number of pencilmarks makes SE slow!
-
1to9only - Posts: 4175
- Joined: 04 April 2018
SukakuExplainerNOAE pencilmarks
by 1to9only » Wed Jul 31, 2019 2:49 pm
I've updated the Hints code (the logical place to make my changes!) to output the pencilmarks BEFORE each SE solving step.
Download the updated SukakuExplainerNOAE.jar (size: 306,733 bytes) from:
http://s000.tinyupload.com/?file_id=06704679737269179102
MD5: 07b5c284211447db37fdd4737c1c102e
[Edit 5 Aug] SukakuExplainerNOAE is now obsolete! see here.
I've put the first of tarek's 11 sukakus from the earlier link posted by MD in a file named puzzle.txt
Usage:
The output can be redirected to a file, use Ctrl-C to exit if the program hangs!
Output (up to the point where SukakuExplainerNOAE hangs:):
Source: The updated getHintsHint() code (in Solver.java) is below:
[Edit 5 Aug] SukakuExplainerNOAE is now obsolete! see here.
I've put the first of tarek's 11 sukakus from the earlier link posted by MD in a file named puzzle.txt
- Code: Select all
..3.5678.1.3456789123456789.23456789...4.678912.4567891234567891.34567891..45.789123.567891.3...7..12345.7..123....891234.678912.4...8.123..6.891........12345.7891234567891234567..12345678.123456.8912345678912345678.123.56.89123456..9123456789.23456789...4.678912.4567891.3.567891.34567891..45.789.234567891..4.678912.456789.23..6.891234.6789123456789123.567891.3...7.912345.789123.567891234.678912.4..78.123456.891234.6...123456789123.56..91234567.91234..7..123456.891234.6...12345678.1234567891...5678912.45678912345678912345678.12.45678..23.567891.3456789123456789123.567891.....7.912.45.789123..6.891234.678912.4..78..23.567891.3...7.912345.789123.56..91234567.9123456789123456.891234.6...12345678.1234567891234567.912345.7..
Usage:
- Code: Select all
java.exe -Xrs -Xmx500m -cp SukakuExplainerNOAE.jar diuf.sudoku.test.hints --input=puzzle.txt
The output can be redirected to a file, use Ctrl-C to exit if the program hangs!
Output (up to the point where SukakuExplainerNOAE hangs:):
Hidden Text: Show
Source: The updated getHintsHint() code (in Solver.java) is below:
Hidden Text: Show
Last edited by 1to9only on Mon Aug 05, 2019 8:22 am, edited 1 time in total.
-
1to9only - Posts: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by dobrichev » Wed Jul 31, 2019 3:34 pm
Thank you!
I will run it for another 2 days to see if it will log more steps before giving up.
BTW is it possible to store the original source files on a public repository? The original project by Nicolas Juillerat disappeared, isn't it?
I've searched for clones and found some which possibly include already modified code.
On my machine I have some files but I am unsure whether they are clean and which version represent.
Cheers,
MD
I will run it for another 2 days to see if it will log more steps before giving up.
BTW is it possible to store the original source files on a public repository? The original project by Nicolas Juillerat disappeared, isn't it?
I've searched for clones and found some which possibly include already modified code.
On my machine I have some files but I am unsure whether they are clean and which version represent.
Cheers,
MD
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by rjamil » Wed Jul 31, 2019 4:47 pm
Hi MD,
I have original source code of Sudoku Explainer by Nicolas Juillerat in my collection, containing 28-Dec-2007 zipped files of the same.
R. Jamil
I have original source code of Sudoku Explainer by Nicolas Juillerat in my collection, containing 28-Dec-2007 zipped files of the same.
R. Jamil
- Attachments
-
SudokuExplainer-src.zip- (190.96 KiB) Downloaded 274 times
- rjamil
- Posts: 730
- Joined: 15 October 2014
- Location: Karachi, Pakistan
Re: Help With Sudoku Explainer
by dobrichev » Wed Jul 31, 2019 8:09 pm
Thank you, rjamil. These source files appear to be authentic.
Now, the next part - does anybody want to create a public repository, say in github, for this project with appropriate credit to Nicolas?
Ideally, over time this project will accumulate links to the work of other contributors as well as code with improvements.
Personally I don't want to manage java project but if nobody else wants I can create it.
Now, the next part - does anybody want to create a public repository, say in github, for this project with appropriate credit to Nicolas?
Ideally, over time this project will accumulate links to the work of other contributors as well as code with improvements.
Personally I don't want to manage java project but if nobody else wants I can create it.
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by 1to9only » Thu Aug 01, 2019 7:00 pm
I think that fixing the AE (AlignedExclusion) issue in SE for Aligned Pair (SE=6.2) and Triplet (SE=7.5) Exclusions will go some way to fix the sukaku solver.
The minimum number of clues in a vanilla sudoku puzzle is 17, the number of unsolved cells being 64 - which is exactly the number of bits in an integer. SE uses this feature: each bit in the integer is used to denote an unsolved cell - in Permutations.java, bits are set for permutations of unsolved cells that are being considered for exclusion.
The SE AlignedExclusion code does not work for sukakus that have more than 64 unsolved cells.
Modifying SE Permutations.java to use:
- a 128-bit integer (BigInteger) is a possibility, but I don't think bit manipulation is well suported.
- a BitSet is possible, but code changes are required.
- 2 64-bit integers, and more code changes are required.
I've no plans to try out any of the above.
The minimum number of clues in a vanilla sudoku puzzle is 17, the number of unsolved cells being 64 - which is exactly the number of bits in an integer. SE uses this feature: each bit in the integer is used to denote an unsolved cell - in Permutations.java, bits are set for permutations of unsolved cells that are being considered for exclusion.
The SE AlignedExclusion code does not work for sukakus that have more than 64 unsolved cells.
Modifying SE Permutations.java to use:
- a 128-bit integer (BigInteger) is a possibility, but I don't think bit manipulation is well suported.
- a BitSet is possible, but code changes are required.
- 2 64-bit integers, and more code changes are required.
I've no plans to try out any of the above.
-
1to9only - Posts: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by dobrichev » Fri Aug 02, 2019 11:15 am
Hi 1to9only,
Below is a wrapper to Permutations. Could you try it?
I saw that from AlignedExclusion only Permutations.hasNext() followed by Permutations.nextBitNums() are called.
Replacing Permutations with Permutations128 in AlignedExclusion.java should work (after fixing the possible syntax errors and bugs in the attached Permutations128).
Aren't AlignedExclusion techniques covered by the complicated chains or there are special filters in chains techniques that expect AlignedExclusion was previously applied?
If AlignedExclusion is covered by the more complex techniques, then enabling it wouldn't resolve the ER=20.0 problem IMO.
Below is a wrapper to Permutations. Could you try it?
I saw that from AlignedExclusion only Permutations.hasNext() followed by Permutations.nextBitNums() are called.
Replacing Permutations with Permutations128 in AlignedExclusion.java should work (after fixing the possible syntax errors and bugs in the attached Permutations128).
Hidden Text: Show
Aren't AlignedExclusion techniques covered by the complicated chains or there are special filters in chains techniques that expect AlignedExclusion was previously applied?
If AlignedExclusion is covered by the more complex techniques, then enabling it wouldn't resolve the ER=20.0 problem IMO.
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by 1to9only » Fri Aug 02, 2019 4:37 pm
I've written some test code for Permutations.java:
Output:
The same test code for Permutations128.java:
Output: as for Permutations.java, and then an exception:
Needs some debugging (I'll find some time!) - looks to be in hasNext().
In SE, for APE/ATE CountOnes is always 2. For ATE, AlignedExclusion.java has this comment:
Hidden Text: Show
Output:
Hidden Text: Show
The same test code for Permutations128.java:
Hidden Text: Show
Output: as for Permutations.java, and then an exception:
Hidden Text: Show
Needs some debugging (I'll find some time!) - looks to be in hasNext().
In SE, for APE/ATE CountOnes is always 2. For ATE, AlignedExclusion.java has this comment:
Hidden Text: Show
-
1to9only - Posts: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by dobrichev » Fri Aug 02, 2019 6:10 pm
in Permutations128 the line in nextBitNums()
should be
(How it compiles? Should everywhere this.xxx be used for safety?)
Your test demonstrated that even for < 64 bits the emulator doesn't work.
Good next test cases include
- Code: Select all
int[] result = new int[countOnes];
should be
- Code: Select all
int[] result = new int[curCountOnesLow + countBitsHigh];
(How it compiles? Should everywhere this.xxx be used for safety?)
Your test demonstrated that even for < 64 bits the emulator doesn't work.
Good next test cases include
- Code: Select all
Permutations128 cellSetPerm128 = new Permutations128( 0, 9); // <=== the first call to hasNext() should return false
Permutations128 cellSetPerm128 = new Permutations128( 1, 90); // <=== will test only lower and only higher iterators
Permutations128 cellSetPerm128 = new Permutations128( 2, 90); // <=== will test merging the lower and higher iterators
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by 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:
To be dubugged.
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: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by 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.
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: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by dobrichev » Sat Aug 03, 2019 6:46 am
In the initialization
Below are 2 examples for the logic
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
The second one is still in processing, taking more time than first.
The older SukakuExplainerNOAE gave 20.0 for the second and third puzzles.
- Code: Select all
curCountOnesHigh = countOnes - countBitsLow; <== WRONG, should be
curCountOnesHigh = countOnes - curCountOnesLow;
Below are 2 examples for the logic
Hidden Text: Show
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
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: 1850
- Joined: 24 May 2010
Re: Help With Sudoku Explainer
by 1to9only » Sat Aug 03, 2019 1:47 pm
In AlignedExclusion.java:
In AlignedPairExclusion.java:
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.
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:
I should have a new sukaku solver release soon...
- 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: 4175
- Joined: 04 April 2018
Re: Help With Sudoku Explainer
by 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
to
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
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: 1850
- Joined: 24 May 2010
