Bands and low-clue puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Re: Bands and low-clue puzzles

Postby coloin » Thu Mar 10, 2016 9:16 pm

champagne wrote:I try to decipher your post to see where we are in line and where we are not

Analysis has revealed that the crossing bands wont help us ...

However i see what you are doing ....

I think that there will be considerably less ways to complete band 3 - given any gangster band in band 1 around 3 million ways only ? [ box 7*8*9 - 8640*300*8 = ~20 million ] [ but this can be reduced x6 ]

Yes the 3 clues could be picked out from these bands - as there are only 432 patterns which are valid - edit ah yes there will be x6 more .....hmmmmm.

Picking the 5 clues from band 2 would be straight forward [ each loci has only 3 options]

I can see great reductions - if you ignore band 3 completions which cant be done in 3 clues ? 90 %
... :!: - but we do know all the ways that any particular band of the 416 that can be covered in 3 clues ....
C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby champagne » Fri Mar 11, 2016 5:22 am

coloin wrote:Yes the 3 clues could be picked out from these bands - as there are only 432 patterns which are valid - edit ah yes there will be x6 more .....hmmmmm.


I don't catch your point for the edit in blue.

coloin wrote:Picking the 5 clues from band 2 would be straight forward [ each loci has only 3 options]
C


tight, except that you can get many valid pairs { band3; gangster} as shown in the frequency table. In theexample, we have 381 valid pairs, somewhere in the middle.

Globally, in the example, we have 1900 possible band3, but 1740 only can be generated out of the valid band 3.
In blind mode, each pair would generate about 3x2x3x2x3=108 to test (considering the 5 clues pattern) .
108 * 381 is far above 1740, so we need filter keeping in mind that we want to avoid calls to the brute force.

So applying directly the generation for each pair can be costly. The minimum would be to work in 2 pass: One pass setting a flag for each

coloin wrote: :!: - but we do know all the ways that any particular band of the 416 that can be covered in 3 clues ....
C


We know that for the canonical minlex form. our band 3 gangsters are never in the canonical form, and this is not a critical path, that's why I preferred to use the brute force.


Back to our example, and to the gangster equivalence I indicated.

The 5 clues pattern has clues in each box, that is not the best shrinking situation, however, the number of pairs was reduced from 381 to 66.
(always sugject to..) this is fresh code.

In that list, 24 pairs have no equivalence, so we could have to expand all or part of them.

This is where I am, looking for more possibilities to filter.

Important point, the reduction step is valid for any pattern having the clues shared in the same columns.
Sorting the file in an appropriate mode, the reduction has to be done once only for the lot.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Bands and low-clue puzzles

Postby champagne » Tue Mar 15, 2016 5:35 am

Extrapolation (always dangerous) of the results of my current test, one could hope that using the bands properties, the number of calls to the brute force in the generation 27 + 5 +3 could be divided by 1000 or more.

If this is confirmed, and if the price to pay to filter is low (I am still working on it to improve the process), it would give a new potential to that search to detect new 17's or establish that we have all of them
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Bands and low-clue puzzles

Postby coloin » Tue Mar 22, 2016 5:11 pm

I see now how you can filter the grids that you need to check...
if the gangster combination in band 2 or 3 cannot be defined by the clues [27plus5plus3] then there will be multiple solutions
good luck with it - it seems such a simple task to have 5 plus 3 clues !!!

champagne wrote:I don't catch your point for the edit in blue.

if you have 432 ed ways to place 3 clues in a band, in 20 million bands
is the same as 432 ways x6 to place 3 clues in 20/6 ed million bands
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby coloin » Tue Mar 22, 2016 5:45 pm

coloin wrote:Anyhow it seems there are way more possibilities than we can ever search .....
It would be interesting to see what proportion of B12347 is solvable in 5 clues, 6 clues, 7 clues [with an empty box 1].
I looked through many of the 17-puzzles but i could not find a puzzle with 6 clues in B12347 - but that is too big a search in any case.
There will be some B12347 which cant be completed in 7 clues - ie have 8 unavoidable clues .....

Well i did a bit of research - and as ever there are too many possibilities to even consider the cross ways approach ...

Number of ED B12347 - around 18 million
Number of ED B5689 - around 12 million

It seems that for a given B5689
eg this one
Code: Select all
+---+---+---+                                   
|...|...|..4|                                   
|...|...|..6|                                   
|...|...|..8|                                   
+---+---+---+                                   
|...|124|685|                                   
|...|375|129|                                   
|...|689|437|                                   
+---+---+---+                                   
|...|537|861|                                   
|...|418|972|                                   
|178|296|543|                                   
+---+---+---+
..............................124685...375129...689437...537861...418972...296543  -  244880 sols
col9 and row9 completed trivially 
there are 6780 grid completion solutions - of which 5972 were ED

From this single B5689 I found
558 ED 36plus5 puzzles - from 449 ED grid solutions [34 5plus36 valid ED patterns found]
929869 ED 36plus6 puzzles - from 5731 ED grid solutions [417 6plus36 valid ED patterns found]

This means that
about 7% of B12347 can be completable in 5 clues
over 95% of B12347 can be completable in 6 clues - and there are many puzzles per individual band crossing ...
And even more ways to add 7 clues !!

C
coloin
 
Posts: 1638
Joined: 05 May 2005

alternative process to prove no 16 and find all 17s

Postby champagne » Mon Apr 25, 2016 8:16 am

alternative process to prove no 16 and find all 17s

Following the positive results on the 27 + X + Y using the facts that in a valid puzzle each band/stack must be solved against the corresponding gangster, I worked on a possible application to the search of new 17s if any or another way to prove that no 16 exists.

Here is a possible way.


Code: Select all
9..8......8....7......6..5.6.......8..4..9......3..6...3......9....2..4......7...

band 1  912875463586234791347961852   123456789457289631698317254   381   3
band 2  653742918824619537179358624   123456789457289163896731524   358   3
band 3  435186279798523146261497385   123456789457189623689732541   261   4

stack 1 312874965695132748478956213   123456789456789132789231546   23   3
stack 2 541298637736415829829763154   123456789456789123789132564   5   4
stack 3 267349581184527396953681472   123456789457189263689732145   160   4

123456789456789132789231546 i=23
nua=43 n1=12224
mladen 41



The first line is an existing 17 taken as start. A valid 17 is a kind of worst case in such a process, so the average situation will be much better than in that case.
The valid 17 has been solved to get the solution grid.
Next three items are the bands and stacks extracted from the solution grid.

For each item, we have
the values in the grid (27 cells in a band format)
the corresponding minlex values
the index of that minlex value in the 416 table I use
the minimum number of clues required to have a valid band in that "416"

In that situation, the best is likely to work on a morph of the puzzle with the final band order "stack1;stack2/stack3"
The target being to have a maximum of "minimum number of clues" if the pending bands

Doing so, we start with the "416" index 23 of my table (likely 24 in mladen's table)
In another program, I checked that "416" and got the following results:

I generated all UA's necessary to have all valid bands up to 9 clues. I have 43 UAs against 41 in mladen's table, but my list has to be cleaned for possible redundancy.
More interesting, I got only 12224 valid band 1.

Knowing that all band 1 with 9 clues can only be combined with 4 clues in band 2 and 4 clues in band 3 to stay within the 17 clues limit, This seems to be a very promising way to go.

The basic idea is to have the table of UA's prepared separately, although the cost to produce it is not that big for a batch of thousands solution grids (less than 4 seconds with my process for the 416 minlex starts)
then to morph a solution grid to the optimal form for the process and finally to extend bands and to check all the "band solutions against the stack".

Most of the solutions will be cancelled within the band expansion except, may be, as here, for solutions grids containing a valid 17.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

bands and high clues puzzles

Postby champagne » Tue May 03, 2016 9:57 am

A side effect of the work I am doing on the thread topic.

If I remember properly, Mladen Dobrichev searched high clues puzzles using generation starting from n-1 clues.

This is not a topic on which I worked, but if we consider Bands minimal solutions of size "n"
I find only 2 of the "416" producing minimal bands with 10 clues or more and 13 "416" producing minimal 9 clues bands.

With so many clues, it would be surprising that the final valid puzzle requires band redundant clues.

IMO mladen high clues puzzles should mainly uses theses bands(may-be exclusively these bands for the highest number of clues).

,
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Bands and low-clue puzzles

Postby dobrichev » Tue May 03, 2016 7:03 pm

Statistics on band frequencies in the first 46294 of the 17s are in the columns "BF7 In17 BF17" in this topic's opening post. There are favorites, but the rightmost column "BF17/7" demonstrates no clear relationship to the low-clue band completion. Every band (of 416) and respectively gang (of 44) produces 17-given puzzle.

For high clue search I used 36-1 to produce 39s.
Also I used the fact that 36-1 sub-grids have small number of solutions - all solutions have been examined and respectively a full set of UA has been used in generation, eliminating validity (but no minimality) checks.

Examining redundancy in a grid with 54+n givens doesn't make much sense to me, but who knows...
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Bands and low-clue puzzles

Postby coloin » Mon Oct 17, 2016 8:00 pm

dobrichev wrote:The bands ordered by frequency in 46294 grids with 17-clue puzzles is in this table below.
.....
Next, for the known 17-clue puzzles we can count the crossing bands (band B1 from 416 crosses stack B2 from 416).
.....

I think there is a more obvious correlation ....

Bands 1-31 / 416 are the repeating minirow bands [ they have a 6 at r2c3 ]
Code: Select all
   
+----------------------------+----------------------------+----------------------------+
| 1        2        3        | 4        5        6        | 7        8        9        |
| 4        5        6        | 789      789      789      | 123      123      123      |
| 789      789      789      | 123      123      123      | 456      456      456      |
+----------------------------+----------------------------+----------------------------+   [Bands 1-31]

I had a brief look at the 17-puzzles and their solution grids
[49157 puzzles - 46300 ed grid solutions]
25721 had a repeating minirow of these 4531 had a crossing repeating minirow

Code: Select all
incidence of mimirow repeat in grids with 17 puzzles is           25721 /  46300         55.5%
incidence of mimirow repeat in random grids is                     4398 / 100000          4.4% 

incidence of crossing mimirow repeat in grids with 17 puzzles   is 4531 /  46300          9.78%
incidence of crossing mimirow repeat in random grids is             165 / 100000          0.16%

Code: Select all
+---+---+---+
|123|456|789|
|456|...|...|
|789|...|...|
+---+---+---+
|2..|...|...|
|5..|...|...|
|8..|...|...|
+---+---+---+
|3..|...|...|
|6..|...|...|
|9..|...|...|
+---+---+---+   crossing repeating minirow #15 below

Code: Select all
+----------------------------+----------------------------+----------------------------+
| 1        2        3        | 4        5        6        | 7        8        9        |
| 4        5        6        | 789      789      789      | 123      123      123      |
| 7        8        9        | 123      123      123      | 456      456      456      |
+----------------------------+----------------------------+----------------------------+
| 2        369      147      | 1356789  1346789  1345789  | 1345689  1345679  1345678  |
| 5        369      147      | 1236789  12346789 1234789  | 1234689  1234679  1234678  |
| 8        369      147      | 1235679  1234679  1234579  | 1234569  12345679 1234567  |
+----------------------------+----------------------------+----------------------------+
| 3        147      258      | 1256789  1246789  1245789  | 1245689  1245679  1245678  |
| 6        147      258      | 1235789  1234789  12345789 | 1234589  1234579  1234578  |
| 9        147      258      | 1235678  1234678  1234578  | 1234568  1234567  12345678 |
+----------------------------+----------------------------+----------------------------+

For completeness

There are only 3 ED with this pattern
Code: Select all
 
+---+---+---+     +---+---+---+      +---+---+---+
|123|456|789|     |123|456|789|      |123|456|789|
|456|...|...|     |457|...|...|      |457|...|...|
|789|...|...|     |689|...|...|      |986|...|...|
+---+---+---+     +---+---+---+      +---+---+---+

There are 3 ED single bands and their incidence in 100000 grids
Code: Select all
123456789456......789............................................................ -  4398 / 100000
123456789457......689............................................................ - 62829 / 100000
123456789457......986............................................................ - 32773 / 100000


There are 20 ED when two bands cross and their incidence in 100000 grids
Code: Select all
#  1        000000001000000002000000003000000004000000005000000006000000127000000348123478569 -4309           
#  2        000000001000000002000000003000000004000000005000000006000000127000000348124378569 -8775           
#  3        000000001000000002000000003000000004000000005000000006000000127000000348127348569 -3711      can 1 
#  4        000000001000000002000000003000000004000000005000000006000000127000000348128347569 -9187           
#  5        000000001000000002000000003000000004000000005000000006000000127000000348137248569 -8775           
#  6        000000001000000002000000003000000004000000005000000006000000127000000348138247569 -8781           
#  7        000000001000000002000000003000000004000000005000000006000000127000000348147238569 -9150           
#  8        000000001000000002000000003000000004000000005000000006000000127000000348148237569 -9319           
#  9        000000001000000002000000003000000004000000005000000006000000127000000348178234569 -4424           
# 10        000000001000000002000000003000000004000000005000000006000000127000000458127458369 -1846      can 1 
# 11        000000001000000002000000003000000004000000005000000006000000127000000458128457369 -4587           
# 12        000000001000000002000000003000000004000000005000000006000000127000000458147258369 -2135           
# 13        000000001000000002000000003000000004000000005000000006000000127000000458147258639 -2220           
# 14        000000001000000002000000003000000004000000005000000006000000127000000458157248369 -9160           
# 15        000000001000000002000000003000000004000000005000000006000000147000000258147258369 - 165      can^2  crossing minirow
# 16        000000001000000002000000003000000004000000005000000006000000147000000258147258639 - 979      can 1
# 17        000000001000000002000000003000000004000000005000000006000000147000000258148257639 -1134           
# 18        000000001000000002000000003000000004000000005000000006000000147000000258157248369 -1950      can 1
# 19        000000001000000002000000003000000004000000005000000006000000147000000258157248639 -4740           
# 20        000000001000000002000000003000000004000000005000000006000000147000000528127458369 -4653
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby champagne » Tue Oct 18, 2016 6:41 am

Hi coloin,

Nice correlation, but unhappily not so easy to use in a search of 17's.

I am wondering whether the underlying reason is not that with such patterns you have lower chances to find unavoidable sets of very small size.
IMO, the more UAs of size 4/6 you have, the less chances you have to produce a 17. This can be another correlation to study.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Bands and low-clue puzzles

Postby coloin » Tue Oct 18, 2016 3:18 pm

Indeed ... but I am thinking more like if there are more UAs - then there is more chance of a 17 [paradoxically]
It wont help in a search for 17s ....

Potentially once the repeating minirow is established - there are eliminations -- I noticed predominately repeating minirows in puzzles with the pattern
Code: Select all
+---+---+---+                 +---+---+---+             
|123|456|789|                 |123|456|789|             
|456|...|...|                 |4..|...|...|             
|789|...|...|                 |7..|...|...|             
+---+---+---+                 +---+---+---+             
|2..|...|...|                 |2..|...|...|             
|5..|...|...|                 |5..|...|...|             
|8..|...|...|                 |8..|...|...|             
+---+---+---+                 +---+---+---+             
|3..|...|...|                 |3..|...|...|             
|6..|...|...|                 |6..|...|...|             
|9..|...|...|                 |9..|...|...|             
+---+---+---+ add 7 clues     +---+---+---+  add 9 clues


Slight modification though

incidence of mimirow repeat in grids with 17 puzzles is ...........................25721 / 46300 = 55.5%
incidence of mimirow repeat in random bands is ................................... 4398 / 100000 = 4.4%
incidence of mimirow repeat in random grids is ......................................... 6 x 4.4 % = 26.4 %

incidence of crossing mimirow repeat in grids with 17 puzzles is .................. 4531 / 46300 = 9.78%
incidence of crossing mimirow repeat in random crossing bands is.................165 / 100000 = 0.16%
incidence of crossing mimirow repeat in random grids is............................... 9 x 0.16 % = 1.44 %
Last edited by coloin on Tue Oct 18, 2016 5:25 pm, edited 2 times in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby champagne » Tue Oct 18, 2016 5:21 pm

coloin wrote:Indeed ... but I am thinking more like if there are more UAs - then there is more chance of a 17 [paradoxically]


I have no evidence of that. The first difficulty in your sentence is the definition of "more UAs". In the search of 16's, Mc Garry produces all (nearly all) UAs of size 4 to 12. The solution grids of known 17 shows as many "low count" as "high count" as far as I could see in a mini sample. I am testing a search with UAs of bigger size, again, the ratio for the number of UAs seems to be in the range one to two.

As stated by Mc Garry as findings of the 16's search, the small UAs play a key role, Your chance to find a 17 are increasing if some cells belonging to smaller UAs are hitting many UAs. As a matter of fact, if you have many disjoint UAs, the minimum price to pay increases and your chances to find a 17 should be lower. This comes always with more UAs of size 4.


coloin wrote:Potentially once the repeating minirow is established - there are eliminations -- I noticed predominately repeating minirows in puzzles with the pattern


IMO that's somehow another wording for "less small UAs"
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Bands and low-clue puzzles

Postby coloin » Tue Oct 18, 2016 5:37 pm

Yes , sorry, i dont think I meant those size 4 UAs ! Was about to comment on it when you posted !
If you look at dobrichev's table
the very popular band 20 has got a high UA count [59] yet is solvable in 3
the band 29 has 81 UAs but is solvable in 2 clues

I think that the more unavoidables you have in general [not u4 though] the more puzzles you have in a grid and therefore statistically more likely to have a 17
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby coloin » Tue Oct 18, 2016 6:02 pm

coloin wrote:Potentially once the repeating minirow is established - there are eliminations


Ahah :!:

these 3 ED 15-patterns
Code: Select all
+---+---+---+        +---+---+---+            +---+---+---+
|123|456|789|        |123|456|789|            |123|456|789|
|456|...|...|        |457|...|...|            |457|...|...|
|789|...|...|        |689|...|...|            |986|...|...|
+---+---+---+  31    +---+---+---+ ~ ?        +---+---+---+ ~  ? 

the repeating minirow has 6x6x6x6 completions , only 3 pms in each cell ...
The other 2 make up the 32-416 , up to 5 pms in each cell, 18x6x6x6.... ie x3 more [same] ways to complete,
But there tends to be more UAs in the bands 1-31 ........ maybe dobrichev or other can clarify !!!!!

Each of the ED 416 bands has got 3x3=9 of these 15-patterns.
All the 15-patterns in bands 1-31 are canonical
The bands 32-416 will have varying numbers of the other 2 ways, of which the first one would seem to be x2 more common.
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Bands and low-clue puzzles

Postby champagne » Wed Oct 19, 2016 6:38 am

coloin wrote:Yes , sorry, i dont think I meant those size 4 UAs ! Was about to comment on it when you posted !
If you look at dobrichev's table
the very popular band 20 has got a high UA count [59] yet is solvable in 3
the band 29 has 81 UAs but is solvable in 2 clues

I think that the more unavoidables you have in general [not u4 though] the more puzzles you have in a grid and therefore statistically more likely to have a 17


Hi coloin,

I suggest another look at the same table.

Just consider all bands having a minimum of 3 clues.

The number of UAs goes, if I am right from 25 to 63. And I see no clear tendency for a high or a low count.

What I see in the search of 17s is that given a lot of UAs still active, It is nearly impossible to predict easily how many clues are still required (likely the reason why Mc Garry used the hgih degree UAs). You have a similar conclusion here. Given a number of UAs, it is nearly impossible to predict how many clues will be needed at minimum. However, if my memory is correct, if you just consider the 6 cells UAs in band 1, you see that a minimum of 6 clues (the final minimum) is required.

Cheers

champagne

PS the number of UAs of any size with no subset is very big in a solution grid. I suspect several thousands in average, but may be somebody have a better approach of the count.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to General