scan solution grids for 17 clues as of blue

Programs which generate, solve, and analyze Sudoku puzzles

scan solution grids for 17 clues as of blue

Postby champagne » Thu Aug 31, 2017 4:13 pm

Permanent url to reach the documentation

old overview

comments on the version used for pass2 (665 distribution)

gangsters and UA collectors

phase 1 selecting bands 3 having potential
phase 2 processing bands 3 having potential
entry files creation
Tests and results analysis



.zip files available for downloads
blue's "pass 1" search of 17 clues with a band/stack >= 7 clues here sk17p1_v3a.
blue's "pass2" distribution 665 here sk17p2a_v1_0.
to come readme plus test file plus comments
16 clues search here sk16.
=============================================================================================================================

Hi All,

blue announced here fantastic results for an exhaustive search of 17 clues puzzles.

We lost contact with blue several months in March 2017 after he gave through pm more information about the process to mladen Dobrichev and me. We don't have the code used by blue. When blue came back later, he had no more interest on this topic, so we stay with the information delivered in 2017.

I worked on blue's findings and tried to achieve similar performances on one of the 2 pass defined by blue ; 17 clues sudokus having no band with more than 6 clues.

The search of 17 with a band having more than 6 clues is done. I have now the program to search 17 with the distribution 665.

It seems that blue expected new 17. I am not sure that he is right and it could be that the scan shows that all 17 are known.

This would not be recognized by the community until several guys have carefully checked the code and somehow certified that it is "bug free". As nobody showed fresh interest to share the project, I release code and comments "just in case".

As the project includes topics that can be studied independently, I published first an overview of the project, then, piece after piece, all independent parts (eg: the program includes a code creating on the spot part of the solution grids that can be studied separately ... ). The first overview is somehow outdated, but still gives an idea of the general design.

The program searching the 665 distribution has been significantly improved compared to the closed one (band >6 clues). This is the code described in several chapters.
Last edited by champagne on Sat Jun 15, 2019 8:26 am, edited 16 times in total.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Thu Aug 31, 2017 4:40 pm

In my files I have 12498 "665" "17 clues puzlzes" corresponding to what could be found in the process described here.
The table below shows how they should appear in the process

The first column "1-416" is the order for the generation of entries, from the lowest count of valid 6 clues for a band to the highest count of valid 6 clues for the band
The second column is the band number 1-416 in the classical min lexical order
The total count1+count 2 indicates how many 17 clues are known for that entry

count1 gives the count of 17 clues that should come with the current entry generator
count2 is for 17 clues that would be 665 (5 clues in band3) in the current process. These puzzles will be produced with another entry generator to appear as 656 (6 clues in band3)

Note: the split count1 count2 is not reliable if band 2 and band 3 have the same rank
note2: high rank corresponds to tougher cases for the process (huge number of valid bands 5 and 6 clues)
Hidden Text: Show
Code: Select all
rank   band   count 1   count2
3   1   0   5
4   413   1   1
5   254   1   2
6   307   0   3
7   225   6   15
8   33   1   8
9   48   8   14
10   219   2   5
11   101   3   4
12   240   1   0
13   45   2   8
14   67   2   3
15   247   10   5
16   105   2   6
17   104   0   3
18   83   2   6
19   183   6   13
20   100   2   13
21   133   0   2
22   289   1   2
23   238   1   11
24   4   23   29
25   415   1   3
26   140   6   15
27   72   16   20
28   93   9   17
29   116   20   20
30   122   6   7
31   54   6   11
32   2   76   79
33   412   14   9
34   414   3   3
35   220   12   10
36   74   12   10
37   223   14   22
38   232   11   21
39   233   13   17
40   84   4   8
41   32   6   7
42   115   18   31
43   109   17   19
44   302   2   5
45   259   5   14
46   152   18   24
47   218   21   8
48   226   11   14
49   230   10   15
50   253   2   5
51   309   4   6
52   241   4   9
53   252   10   32
54   305   13   26
55   16   0   3
56   222   17   33
57   229   23   34
58   160   16   25
59   294   24   25
60   39   33   37
61   46   14   18
62   124   11   9
63   217   16   17
64   260   15   22
65   171   21   30
66   8   8   9
67   92   17   27
68   196   22   26
69   228   13   23
70   137   6   3
71   119   11   28
72   35   26   18
73   49   18   34
74   135   20   31
75   136   21   34
76   59   23   33
77   62   19   35
78   47   21   28
79   127   19   26
80   187   19   40
81   192   24   22
82   245   4   9
83   193   10   16
84   239   12   28
85   88   29   30
86   148   5   6
87   213   10   9
88   293   21   31
89   256   7   13
90   306   15   17
91   57   33   44
92   90   30   34
93   36   10   23
94   94   15   18
95   51   18   39
96   149   11   9
97   314   9   10
98   44   23   16
99   66   24   28
100   112   21   28
101   231   14   37
102   221   15   37
103   234   21   26
104   69   27   26
105   287   7   5
106   82   19   22
107   131   23   24
108   95   27   35
109   71   17   16
110   98   8   10
111   87   22   29
112   132   16   17
113   91   18   25
114   97   10   6
115   114   13   8
116   81   39   23
117   58   32   34
118   108   25   22
119   110   17   29
120   235   5   17
121   102   15   22
122   151   19   22
123   242   20   20
124   246   28   26
125   282   29   29
126   75   9   10
127   129   8   2
128   227   18   33
129   189   13   14
130   77   30   31
131   103   26   33
132   99   28   36
133   42   18   15
134   9   17   32
135   416   1   1
136   236   33   35
137   60   31   40
138   138   42   48
139   182   17   16
140   111   18   38
141   214   5   6
142   78   15   43
143   126   24   35
144   43   31   34
145   188   19   22
146   195   12   23
147   295   34   27
148   113   23   27
149   76   24   34
150   202   28   38
151   96   38   46
152   79   37   37
153   167   8   14
154   175   11   9
155   63   29   29
156   86   20   35
157   303   10   6
158   250   10   9
159   284   7   16
160   298   5   8
161   324   26   33
162   327   14   32
163   52   27   36
164   3   30   45
165   398   11   9
166   80   38   30
167   191   20   13
168   291   26   24
169   272   16   25
170   38   36   41
171   174   13   13
172   275   8   14
173   249   25   49
174   269   19   25
175   41   15   33
176   286   14   15
177   186   26   32
178   198   14   34
179   266   8   30
180   73   25   20
181   34   24   27
182   123   14   23
183   55   26   37
184   37   24   26
185   10   101   110
186   411   11   16
187   64   26   31
188   310   4   7
189   243   31   25
190   6   199   198
191   410   11   27
192   141   18   16
193   161   16   18
194   163   20   26
195   264   21   26
196   268   23   26
197   106   13   19
198   267   16   32
199   290   14   20
200   278   18   17
201   172   20   18
202   203   23   32
203   280   8   16
204   255   7   3
205   304   9   3
206   271   17   23
207   18   60   68
208   21   82   77
209   397   9   13
210   400   6   14
211   402   18   20
212   406   10   32
213   5   85   84
214   393   12   8
215   403   14   10
216   12   119   113
217   283   18   13
218   157   12   27
219   244   9   23
220   292   13   23
221   85   19   38
222   251   6   12
223   308   10   9
224   117   33   36
225   128   16   22
226   144   13   7
227   61   28   41
228   158   15   17
229   336   12   6
230   204   26   16
231   53   12   9
232   121   25   33
233   274   6   10
234   70   25   21
235   205   16   21
236   257   16   19
237   139   14   11
238   164   9   27
239   134   22   26
240   323   5   8
241   335   10   20
242   159   13   20
243   347   17   25
244   331   11   24
245   337   16   18
246   156   4   17
247   19   52   59
248   395   8   10
249   409   8   13
250   13   27   17
251   299   19   26
252   297   13   22
253   190   7   7
254   326   21   7
255   56   33   24
256   68   16   23
257   125   11   22
258   332   7   16
259   89   24   22
260   208   9   8
261   142   5   6
262   150   8   8
263   146   12   16
264   277   10   7
265   288   5   3
266   216   14   20
267   317   8   11
268   258   16   16
269   300   14   12
270   263   16   18
271   346   6   7
272   261   13   15
273   281   5   2
274   15   63   73
275   166   15   11
276   14   64   60
277   173   11   17
278   330   9   20
279   147   3   10
280   197   8   17
281   65   20   16
282   130   14   11
283   184   11   12
284   153   10   17
285   325   6   7
286   178   17   12
287   279   3   5
288   40   11   14
289   181   7   11
290   320   9   9
291   341   12   11
292   362   8   11
293   372   8   9
294   118   13   14
295   107   15   13
296   215   5   13
297   318   5   7
298   360   7   2
299   313   7   4
300   377   6   4
301   50   15   10
302   154   9   10
303   301   7   5
304   344   4   7
305   262   6   8
306   285   12   9
307   194   5   2
308   23   20   25
309   408   1   4
310   334   2   4
311   120   9   9
312   180   10   6
313   375   2   3
314   367   8   11
315   370   6   11
316   312   9   7
317   339   7   13
318   379   10   9
319   11   36   27
320   407   4   5
321   210   1   2
322   270   5   6
323   329   2   5
324   212   3   4
325   343   2   3
326   265   5   8
327   143   7   10
328   179   7   7
329   248   6   11
330   145   9   9
331   200   6   6
332   169   7   12
333   177   7   11
334   342   7   5
335   316   4   3
336   338   3   9
337   333   2   6
338   373   5   2
339   185   5   8
340   311   3   8
341   392   1   3
342   162   5   6
343   207   3   7
344   340   6   3
345   276   2   2
346   322   4   3
347   209   10   3
348   7   8   6
349   296   3   2
350   328   6   3
351   391   2   1
352   168   4   13
353   170   6   7
354   387   3   7
355   199   6   4
356   20   25   23
357   399   3   2
358   206   3   6
359   155   2   4
360   22   21   16
361   24   8   14
362   405   1   3
363   273   2   1
364   315   4   1
365   176   4   1
367   211   1   3
368   201   0   3
369   371   3   2
370   384   0   1
371   388   0   1
372   321   0   1
373   319   0   1
378   368   1   1
380   376   1   3
381   165   2   2
382   363   1   0
384   356   0   2
387   17   1   1
388   345   1   1
390   361   1   1
391   357   1   0
392   25   2   7
395   28   5   1
398   353   0   1
404   369   1   0
      5593   6905 =12498 known 665 17 clues sudokus


Following a table of 20 entries for the 656 566 pass. These entries have all a high number of valid bands 1+2 (average 555 000) after filters and a very bad run time in thefirst version "part 2" process.
average 4 seconds to produce valid bands 1+2
average 51.6 seconds run time

This is a good file to study "part 2" optimization


Hidden Text: Show
123456789457189236896273154348562971571894623962731548;50127
123456789457189623689732415268943157394517862715628394;57893
123456789457189623986327154245631897639578241871294536;52034
123456789456789123897231564214867935539124876678593241;50847
123456789457189326689723145296531478714862593835947261;50112
123456789457189236896723514389541627615297348742638195;55393
123456789457189263698273145245731896319862574786594321;99818
123456789456789123789231645218367594637945812945812367;51831
123456789457189326689372541364295178872613954915748632;55206
123456789457189326689372541231568497768934215945217863;63394
123456789457189236896327514315768942689241357742935168;67926
123456789457189236968732154234567891589214367671398542;54940
123456789457189236689732154314978625592613478768245913;81145
123456789457189236689327451534792618792861345816543972;52847
123456789457189236968237154285761493394825671671943528;62706
123456789457189263869327451248613597395748612716592834;51706
123456789457189263689273541295348176368517924714692358;51691
123456789457189263689273541235948176764315928891627354;50534
123456789457189263968327541284563197395718426716942358;52706
123456789457189623896327415571932846682745391934618572;58019


next table is the new set of "bad cases" out of the second version of the sample. the first item was in the previous table.
The corresponding 26 entries have >= 10 seconds of run time with the revised code including a tailored made brute force for band 3

Hidden Text: Show
123456789457189623896327415571932846682745391934618572; 87; 9872;t=10245
123456789457189623896237415271394568534862971968571342;104;11724;t=13671
123456789456789123798132465234578691861294537975613842;133;14434;t=10300
123456789457893612986217354234781965578629431691345827;134;14437;t=11920
123456789457893612986217354235968471698174523741532968;134;14440;t=15287
123456789457189236986327154234761895579842613861935427;137;14698;t=10960
123456789457189236689273541294315678571864923836792154;143;15195;t=10631
123456789457189263869237415298571346514623978736894521;144;15278;t=10044
123456789457189263896327415382615974715948326964732158;149;15739;t=10339
123456789457189623698372154362847915715923468849615372;168;16882;t=10670
123456789457189263698732451345978612782613594916245837;176;17328;t=11624
123456789457189623689273145534712968792568431816394572;188;17952;t=12977
123456789456789123789132564295378641348561297617294835;189;17995;t=10879
123456789456789123789132564247963851538217496691845372;189;18013;t=10870
123456789456789123789132564348217956672945318915863472;189;18017;t=14954
123456789456789123789132564248591637631827495975364812;189;18032;t=10540
123456789457189263689732145516924378792863514834517926;192;18174;t=13143
123456789457189623869237145392741856574863291618592437;199;18527;t=13178
123456789457189263896327451261538974538794612974612538;201;18602;t=10555
123456789457289631986137254264593817579861342831724596;208;18791;t=10807
123456789457189236689723145276394851531678492894512367;254;19913;t=13327
123456789457189263896372451382945176615837942749621835;259;19999;t=11789
123456789457189263689237451348592176562871934791364825;260;20014;t=11266
123456789457189623698237145731928564865743912942561378;269;20111;t=13385
123456789457189623689732514592617348716348295834925176;271;20132;t=10354
123456789457189632689273145264518397871932564935764218;339;20358;t=10129
Last edited by champagne on Fri Oct 06, 2017 6:17 am, edited 4 times in total.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

scan solution grids for 17 clues new design

Postby champagne » Thu Aug 31, 2017 4:41 pm

In blue's solution to find 17 clues in solution grids, the first step is to combine all valid solutions of size n in band 1 to all solutions of size p in band 2 with the restrictive condition

n+p= 1 with a distribution 566 656
n+p<=10 if the band 3 has >6 clues

In this process, the solution for band 1 or band 2 is usually not minimal.

I tried and failed to built an alternative process based on the "minimal" solutions for bands 1 and band 2.

As the 566 656 distribution remains very slow for the power available on my side, I am still looking for a better process.
Looking for 18 clues puzzles having a band with 2 clues, I saw a new possibility to run this scan.

The concept is relatively simple for anybody having analyzed the current search.
It's accepted that no 17 exist having a band with 2 clues

Band1 and band 2 are alternatively band a and band b where

band a had a maximum of 5 clues.
band b is filled to reach the expected count of clues in bands 1+2

For each "valid band a" (3_5 clues)
Bands 1+2 Uas still valid are extracted
Band 2 is processed in the same way as bands 3 in the current process
and the process for band 3 is unchanged

The key point, seen in the search of 18's having a band with 2 clues, is that many UAs for bands 1+2 are left with only clues in a mini row, so most of the "valid bands b" can just be ignored

This post will be updated with more information along the implementation and test of the code.
Implementation starts with a loop on the first 3 clues in band a.
Last edited by champagne on Mon Jul 22, 2019 10:35 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

566 distribution V3

Postby champagne » Mon Sep 04, 2017 1:04 pm

I dont' delete the previous post, although it is now obsolete. I know that I would have a bug to fix in it, but I am now working on a third version.
Here is a short description of the third version, with comments version 1 version 3.
This is for the process specific to the 566 656 distribution.

Entry file generator and UAs collector:

In this part, we have no significant changes.
The band expansion has been modified to have a 3 clues index ( see 3X3Y steps below)
An attempt has been made to add in the UAs generator UAs bands 1+2 and GUAs sockets to produce and use uas limited in one band to the pattern
Code: Select all
a..b
.ba.

This worked well but with a limited effect in bands 1+2. For the guas 4 columns sockets, the price to use it was to high. The idea could come back in another context.

Bands 1+2 process till the "go band 3"

The previous 2X2Y or 2X3Y steps have been replaced by 3X3Y steps.
The outer X loop is just used to produce reduced tables.
At the 3X3Y level,for bands 1+2 the number of valid UAs is generally below 128, the code accepts 2x128 as upper limit.
A 1x128 and a 2x128 process have been extended to optimize the "matrix" sequence combining a valid X to a valid Y for the relevant sub files.

The next step checking the validity of the XYs passing the first filter is slightly different depending on the number of bands 3 attached.
With a small number of bands 3 (1-4 in the code released), the program first checks if there is a band 3 to apply, considering the GUAs sockets status.
With more bands 3, the probability to have at least one band 3 to check is too high. Applying first the brute force saves time. Then, the brute force check deliver a file of XYs passing the brute force (still an attempt to optimize the cache effect).

Band 3 process


Limited changes here, but many small adjustments.

The band expansion has been revised and is applied now as soon as the main process does not show a positive picture just considering the critical status ans the UA structure.

The critical process has been revised to avoid non compulsory calls and the brute force calls in this area have been limited to the test of the 17 clues.

Small adjustments have been done in the other functions of the band 3 process.
Last edited by champagne on Thu Nov 07, 2019 10:37 am, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Mon Sep 04, 2017 9:22 pm

Hi Champagne,

Thank you for the explanation.

Is the covered so far part of the process (finding case 2 17s having givens per band distributions of 6+5+6 or 5+6+6) intended to discover a puzzle having such bands distribution but different givens per stack distribution, say 7+5+5? Or only puzzles with 6+6+5 distributions in both band and stack orientation are intented to be found?

A secondary less important question is do you have clues that larger cache tables became ineffective due to the processor architecture, or the reason is the increased number of cycles for building and using them as they grow?
dobrichev
2016 Supporter
 
Posts: 1850
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby champagne » Tue Sep 05, 2017 11:10 am

Hi mladen,

dobrichev wrote:Is the covered so far part of the process (finding case 2 17s having givens per band distributions of 6+5+6 or 5+6+6) intended to discover a puzzle having such bands distribution but different givens per stack distribution, say 7+5+5? Or only puzzles with 6+6+5 distributions in both band and stack orientation are intented to be found?



Let me answer in a different way. Blue's experimentation shows that the specific search of puzzles having a band3 with 7 clues or more is faster than the 656 566 search. Assuming the "pass >=7" done, all possibilities to speed up the process limiting stacks to 6 clues are used. So the answer is "no, the released process will not find 17s with another distribution than 665". And, relying on blue findings, I think that it would be a waste of time to open the process to be redundant with the pass"band3 >=7 clues".


dobrichev wrote:A secondary less important question is do you have clues that larger cache tables became ineffective due to the processor architecture, or the reason is the increased number of cycles for building and using them as they grow?


IMO, this is not a secondary point.

I am by far not expert in cache optimization and I am convinced that we have to investigate other possibilities. I have seen a huge improvement in the "part 1" process (delivery of valid bands 1+2) when I activated a cache optimization frame, As I wrote in the comments, I have in mind something likely better (smaller x and bigger y chunk size plus piling XY to test after the first filter in a way closer to blue's buffer). I differed the test for several reasons:

I had first to come to an acceptable process for the part 2 (processing valid bands)
I committed myself to release the code as it is within the next 3 weeks.
And the improvement will be applied to a part of the code than can be run already for cases with a limited number of valid XY "as it is".

And clearly, other options can be suggested by experts in that field.

The next release of code will be limited to all preparation tasks (hope to do it to-morrow, I still have a lot of work to write the overview for that part of the process) and will be followed quickly by the outer loop of the search process, voluntarily limited to the point where the cache optimization plays a role. So in few days, others will be in a position to test other cache options.

BTW, if the release of the preparation tasks must be done first, digging in the corresponding code is not so important. The most important point is to have in mind the output of that phase.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Wed Sep 06, 2017 12:50 pm

deleted, now obsolete
Last edited by champagne on Fri Sep 08, 2017 8:01 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby coloin » Thu Sep 07, 2017 5:59 pm

As I understood blue's method - it will only not find 17s which have 7**,7** band counts both horizontally and vertically.
coloin
 
Posts: 2381
Joined: 05 May 2005
Location: Devon

Re: scan solution grids for 17 clues as of blue

Postby champagne » Thu Sep 07, 2017 7:05 pm

coloin wrote:As I understood blue's method - it will only not find 17s which have 7**,7** band counts both horizontally and vertically.


Hi coloin,

blue covers all the field in two "pass" and gave results on the 100 grids sample for both pass.

In the so called "first pass", blues tests each possible band of the catalogue as band 3 for 7 clues or more.
Once this done, all non redundant 17 can not have any band/stack with 7 clues or more.
So, in "pass 2", the option described here, the only possible distribution is 2 band/stacks with 6 clues and the third one with 5 clues.

BTW, as noticed blue, the first pass is enough for the proof that no 16 clues puzzle exists.

either the 16 clues puzzle has a band with 7 clues or more and it would appear in pass one
or the puzzle has a 556 distribution, but then a 557 clue not minimal should come

So when blue wrote that this process is 350 times faster than the Gary McGuire process (350 from my memory) he refers to the run of the "pass1"

Here, for reasons explained in the opening post, I am working on "pass2 "the 665 distribution, and more precisely, on the 566 and 656 distribution with
band 1 valid 6 clues count <=
band 2 valid 6 clues count <=
band 3 valid 6 clues count.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby coloin » Thu Sep 07, 2017 10:20 pm

Gosh ..... that is a clever one ... well done blue . And thanks for explaining that.
Pass two - this means that only clues which fall into a pattern {665,665} need to be tested ....and in these there is always a band crossing with 5 clues total in each band
coloin
 
Posts: 2381
Joined: 05 May 2005
Location: Devon

Re: scan solution grids for 17 clues as of blue

Postby champagne » Fri Sep 08, 2017 1:34 am

coloin wrote:Gosh ..... that is a clever one ... well done blue . And thanks for explaining that.
Pass two - this means that only clues which fall into a pattern {665,665} need to be tested ....and in these there is always a band crossing with 5 clues total in each band

Right, but as you don't know which stack has the 5 clues (at least I did not see how you could), the stack control in the process just takes care that all solutions with more than 6 clues in stack are filtered. This is done mainly processing bands 3, the last part of code to be released (say in one week at best, preparing the comments is a hard task for me with my poor English).
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Fri Sep 22, 2017 2:43 am

The last release of the first version of the code doing the 665 656 search of 17 clues puzzles is now uploaded on my website.

The corresponding comments have been added to the documentation (URL in the first post)

The release can be downloaded at the following place here

The zip file contains

. the source code in the directory src
. the project definition used on the platform microsoft visual studio
. a short readme file


The readme file contains comments on the status of the attached code.

Next step on my side if to run more tests, to implement if possibles improvements foreseen on specific parts of the process,
then to release the first version to be run for the search, with the only .exe that I can produce, a windows .exe

The released code contains 2 different version of the chunk split, first tests show a minor change in the performance.

Note 1 : this is a 64 bits code using 128 bits registers and intrinsic instructions.
Note 2 : another entry generator is required to exchanges bands 2 and 3 of the current entry generator and avoid to run a 665 case
Note 3: a different program is needed with the appropriate entry generator to process the "pass 1" in the blue terminology, with more than 6 clues in band 3.


EDIT Sept 22

Regressive tests on the known 17 is now ok, but 2 bugs were fixed in the fresh code
The sample 1000 bands 1+2 130000 bands 3 was run with changes (chunks 256 x256)
The average run time per entry was down to 6.2 seconds per entry, slightly below 0.5 second per solution grid.
More tests are on the way (the test on the sample for the alternative chink organization is not yet ready).
The fixed code will be released with a .exe on saturday, 23th my dead line.

A table showing where known 665 17 will come has been added in post 2 out of the 12498 known 17 with a 665 distribution, about 5593 should come with the current code. The rest requires a band2/band3 permutation to stay in 6 5 6 mode (the 6 6 5 mode is expected to have a very bad run time).

blue's pass1

To implement blue's pass 1 (band 3 having more than 6 clues), we must have an entry file with all bands/stacks of the solutions grids appearing once as band 3.
The corresponding 983 959 110 ED bands 1+2 can be easily created with the current outer loop just ignoring the band3 generation and the clearing of ED bands 1+2 with no band 3 (checked).
As a consequence, only the band 3 generator has to be changed to apply the outer band to blue's pass 1.

Next week the first runs will start. Free cycles are welcome
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Wed Sep 27, 2017 12:44 pm

This is my deadline to release the promised code.

the regressive test on the known 17 showed small bugs in the fresh code, now fixed,
and the big sample test was reworked, showing small improvements.

The documentation has not changed since the previous post. (URL in the first post)

The release can be downloaded at the following place here

The zip file contains

. the source code in the directory src
. the project definition used on the platform microsoft visual studio
. a short readme file
. sk17p2a.exe executable code under windows
. _zbad50.txt a list of 20 puzzles giving very bad run times in pass 2.

The _zbad50.txt file is the list of entries with a run time over 50 secondes in the pc where was run the test with 10 000 entries (my working station has s lightly better processor 10% faster)
First investigations show that more than 90% of the run time is in the process of bands 3.("part 2")

I'll use this file in the next days to see if easy improvements can be done in the code for "part 2"

2 versions of the chunk split are in the code, with a very weak effect on the overall performance.
Optimization of the "part 1" is now on the bottom part of the todo list. The priority is to see what can be done to speed up "part 2";


The _zbad50 file is also available in the post 2 of this thread.to have in mind the output of that phase.

EDIT September 27th

I started the tailor made brute force for the processing of a band 3.

Doing so, a bug in the G17XY::Go_ValideB12() process showed up, with a bad selection of the band 3 currently processed. This will be fixed later in the released code.

The main point is that the tailored brute force can now produce new GUA2s GUA3s available for the downstream process.

This is something likely done in blue's code but not clearly described in the exchanged posts.

A new GUAs in one of the GUAs sockets can be reused in the next 2X2Y steps
A new GUA2 GUA2 socket for a given band can be reused for other bands of the same XY
A new socket (more than one mini row in the gangster band 3) can be reused for other bands of the same XY

But all this requires to extend the frame to the handling of these fresh UAs in gangster mode. I hope to prepare and test the corresponding code within one week. Then a new release will take place, with the above bug fixed.

Note : what will be done here is very similar to what is already implemented in bands 1+2. The main difference is in the constraint to transform the fresh UA in a gangster socket.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby coloin » Sat Sep 30, 2017 3:39 pm

champagne wrote:Optimization of the "part 1" is now on the bottom part of the todo list. The priority is to see what can be done to speed up "part 2";


ok so "part 1" is almost achievable

"part 2" - the {665,665} is problematic

Split up the the grids into
A-grids which have a band needing a 6
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 ?

C
coloin
 
Posts: 2381
Joined: 05 May 2005
Location: Devon

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sat Sep 30, 2017 8:52 pm

coloin wrote:
champagne wrote:Optimization of the "part 1" is now on the bottom part of the todo list. The priority is to see what can be done to speed up "part 2";


ok so "part 1" is almost achievable

"part 2" - the {665,665} is problematic

Split up the the grids into
A-grids which have a band needing a 6
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 ?

C

Hi coloin,

First a reminder of blue's terminology. I try to stick to it, but I confess that this is not easy.

Blue split the process in 2 " pass" corresponding to 2 different programs

"pass 1" where the band 3 has >= 7 clues
"pass 2" where no band/stack can have >= 7 clues

Within any pass, blue split the process in 2 "parts"

" part 1" finding all valid bands 1+2
" part 2" processing all bands 3 attached to a valid band 1+2.

I am working on "pass 2" and I see now "part 1" of "pass 2" as "close to the optimum in this process".

I expected (and the first implementation seems to confirm it) a possible huge improvement in a better use of the brute force in the "part 2" of the "pass 2".

I have some difficulties with your wording in this context.

The case 557 is part of "pass 1" in blue's programs.
So, in "pass 2" we have a 665 distribution in both directions (bands; stacks).
In blues process, the band 3 has always 6 clues but he has ~900 millions ED bands 1+2.
Having the band 3 with 5 clues is likely a bad choice. The only way to force 6 clues in band 3 is in some way, to use the 900 millions ED bands 1+2.
I have currently a "pass 2a" with ~600 millions ED bands 1+2, but to test all cases, it would be necessary to test the case with 5 clues in band 3, so I'll have later to finish the pass 2 with a different feed, switching bands 2 and 3 to put the band with 5 clues as second band.
champagne
2017 Supporter
 
Posts: 7354
Joined: 02 August 2007
Location: France Brittany

Next

Return to Software