The New Sudoku Players' Forum

[champagne]

deleted obsolete
EDIT 1 processors performance.

I am using 3 different processor, all 8 cores with 8 GO of ram.

Code: Select all

processor performance index
AMD FX-8320E  7511
I7 -2600      8214
i7 -4770      9309

This is far from the performance index of the best processor. Run times given here have been usually done on the best i7.
I made benchmarks with the program searching 17s and I have results well correlated with the performance index.

[dobrichev]

B-grids which have all bands 5 or less

With the B-grids - what about only taking 15 clues with a {555,555} pattern - and then adding two clues generally ?

Maybe this doesn't fit well in the model.
several microseconds for +2 x huge number of tests = ages.
From other hand, at this point the process has collected sufficient constraints to discard say 99.9999999% of them in few CPU cycles.

[champagne]

…

Maybe this doesn't fit well in the model.
several microseconds for +2 x huge number of tests = ages.
From other hand, at this point the process has collected sufficient constraints to discard say 99.9999999% of them in few CPU cycles.

Hi mladen,

I agree with you. When blue started with valid band1 x valid band 2, he made a very simple act nearly impossible to beat.

As I wrote in the comments, an optimized filter to clear 9…..% of the cases is a single “and” native instruction.

To beat that, an unseen property of a Sudoku has to be explored.

To be honest, the second key in blue’s process is the GUAs 2/3 intensive use and optimization.

This is something we (blue and me) discovered in the XY27 search, but he really did the best out of it.

BTW, I checked the ED bands 1+2 situation for bands of low rank, Band 9 (index 8) has more ED bands 12 than average. Reversely, the average run time in that area is better than I expected. So at the end, if I am not too bad in the batch control (and without power failure) , I should have results for the top 10 bands 1 when I am back from the week off (say October 16th)

[coloin]

..... what about only taking 15 clues with a {555,555} pattern - and then adding two clues generally ?

Yes i take your point about it not fitting with the model - and i think it might be flawed as not all 6 clues which solve a band in a puzzle - can originate from a 5 clue which solves a band , plus 1 more clue added.

Code: Select all

+---+---+---+
|..5|...|...|
|28.|...|...|
|...|...|93.|
+---+---+---+
|123|456|789|
|764|298|513|
|598|137|624|
+---+---+---+
|657|823|491|
|931|745|268|
|842|961|375|
+---+---+---+  this band 1 is solvable in 5 clues

+---+---+---+
|..5|.1.|..2|
|...|3..|1..|
|4..|...|...|
+---+---+---+
|123|456|789|
|764|298|513|
|598|137|624|
+---+---+---+
|657|823|491|
|931|745|268|
|842|961|375|
+---+---+---+  but all 6 clues in the band 1 are necessary here [ same solution grid]

another angle

search for18s {6,6,6} {6,6,6} and check for a 17
splitting it up into 3 different runs where there is maximum clues in a box of 2,3 or 4 clues

the 2 search would involve all boxes with 2 clues - has advantage that 1 pass only is needed
the 3 search would involve one or more bands being 321 or 330 { this would affect the perpendicular bands]
the 4 search would involve one or more bands being 420 or 411

maybe this fits with the model better ?

Code: Select all

222
222
222  one way

321
213
132

321
222
123

330
123
213   

330
033
303    ways with max 3 in a box   [other isomorphic permutations too ]

411
132
123
   
420
123
123
   
420
132
114
   
420
222
024

411
141
114    ways  with max 4 in a box

510
123
033 

510
132
024

510
141
015

510
114
042

600
033
033

600
042
024

600
051
015

[champagne]

another angle

search for18s {6,6,6} {6,6,6} and check for a 17
splitting it up into 3 different runs where there is maximum clues in a box of 2,3 or 4 clues

the 2 search would involve all boxes with 2 clues - has advantage that 1 pass only is needed
the 3 search would involve one or more bands being 321 or 330 { this would affect the perpendicular bands]
the 4 search would involve one or more bands being 420 or 411

maybe this fits with the model better ?

Hi coloin,

The direct search of a 6,6,5 (in bands) is possible with the released program with minor changes.

The problem foreseen by blue with this case is that the number of valid bands 1+2 grows sharply and to use it’s wording, this could be the show stopper.

Reading your post, I am wondering whether with the last feature (the tailor made brute force and the carry over of the fresh GUAs ) the threat is still there. I could have to re think the option to have a separate pass2 with another entry file.

But this does not change another key option of the blue’s strategy: the sharing of the band 1+2 process with all attached bands 3. Here is a 10 factor (more in the pass 1) that has to be replaced by something else if another strategy is used.

Regarding the “add” strategy, I had long discussions with blue not so far from what you have in mind. I expected good results using only the set of valid minimal bands, then adding clues if necessary. Blue was so strongly convinced that this was not a good strategy that he had difficulty to just read properly what I proposed. When I compared the corresponding implementation with the optimized version of blue’s approach, I stopped the alternative way.

Just to say that any alternative solution has to be nearly implemented to say whether it has a chance or not to beat the released one.

[coloin]

Just to say that any alternative solution has to be nearly implemented to say whether it has a chance or not to beat the released one.

of course ...
splitting it up into sections though might well be faster .... and its better to get it sorted before hitting the button !

i think filling the bands with clues {5,5,5} case needs more thought - i re-evaluated this [ as you may well have done}
I think it only works when all the {3} bands each have 5 disjoint unavoidables - and that will be a very rare solution grid. [MCN-15]
The main thing to note about that search is that you have to know the MCN for each of the 416 individual bands - there has to be a clue in each disjoint unavoidable - but that is another add-on for mladin !

now getting back to yours and blue's {6,6,5} search - with each ED band1and2 extrapolate the 6+6 which solve the individual bands
remove the {6+6} which don't solve the complete band1band2
complete with 5 clues from band 3 {3 options per cell} {gangster} { these are known}
it looks like the ~ x10 improvement comes from the 416/44 ratio and effectively multiple grids are simultaneously searched - is that correct ?

I just wonder if with your method the max 2 clues in a box could be implemented .... and done rapidly ?
There is only one pass in this process....
reduce the options to test further by excluding any {6+6} which has more than 2 clues per box and only attempt to add the band3 {gangster} solutions which have 2 clues in each box, adding 6 clues.
this finds 18s with {6,6,6}

we could then find all 222222222 18s and therefore all 17s with 222222221 box distribution

[champagne]

i think filling the bands with clues {5,5,5} case needs more thought - i re-evaluated this [ as you may well have done}
I think it only works when all the {3} bands each have 5 disjoint unavoidables - and that will be a very rare solution grid. [MCN-15]
The main thing to note about that search is that you have to know the MCN for each of the 416 individual bands - there has to be a clue in each disjoint unavoidable - but that is another add-on for mladen !

I am not sure to have a clear view about your implementation of this. Following blue’s view, we already have all the valid bands with 5 clues and all minimal solutions with 6 clues. Here we don’t use the disjoints UAs (somehow it has been done building the valid solutions) BTW finding the MCN per band is not a problem and you even can think of finding higher degree UAs.

now getting back to yours and blue's {6,6,5} search - with each ED band1and2 extrapolate the 6+6 which solve the individual bands
remove the {6+6} which don't solve the complete band1band2
complete with 5 clues from band 3 {3 options per cell} {gangster} { these are known}
it looks like the ~ x10 improvement comes from the 416/44 ratio and effectively multiple grids are simultaneously searched - is that correct ?

Small adjustment, in blue’s approach, band 3 has always 6 clues. And you are right; the x10 is the average number of grids attached to a given band 1+2 in the pass2. In the pass1 it is around 17 bands 3 per ED band 1+2.
It’s difficult to tell what is the true effect of an average 10 band 3 per ED band 1+2 (in fact 9), but with the last code, each band 3 contributes to a better filtration of bands 1+2 to send to “part 2”

Code: Select all

I just wonder if with your method the max 2 clues in a box could be implemented .... and done rapidly ?
There is only one pass in this process....
reduce the options to test further by excluding any {6+6} which has more than 2 clues per box and only attempt to add the band3 {gangster} solutions which have 2 clues in each box, adding 6 clues.
this finds 18s with {6,6,6}
we could then find all 222222222 18s and therefore all 17s with 222222221 box distribution


A very simple way to go in that direction would be to store only valid bands having no box with more than 2 clues. So I would say “yes it is easy and it would go very fast”.

[coloin]

Yes the 54-plus-n completions inherently uses the UAs in a band - and include minimal and non-minimals....

... all possibilities to speed up the process limiting stacks to 6 clues are used.

so this would mean you are already optimizing the band 3 additions...
although maybe a gain in not searching

222
221
xxx

since

321
122
222

puzzle would still be found [?]

incidentally - i am not sure how you make the band1and2 {6,5} reductions - {50000,4000} is a big product !
surely it cant be quick enough to just - solve and discard if sol >1

choosing band 3 to have 6 clues
Pros
- the number of {6,6} is too large ?
Cons
- only one pass is needed at searching a {6,6,5}
- band 3 search is quicker with 5 clues

and just out of interest ...
for a single band1and2 approx how many {5,6} and {6,5} completions are there per band 3 gangster representative ? and how many valid {6,6}

how do you make sure that you consider every ED band in band 3 gangster - adding a GUA to band 3 excludes some ED bands. Is this your worry ?

[champagne]

Hi coloin,

I am travelling with irregular links to the net. Some quick answers

champagne wrote:... all possibilities to speed up the process limiting stacks to 6 clues are used.
so this would mean you are already optimizing the band 3 additions...
although maybe a gain in not searching

222
221
xxx

since

321
122
222

puzzle would still be found [?]

In your example, one box has more than 2 clues. This is assumed filtered in my answer

incidentally - I am not sure how you make the band1and2 {6,5} reductions - {50000,4000} is a big product !
surely it cant be quick enough to just - solve and discard if sol >1

I answer as if you were here in the general search problem. My rough estimate is an average number of XY over 1 billion as written in the comments. The first reduction is done using UAs located in bands 1+2 and more precisely bit field vectors already settled for each band. This is explained with many details in the comments and a simple “and” on 2 64 bits fields already clear more than 90% of the {valid band1} x {valid band2} XY

choosing band 3 to have 6 clues
Pros
- the number of {6,6} is too large ?
Cons
- only one pass is needed at searching a {6,6,5}
- band 3 search is quicker with 5 clues

In the 6 6 5 (5 clues in band3) the threat is not only the bigger number of XY but more the intrinsic bigger number of finally valid Bands 1+2 (toward the double gangster). As you wrote, the brute force remains a costly process, especially when the solution is unique. I am hesitating to-day because the filter on GUAs is now so efficient that, applied just after the previous one, it can save most of the calls to the uniqueness check for bands 1+2. This can make the 665 search better than a 656 search with another entry file.

and just out of interest ...
for a single band1and2 approx how many {5,6} and {6,5} completions are there per band 3 gangster representative ? and how many valid {6,6}

I keep this for later but just a remark. Having a given ED band 1+2, the gangster in band 3 is unique. The number of attached bands 3 vary.

how do you make sure that you consider every ED band in band 3 gangster - adding a GUA to band 3 excludes some ED bands. Is this your worry ?

Again, I have some problems with the wording. The entry is an ED band 1+2. The gangster in band 3 is just the consequence of missing digits in each column, and the attached bands 3 are all possible fills of the band 3 gangster filtered to avoid redundancy (the total number of bands 3 is here equal to the number of ED solution grids).

In this context, a band 3 is considered if the band 1+2 has been checked valid and if known GUAs did not pass the limits (band 3 number of clues or stack limit).

Then, a brute force for the entire grid can produce a new UA with a corresponding GUA.

And yes, such GUAs added to known ones can filter other ED bands 1+2.

Is this the answer to you point ?? If yes, it’s not a worry, it’s a chance to find so many such GUAs

[champagne]

deleted obsolete

[champagne]

deleted obsolete

[coloin]

Well work in progress - especially if search the band 3 is so quick.

Maybe the 18 clue puzzle search {666,666} > -1 to a {665,665} approach is an option - depending on how long the timings are ?
However - there is a potentai {x6} reduction - If you search all the ED double gangsters with a band 3 search - you will have over searched by 6 times the 5e9 ed grids.
perhaps each ED grid has a {44,44,44:44,44,44} number and this could be a way to avoid the awkward bands in the the difficult grids

[champagne]

Hi again,

Code: Select all

Well work in progress - especially if search the band 3 is so quick.


We have here a double effect

adding fresh UAs in bands 1+2 reduces the number of XY to check
adding fresh GUAs increases the chances to exceed the number of clues in band 3 just considering the GUA2s GUA3s. As bands 3 are checked against this limit before the validity check for an XY (potential valid bands 1+2), the band 3 check is at the end limited in most cases to the extraction of valid GUA2s GUA3s and the validity of bands 1+2 not checked. This is more efficient for "bad cases" that have usually a small number of attached band 3.

Maybe the 18 clue puzzle search {666,666} > -1 to a {665,665} approach is an option - depending on how long the timings are ?

For the 18 clues 222222222 search, (I did not work yet on this topic), the major effect should be the clearing of all 'X' all 'Y' having one box with more than 2 clues. IMO, we would do a direct 666 search, adding the constraint of 2 clues per box in each band 3.

However - there is a potential {x6} reduction - If you search all the ED double gangsters with a band 3 search - you will have over searched by 6 times the 5e9 ed grids.
perhaps each ED grid has a {44,44,44:44,44,44} number and this could be a way to avoid the awkward bands in the difficult grids

The entries of the current process have exactly the number of bands 3 attached corresponding to the catalogue 5 472 730 538. What you mention is the entry file needed for the pass 1 in blue's terminology (more than 6 clues in one band).

[coloin]

I see now ... yes blues pass one - for 7 or more in band 3, you will have to scan the ED 1&2 plus all the bands in 3. Of course with band 1&2 only 5,5 or 6,4 or 7,3 [plus 7] - there are many less combinations than a 6,5 ..

For the 656 search , now I see now how your unhit UA4s in band 1&2 [ i.e. e.g. in box1 and box4] will remove potential combinations. I also realize that you have rightly chosen the bands in 1&2 as the band having less completions with n clues [probably].

My concerns for filling in band 3 are now unfounded - you are fixing the band [ ie not testing every band in the gangster] - therefore revealed GUAs [ with for example only 2 clues in the band 3 [ 4 clues in band 1&2 which are unhit ] mean that there a many less options to try to add clues in band 3 [ band 1&2 are untouched], as well as curtailing any stack which would already have 6 clues ...

So not every ED band 1&2 is searched and not every ED band in the band 3 gangster is searched - but ultimately every grid is searched - for a 656 or 566, and roughly half again are searched for a 656 [ band 3 becomes band 2] .

So 2.5 x sample grids searched for a 656 compared
with timings for
1 x sample grids searched for a 666 [- minus1]
3 x sample grids for a 665
Yes - i can see how the 656 search is probably quicker .

[champagne]

I see now ... yes blues pass one - for 7 or more in band 3, you will have to scan the ED 1&2 plus all the bands in 3. Of course with band 1&2 only 5,5 or 6,4 or 7,3 [plus 7] - there are many less combinations than a 6,5 ..

Right. and if you want to compete against Gary McGuire proof than no 16 clues exists, you can still make it simpler.

I also realize that you have rightly chosen the bands in 1&2 as the band needing less clues

Yes it makes a true difference

My concerns for filling in band 3 are now unfounded - you are fixing the band [ ie not testing every band in the gangster] - therefore revealed GUAs [ with for example only 2 clues in the band 3 [ 4 clues in band 1&2 which are unhit ] mean that there a many less options to try to add clues in band 3 [ band 1&2 are untouched], as well as curtailing any stack which would already have 6 clues ...

Globally yes again

So not every ED band 1&2 is searched and not every ED band in the band 3 gangster is searched - but ultimately every grid is searched - for a 656 or 566, and roughly half again are searched for a 656 [ band 3 becomes band 2] .

The code to create the corresponding entries is not implemented, but you got the point. The target is to have a code providing the right set of band 3 for each ED band 1+2 to consider. The ED bands 1+2 count should be somewhere in between the number of entries in the pass 566 656 and Blue's count for pass 1

So 2.5 x sample grids searched for a 656 compared
with timings for
1 x sample grids searched for a 666 [- minus1]
3 x sample grids for a 665
Yes - i can see how the 656 search is probably quicker .

Here I am not sure to follow you, but, being granted that the 566 + 656 pass on the current entry file is achieved, we can say

You can do in the same pass a 665 search
or do a 656 search on another entry file and from my current results,

I am nearly 100% convinced that the second option is the good one.

Note :
For the 222222222 18 clues search, one pass with the 666 distribution remains the best option to test on the limited current entry file. This is really a minor change in the process.