The New Sudoku Players' Forum

[coloin]

As the number of 17-puzzles is now on 47998.....mainly due to the relentless background searching by gsf and Kohei Noshita here, recent musings on this page has possibly given me an idea.

Following up Red Eds failed method.......

With all the great 17-mining that's been going on recently, I thought you might be amused by a method I have pioneered for not finding new 17s.

It works as follows. I would like to be able to do a delete-three-add-three search ("3 off, 3 on") around gfroyle's list of 17s, but that would take too long. So instead I search for all 14-clue subgrids that have <100000 solutions -- this should give me just the "best" of the 3-offs. Now for each of those 14-clue subgrids (335 of them, up to isomorphism), I add back 3 clues in all possible ways. Not a single new 17 appears!

Perhaps we could extend this work.............

Instead of counting the number of solutions, perhaps we should be counted the number of infered clues....

In a 14-clue subpuzzle/grid - there is undoubtably a relationship between these, however the number of solutions is not too relevant to the single soluton grid which happens to be solved with 3 more clues.

counting the number of inserted clues is quick - is there a gsf code for this ?

Also doing an individual {-0+3} is significantly quicker with 14 plus 15 or so clues already inserted.

So perhaps this selective {-0+3} or {-0+4} on selected 14 and 13 subpuzzles which have a significant amount of inserted clues might prove a more productive way.

Perhaps Red Ed s method wasnt that bad ?

C

[coloin]

Taking the most recently found 17

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|..2|.34|...|
+---+---+---+
|...|3..|.5.|
|.1.|...|4..|
|.6.|71.|...|
+---+---+---+
|...|8..|..6|
|..4|...|.2.|
|5.3|...|...|
+---+---+---+  #47998

of the 680 [17*16*15*1/6] or so 14-subpuzzles this one

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..4|...|
+---+---+---+
|...|3..|.5.|
|.1.|...|4..|
|.6.|71.|...|
+---+---+---+
|...|8..|..6|
|..4|...|...|
|5.3|...|...|
+---+---+---+ has 14 clues, plus 12 inserted, 2266528 sol.

possibly the most favorable iof all the 680 14-subpuzzles from this puzzle.

of course doing a {-0+3} doesnt find any more 17s, but probably there arnt any at that level, more likely some at the 13 plus 4 level.

It wouldnt be difficult to do this for many of the more remote and/or more recently found 17s. Certainly it wont be a slow process.

C

[JPF]

Here are some stats based on the first 48010 known 17-puzzles :

There are only 32805 non isomorphic patterns.
Therefore, in average, each pattern contains 1.46 puzzles

The most popular pattern contains 36 different puzzles.
Here's the pattern in minlex form :

Code: Select all

...|...|...
...|...|.xx
..x|.xx|...
---+---+---
...|..x|x.x
.x.|...|...
xx.|x..|...
---+---+---
...|x..|...
..x|x..|x..
x..|...|...


Here are the 36 puzzles, as they are in Royle's database :

010000003062000000000400500070000260800900000000300000300000400500060000000010000
010000003062000000000400500070000260800900000000300000900000400500060000000010000
010000003062000000000400800070000210800500000000300000300000400500060000000010000
010000003062000000000400800070000260400900000000300000300000400500060000000010000
010000003082000000000500700040000680600700000000300000700000200400080000000010000
010000004082000000000500700060000280300900000000300000500000300400080000000010000
010000004092000000000500800060000290700800000000300000800000300400090000000010000
010000005062000000000400300070000260800900000000300000300000400500060000000010000
010000005062000000000400800070000260300900000000300000900000400500060000000010000
010000005062000000000400800070000260400900000000300000300000400500060000000010000
010000005062000000000400800070000260800900000000300000900000400500060000000010000
010000005062000000000400900070000260800900000000300000900000400500060000000010000
010000005062000000000400900070000860800900000000300000900000400500060000000010000
010000005092000000000600800070000290300400000000300000600000400500090000000010000
010000007052000000000400800060000250700900000000300000800000400300050000000010000
010000008062000000000400300070000260800500000000300000300000400500060000000010000
010000008092000000000600300070000290800400000000300000300000400500090000000010000
010000009082000000000500700040000680600700000000300000700000200400080000000010000
050000007012000000000400800060000250700900000000300000800000400300050000000010000
060000003012000000000400500070000260800900000000300000300000400500060000000010000
060000003012000000000400500070000260800900000000300000900000400500060000000010000
060000003012000000000400800070000210800500000000300000300000400500060000000010000
060000003012000000000400800070000260400900000000300000300000400500060000000010000
060000003012000000000500800040000760700800000000300000800000200400060000000010000
060000005012000000000400300070000260800900000000300000300000400500060000000010000
060000005012000000000400800070000260300900000000300000900000400500060000000010000
060000005012000000000400800070000260400900000000300000300000400500060000000010000
060000005012000000000400800070000260800900000000300000900000400500060000000010000
060000005012000000000400900070000260800900000000300000900000400500060000000010000
060000005012000000000400900070000860800900000000300000900000400500060000000010000
060000008012000000000400300070000260800500000000300000300000400500060000000010000
060000009012000000000500800040000760700800000000300000800000200400060000000010000
070000004012000000000500800060000270300900000000300000500000300400070000000010000
070000004012000000000500900060000270800900000000300000900000300400070000000010000
080000005012000000000600900070000280300400000000300000600000400500080000000010000
080000009012000000000600300070000280900400000000300000300000400500080000000010000

Nothing new, they are old (#14732 to #23255)

For information, here are the next two patterns with 34 puzzles :

Code: Select all

...|...|...
...|...|.xx
..x|.xx|...
---+---+---
...|...|x.x
.x.|...|...
xx.|x..|...
---+---+---
...|x..|.x.
..x|...|x..
.x.|..x|...


#4713 to #6152

Code: Select all

...|...|..x
...|..x|...
..x|...|.xx
---+---+---
...|..x|x..
..x|.x.|...
.x.|...|..x
---+---+---
...|xx.|...
.x.|...|...
xx.|...|x..


#26050 to #33468

An other interesting observation :

There are 23 481 (48.9%) puzzles sharing an isomorphic pattern with others.
Among them, only 13 puzzles are not all-singles.
99.99 % are all-singles puzzles.

Of course, it could be the result of the way these puzzles have been found, but...

JPF

[coloin]

..........
There are 23 481 (48.9%) puzzles sharing an isomorphic pattern with others.
Among them, only 13 puzzles are not all-singles.
99.99 % are all-singles puzzles.......
JPF

And of those puzzles which are formed from a 14-puzzle with significant insertable clues.......
-the 17 puzzles will have have predominantly singles
-the 17 puzzles wont be remote - there will be others close - therefore the puzzles are very unlikely to be new.

The most recently found 17-puzzles tend to have no others within {-1+1} and have reduced 18s when they are subjected to {-1+2}
These 18s produced also tend to be remote. Some dont have any within {-1+1} and of those that do - they often form a closed group.

If you are making 18s by a {-1+1} process you are definitely less likely to hit these 18-puzzles. Which must explain why we havnt found the new puzzles.

C

[holdout]

Judicious Relabeling Finds Additional 17-Clue Puzzles

Like many others, I examined the 17-clue set with 36 puzzles having the same pattern. My purpose was to use the set as a model to guide me in writing a routine to maximize the number of hits when counted over all 17 positions. The idea is to selectively relabel portions of some puzzles to increase the hit rate.

While the routine has not been written, I believe it has led me to discover four new 17-clue puzzles. Relabeling decisions are not always straightforward. You might think that positions having a constant clue (i.e. 12. 49 and 77, below) should not be relabeled. Notice, however that positions 2 and 11 can be made constant, at the expense of position 77 being split into two values -- resulting in a net gain in hits.

Code: Select all

                       From Gordon Royle's 17-Clue Database

         111111111122222222223333333333444444444455555555556666666666777777777788
123456789012345678901234567890123456789012345678901234567890123456789012345678901 Line#
           =                                    =                           =
.1......3.62.........4..5...7....26.8..9........3.....3.....4..5...6........1.... 14731
.1......3.62.........4..5...7....26.8..9........3.....9.....4..5...6........1.... 14732
.1......3.62.........4..8...7....21.8..5........3.....3.....4..5...6........1.... 14733
.1......3.62.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 14734
.1......3.82.........5..7...4....68.6..7........3.....7.....2..4...8........1.... 14735
.1......4.82.........5..7...6....28.3..9........3.....5.....3..4...8........1.... 14743
.1......4.92.........5..8...6....29.7..8........3.....8.....3..4...9........1.... 14744
.1......5.62.........4..3...7....26.8..9........3.....3.....4..5...6........1.... 14753
.1......5.62.........4..8...7....26.3..9........3.....9.....4..5...6........1.... 14754
.1......5.62.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 14755
.1......5.62.........4..8...7....26.8..9........3.....9.....4..5...6........1.... 14756
.1......5.62.........4..9...7....26.8..9........3.....9.....4..5...6........1.... 14757
.1......5.62.........4..9...7....86.8..9........3.....9.....4..5...6........1.... 14758
.1......5.92.........6..8...7....29.3..4........3.....6.....4..5...9........1.... 14759
.1......7.52.........4..8...6....25.7..9........3.....8.....4..3...5........1.... 14786
.1......8.62.........4..3...7....26.8..5........3.....3.....4..5...6........1.... 14793
.1......8.92.........6..3...7....29.8..4........3.....3.....4..5...9........1.... 14794
.1......9.82.........5..7...4....68.6..7........3.....7.....2..4...8........1.... 14799
.5......7.12.........4..8...6....25.7..9........3.....8.....4..3...5........1.... 19621
.6......3.12.........4..5...7....26.8..9........3.....3.....4..5...6........1.... 20754
.6......3.12.........4..5...7....26.8..9........3.....9.....4..5...6........1.... 20755
.6......3.12.........4..8...7....21.8..5........3.....3.....4..5...6........1.... 20756
.6......3.12.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 20757
.6......3.12.........5..8...4....76.7..8........3.....8.....2..4...6........1.... 20758
.6......5.12.........4..3...7....26.8..9........3.....3.....4..5...6........1.... 20761
.6......5.12.........4..8...7....26.3..9........3.....9.....4..5...6........1.... 20762
.6......5.12.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 20763
.6......5.12.........4..8...7....26.8..9........3.....9.....4..5...6........1.... 20764
.6......5.12.........4..9...7....26.8..9........3.....9.....4..5...6........1.... 20765
.6......5.12.........4..9...7....86.8..9........3.....9.....4..5...6........1.... 20766
.6......8.12.........4..3...7....26.8..5........3.....3.....4..5...6........1.... 20770
.6......9.12.........5..8...4....76.7..8........3.....8.....2..4...6........1.... 20773
.7......4.12.........5..8...6....27.3..9........3.....5.....3..4...7........1.... 22018
.7......4.12.........5..9...6....27.8..9........3.....9.....3..4...7........1.... 22019
.8......5.12.........6..9...7....28.3..4........3.....6.....4..5...8........1.... 23249
.8......9.12.........6..3...7....28.9..4........3.....3.....4..5...8........1.... 23254


At any rate, the follow-your-nose relabeling procedure resulted in 8 constant positions and made very clear that the puzzles could be grouped into 16 pairs, with 4 puzzles having no mate. See below. New 17-clue puzzles were generated by constructing the obvious puzzle mates.

Due to connectivity problems with the Sudoku Identification Service, I have not been able to verify that the puzzles are actually new. I have verified that each puzzle has a unique solution.

Code: Select all

               After Judicious Relabeling (with four additional puzzles)

         111111111122222222223333333333444444444455555555556666666666777777777788
123456789012345678901234567890123456789012345678901234567890123456789012345678901 Line#
 =        ==         =      =    =     =        =         
.1......5.62.........4..8...7....21.3..9........3.....4.....3..5...1........6.... 22018
.1......5.62.........4..8...7....26.3..9........3.....4.....3..5...6........1.... 14743

.1......5.62.........4..8...7....21.3..9........3.....4.....9..5...1........6.... 23249
.1......5.62.........4..8...7....26.3..9........3.....4.....9..5...6........1.... 14759

.1......5.62.........4..8...7....21.3..9........3.....9.....4..5...1........6.... 20762
.1......5.62.........4..8...7....26.3..9........3.....9.....4..5...6........1.... 14754

.1......3.62.........4..8...7....21.4..9........3.....3.....4..5...1........6.... 20757
.1......3.62.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 14734

.1......5.62.........4..8...7....21.4..9........3.....3.....4..5...1........6.... 20763
.1......5.62.........4..8...7....26.4..9........3.....3.....4..5...6........1.... 14755

.1......5.62.........4..8...7....21.5..9........3.....8.....4..3...1........6.... 19621
.1......5.62.........4..8...7....26.5..9........3.....8.....4..3...6........1.... 14786

.1......3.62.........4..5...7....26.8..9........3.....3.....4..5...6........1.... 14731
.1......3.62.........4..5...7....21.8..9........3.....3.....4..5...1........6.... 20754

.1......5.62.........4..3...7....21.8..9........3.....3.....4..5...1........6.... 20761
.1......5.62.........4..3...7....26.8..9........3.....3.....4..5...6........1.... 14753

.1......8.62.........4..3...7....21.8..9........3.....3.....9..5...1........6.... 23254
.1......8.62.........4..3...7....26.8..9........3.....3.....9..5...6........1.... 14794

.1......8.62.........4..3...7....26.8..9........3.....3.....4..9...6........1.... 14793
.1......8.62.........4..3...7....21.8..9........3.....3.....4..9...1........6.... 20770

.1......3.62.........4..8...7....26.8..9........3.....3.....4..9...1........6.... 20756
.1......3.62.........4..8...7....21.8..9........3.....3.....4..9...6........1.... 14733

.1......3.62.........4..5...7....21.8..9........3.....9.....4..5...1........6.... 20755
.1......3.62.........4..5...7....26.8..9........3.....9.....4..5...6........1.... 14732

.1......5.62.........4..8...7....21.8..9........3.....9.....4..5...1........6.... 20764
.1......5.62.........4..8...7....26.8..9........3.....9.....4..5...6........1.... 14756

.1......5.62.........4..9...7....26.8..9........3.....9.....4..5...6........1.... 14757
.1......5.62.........4..9...7....21.8..9........3.....9.....4..5...1........6.... 20765

.1......5.62.........4..9...7....86.8..9........3.....9.....4..5...6........1.... 14758
.1......5.62.........4..9...7....81.8..9........3.....9.....4..5...1........6.... 20766

.1......5.62.........4..9...7....21.8..9........3.....9.....3..5...1........6.... 22019
.1......5.62.........4..9...7....26.8..9........3.....9.....3..5...6........1.... 14744

.1......3.62.........4..9...7....51.5..9........3.....9.....2..7...1........6.... 20758
.1......3.62.........4..9...7....56.5..9........3.....9.....2..7...6........1.... new

.1......5.62.........4..9...7....86.8..9........3.....9.....2..7...6........1.... 14799
.1......5.62.........4..9...7....81.8..9........3.....9.....2..7...1........6.... new

.1......3.62.........4..9...7....86.8..9........3.....9.....2..7...6........1.... 14735
.1......3.62.........4..9...7....81.8..9........3.....9.....2..7...1........6.... new

.1......8.62.........4..9...7....51.5..9........3.....9.....2..7...1........6.... 20773
.1......8.62.........4..9...7....56.5..9........3.....9.....2..7...6........1.... new


[gsf]

Code: Select all

.1......3.62.........4..9...7....51.5..9........3.....9.....2..7...1........6.... 20758
.1......3.62.........4..9...7....56.5..9........3.....9.....2..7...6........1.... new

.1......5.62.........4..9...7....86.8..9........3.....9.....2..7...6........1.... 14799
.1......5.62.........4..9...7....81.8..9........3.....9.....2..7...1........6.... new

.1......3.62.........4..9...7....86.8..9........3.....9.....2..7...6........1.... 14735
.1......3.62.........4..9...7....81.8..9........3.....9.....2..7...1........6.... new

.1......8.62.........4..9...7....51.5..9........3.....9.....2..7...1........6.... 20773
.1......8.62.........4..9...7....56.5..9........3.....9.....2..7...6........1.... new


no need for the full catalog
if you canonicalize and sort/uniq the last 8 puzzles you get 4 puzzles
also, the equivalent puzzles are paired

[coloin]

Is there a reason why the 4 puzzle pairs are isomorphic and the other ones arnt ? Its not obvious !

They only differ by a [6>1] relabel and a single 6>1 clue swop

Code: Select all

.1......5.62.........4..9...7....86.8..9........3.....9.....2..7...6........1.... # 14799
.6......5.12.........4..9...7....86.8..9........3.....9.....2..7...6........1.... # "new"

Edit - this means that the relabeling and clue swop gives the same 2-rookery [envolving the 1 and 6]
The clue swop changes a u4, and the relabelling changes the u14.

BTW its a shame we lost anon17 posts

C

[gsf]

BTW its a shame we lost anon17 posts

yes
at the time of those posts I was too busy (earning a paycheck) to respond
I think on this forum anon17 => ano1

near the end of summer I'll have access to another large cpu cluster that will need some breaking in
it would be nice to line up some 17s processing for that

[holdout]

Is there a reason why the 4 puzzle pairs are isomorphic and the other ones arnt ? Its not obvious !

Certainly not to me!
-- Holdout --

[coloin]

Well i was wrong - clue swapping changes all the clues - and swopping 2 clues giveds a different grid.

here are the true pairs

puzzle and index for solution

Code: Select all

.1......3.62.........4..9...7....51.5..9........3.....9.....2..7...1........6....  #  165 182 375  ,  24 154 319
.1......3.62.........4..9...7....56.5..9........3.....9.....2..7...6........1....  #  247 182 375  ,  14  88 319
                                                                                                               
.1......5.62.........4..9...7....86.8..9........3.....9.....2..7...6........1....  #  117 345 336  ,  18  23 319
.1......5.62.........4..9...7....81.8..9........3.....9.....2..7...1........6....  #  296 345 336  ,  18  27 319
                                                                                                               
.1......3.62.........4..9...7....86.8..9........3.....9.....2..7...6........1....  #  247 182 375  ,  14  88 319
.1......3.62.........4..9...7....81.8..9........3.....9.....2..7...1........6....  #  165 182 375  ,  24 154 319
                                                                                                               
.1......8.62.........4..9...7....51.5..9........3.....9.....2..7...1........6....  #  296 345 336  ,  18  27 319
.1......8.62.........4..9...7....56.5..9........3.....9.....2..7...6........1....  #  117 345 336  ,  18  23 319

its easier to see the isomorph now [5>8]

Code: Select all

.1......5.62.........4..9...7....86.8..9........3.....9.....2..7...6........1....  #  117 345 336  ,  18  23 319
.1......8.62.........4..9...7....56.5..9........3.....9.....2..7...6........1....  #  117 345 336  ,  18  23 319

C

[dobrichev]

1) Take the known 17-clue puzzles.
2) Store them in canonical form.
3) Group them by solution grid.
4) For some solution grid:
4.1) collect some unavoidable sets (UA). You may use Gridchecker --unav to do it.
4.2) for each UA:
4.2.1) compose a pseudopuzzle with all givens except the UA cells.
4.2.2) find all pseudopuzzle solutions. By definition they are > 1.
4.2.3) canonicalize each solution. Remember the transformation applied.
4.2.4) ignore solutions identical to the original grid. My observation is that multisolution UA lead to no more than 2 essentially different (ED) grids. So after this step we have zero or one ED grid.
4.2.5) Check whether the grid has known 17s. If it hasn't, ignore it.
4.2.6) find the known 17s for this grid.
4.2.7) for each canonicalized known puzzle within the grid:
4.2.7.1) apply the reverse transformation to the puzzle (see 4.2.3).
4.2.7.2) look at the differences between the puzzle and all known puzzles for the solution chosen at step 4.

There are much puzzles which differ only by:
- relabelling a single clue;
- relabelling 2 clues;
- relabelling 1 and applying -1/+1;
- relabelling 2 and applying -1/+1;
....

So, relabel 2 clues for a known puzzle (in all possible ways). Then remove, one at a time, each of the rest clues. Then add a new clue at each possible positions, assigning each possible digits. Check for a single solution, then canonicalize and check whether it is known.
This takes 5 - 10 minutes per puzzle and leads to a puzzles at Hamming distance of 3[EDIT: 4. Same is covered by -2/+2].
Taking into account common unavoidables (at least one clue per 2 rows in a band, at least 8 different digits, etc.) will speedup the process in some degree.

[EDIT: In similar way relabelling 3 then applying -1/+1, or relabeling 2 then applying -2/+2 leads to more distant puzzels with expected high hit rate.]

MD

[coloin]

I think it ought to be said that anon17 did very clever work on finding at least 150 approx more 17-puzzles - giving our present total of 49151.

Unfortunately the details were lost in the old forum crash.

From my recollection and appologies if there is inaccuracies in this.

There are estimated to be more than 1.6 billion 18 puzzles.

There is a large closed to {-1+1} group of 0.9 billion 18s

There was an estimated ^200 {-1+1} tree to all these 0.9 billion puzzles [ ? correct]

The rest of the 18s are without this group and exist in clusters of {1+1} - some i believe with more than 1000 puzzles.

The storage and filing of these puzzles is a massive logistic exercise.

It was thought that there would be very few new 18s within the large 0.9 billion group found by a {-2+1} process. And when mere mortals were searching within this group of 18s explains why new ones wernt found easily !

There wont be that many 17-puzzles ? estimated 50 left to find - in the non-massive group of 18s subjected to a {-1+1}x4{-2+1} .

Perhaps anon17 can repost ?

C

[holdout]

Many people talk about "minlex ordering", without it being well defined.
I would appreciate a good definition.

Holdout

[FLOCKMAN]

Hi Havard, Gordon and Coloin,

I am interested in 17 clue Sudokus of type 122222222.

There is controversy as to how many have been found, Some say 5 others say more.

I would like to study them in detail. Can anyone point me to them?

[coloin]

It depends what you mean ! - of the 49152 known ED puzzles.......

Code: Select all

+---+---+---+
|...|...|...|
|...|..1|..2|
|..3|...|..4|
+---+---+---+
|...|...|.5.|
|...|.6.|.7.|
|21.|..8|...|
+---+---+---+
|...|3..|...|
|.4.|...|6.9|
|8..|5.7|...|
+---+---+---+

there are 10 17-puzzzles with clue frequencies of 222222221

and

Code: Select all

+---+---+---+
|...|...|..1|
|...|..2|..3|
|..4|.5.|...|
+---+---+---+
|...|.6.|74.|
|.8.|...|...|
|.3.|7..|...|
+---+---+---+
|...|3..|..8|
|..5|...|.6.|
|9..|.2.|...|
+---+---+---+

There are 2084 17-puzzles with clues-in-box distriution 222222221

gsfs proram can count the clues, box, row and column
pm me and i can send you the files

C