The New Sudoku Players' Forum

[gsf]

5 new 17's popped out

Did you do a two-off search on the 5 new puzzles as well? Maybe there's even more there...

new puzzles found during the search were thrown back into the mix
so the 5 new ones (6 was a clerical error) were searched too

[gsf]

For each input puzzle remove each clue, one at a time, and determine (and tour)
the valid puzzles that result when each empty cell is assigned all possible
values. This induces a partition on the input puzzles.

Well done with that fast search.

How much work is actually saved by partitioning the search space? I had assumed not much, which is why I didn't do that. I assume your search finished so quickly mainly due to your much faster solver.

a fast solver and canonicalizer helped
the search was organized around a canonical puzzle dictionary
a puzzle in the dictionary means it was already searched
so dictionary hits are a big win
partitioning was just a byproduct of labelling puzzles in each branch of the search

I didn't count the #solves/canonicalizations (dictionary lookups were in the noise)
but based on ~5000 solutions/canonicalizations per sec for the 17 catalog and 10h11m run time
there were probably > 150,000,000 solutions/canonicalizations in the run
(not every solve lead to a solution, so the solver probably dominated canonicalization)

[ronk]

the two runs over known 17's, each using slightly different techniques, agreed
the second one completed in 10h11m on a 3.2Ghz pentium
papy's 3 and Red Ed's 1 were corroborated
and 5 new 17's popped out

Code: Select all

000406700050700000089000004000090050004000000000000200000000006500200000010000090
003450700000000000890000010005060000700000008000001020000000600010008000000000005
020450000000000103090000000200003000000000900005000040000000000007001600040020050
100000700000009030608200000000500600000000190030002000000000000500610000000000020
103000000000000060000007005008000000306000090000042100000600004070000008000300000


gsf, excellent job. However, I think there's still a clerical error. Your third puzzle is equivalent to Red Ed's puzzle here.

Code: Select all

.2.45..........1.3.9.......2....3.........9....5....4............7..16...4..2..5. #gsf

.1.2...3.4.....5.....6.....7...4.....2......6....5....5...73....8....4..........7 #Red Ed

While it's useful to compare puzzles in canonical form, I certainly hope they aren't catalogued that way. Which begs the question ... what is the catalog form of the 36,628?

I would argue that the catalog form should be a maximally-symmetric, however that might be defined. Does anyone already have software to do that?

[gsf]

gsf, excellent job. However, I think there's still a clerical error. Your third puzzle is equivalent to Red Ed's puzzle here.

Code: Select all

.2.45..........1.3.9.......2....3.........9....5....4............7..16...4..2..5. #gsf

.1.2...3.4.....5.....6.....7...4.....2......6....5....5...73....8....4..........7 #Red Ed

I'm glad I'm not paying for the proof reading ...
original post corrected
thanks

While it's useful to compare puzzles in canonical form, I certainly hope they aren't catalogued that way. Which begs the question ... what is the catalog form of the 36,628?

They are stored in lex order according to the canonical labelling that comes out of a program, and so the old ones will be interleaved with the new ones, thus any references to "Number #21020" and so on will change. When I get round to it, I will put them in a proper database with a permanent ID number.

and I believe that program is nauty -- a graph/digraph (lines and edges) automorphism/isomorphism workhorse by Brendan McKay

so the original catalog posted by gordon is in a canonical order

I would argue that the catalog form should be a maximally-symmetric, however that might be defined. Does anyone already have software to do that?

for computations involving equivalence a canonical representation is most efficient
I work off a 1 puzzle per line file with 7 fields
< canonical-puzzle canonical-grid original-puzzle original-ordinal tour-class contributer date >
http://www.research.att.com/~gsf/sudoku/data/sudoku17-2007-01-22.can.gz
sort, uniq, cut, join on that file produce all of the data in the posts
the (numerous) clerical errors were due to entry errors in the catalog
the posted catalog should have it right

I don't think anyone has posted a "symmetrizer"

[coloin]

Excellent, thankyou for that work, the file and explanations as to the computation.

So, 5 more 17-puzzles ................giving a total of 36628 + Papys (3)+ Red Ed's (1)+ gsf's(5)= 36637

That shows perhaps just how complete Gordon's search was.

I know everybody wants to ask but darnt........how is the 4-off search coming on ?

C

[gsf]

That shows perhaps just how complete Gordon's search was.

I know everybody wants to ask but darnt........how is the 4-off search coming on ?

4 off search will require a different tactic
it could blow up by ~100X
and at some point it would encroach on checker's turf

[ronk]

So, 5 more 17-puzzles ................giving a total of 36628 + Papys (3)+ Red Ed's (1)+ gsf's(5)= 36637

That shows perhaps just how complete Gordon's search was.

I followed this development post-by-post and saw it as ...

4 more 17-puzzles ................giving a total of 36628 + Papys (3)+ Red Ed's (2)+ gsf's(4)= 36637

Each time a "new" puzzle was posted, I added it to my copy of the original 36628 and checked the total of non-equivalents. That total was 36633 before gsf posted his results, and 36337 after.

[gsf]

I followed this development post-by-post and saw it as ...

4 more 17-puzzles ................giving a total of 36628 + Papys (3)+ Red Ed's (2)+ gsf's(4)= 36637

Each time a "new" puzzle was posted, I added it to my copy of the original 36628 and checked the total of non-equivalents.
That total was 36633 before gsf posted his results, and 36337 after.

thanks for the kind posts from those who know how to count
I fixed the clerical errors and reposted the complete .can.gz file
that file has gordon's original ordinal labels and the 9 recent new ones labeled 36629-36637

I also reposted my solver with a -t option that tours the 1-off and 2-off neighborhoods of the input puzzles

[coloin]

These two 17s - one found by Papy and the other from Gordon..

Code: Select all

.2.4....9..6.8.........................9.7.....8...61.5....1....9....4.2....6...7
.2.4....9..6.8.........................9.7.....8...61.5....1....9....4.3....6...7

Checker has confirmed that there are NO non-minimal 18s in either of these two grids, plenty of 19s though..................


When refering to a 4-off search....and how it would be difficult

and at some point it would encroach on checker's turf

I agree.........except perhaps it could be focused..........

Given the SF grid and these 14 common clues - a program can find the 29 17-clue soduku puzzles in around 10 seconds.

Code: Select all

....4.7...8........1..........8....67........4.....2..3...7..................6.18

This subgrid has 621862 grid solutions which would prohibit a search for other 17s.

However a program [as yet unwritten] which could easily identify 4 or more unavoidable sets in any of these grid solutions would immediatly rule that grid out - so speeding up any search......
.....just a thought

C

[RW]

This subgrid has 621862 grid solutions which would prohibit a search for other 17s.

However a program [as yet unwritten] which could easily identify 4 or more unavoidable sets in any of these grid solutions would immediatly rule that grid out - so speeding up any search......
.....just a thought

Could perhaps make it faster for some grids, but those 14 clues in the SF grid are of course exceptional. I guess most 15 clue combinations from other puzzles would have more solutions. And for some grids (like this one) the method could be very slow. Maybe worth a try though...

RW

[coloin]

Well......how do I put this.......as a sort of follow up to the above post, I asked ravel to look at common equivalent clues in 17 clue puzzles of this clues/in/box pattern equivalent

Code: Select all

122
222
222

In the sudoku space thread he developed a technique to attempt to get the greatest concordance of clues between two puzzles.

I believe he lines up the clues in the boxes and then swaps the clue numbers, analysing for best fit......

It's not clear for me, what you want, but this might be interesting for you:
There are 1565 17-clues with this box/clue distribution in Gordon's list now. When i calculated the puzzles with maximum common clues relatively to the first one, it turned out that almost all of those with 15/16 common clues and some with 14 had the same 14 clues in common

Code: Select all

.......24.1...8.......7....6..2.15..4.......3..........7....81.5..43.............
.......24.16..8.......7.......2.17..4.......3..........7....81.5..43.............
.......24.1...8.......7....6....1...4.......3...2....9.7....81.5..43.............
6......24.1...8.......7.......2.15..4.......3..........7....81.5..43.............
.......24.1...8.......7....6....1...4.......3...2....6.7....81.5..43.............
6......24.1...8.......7.......2.19..4.......3..........7....81.5..43.............
.......24.1...8.......7....6....1..94.......3...2......7....81.5..43.............
.......24.1...8.......7........61.7.4.5.....3..........7....81.5..43.............
.......24.1...8.......7....6..2.1...4.......3........9.7....81.5..43.............
6......24.1...8.......7.........1...4..2....3......5...7....81.5..43.............
.......24.1...8.......7....6....1.9.4.......3...2......7....81.5..43.............
6......24.1...8.......7.......2.1...4.......3..6.......7....81.5..43.............
9......24.1...8.......7.......2.1...4.......3..6.......7....81.5..43.............
.......24.1...8.......7....6....1...4..2....3........7.7....81.5..43.............
..9....24.1...8.......7.........1.6.4.......3...2......7....81.5..43.............
.......24.16..8.......7.........1...4..2....3......5...7....81.5..43.............
.......24.16..8.......7.......2.1...4.......3........6.7....81.5..43.............
6......24.1...8.......7.......2.1.6.4.......3..........7....81.5..43.............

Havard has a program which easily finds 17s from these subgrids
Initially they were thought to be new but subsequently were found to not to be.

I thought it was a good try.
C

[Havard]

I guess I just have to try again...

Code: Select all

.......16.......4..5.2.....4...6.3.......82......41......5...9.1.4......3........   
.......21...5...3.4..6.........21...8........5.....6.....4..5...1..7.9...3.......   
.......21.6.8............7..7..21....2....4.......5...5..43.6..1................9   
.......246..8.5...1............4..1..7....3...4.6......2...4.........8.6.....3...     
.......29.3...6........5..8.6....5...53..........2..........15.2...7.4..9........
.......3.4...2.........7..1...3.1.5.7..5.....2.6..........8.2...3.......5.....4..   
........16..8..........2..3.3....85..2..1.......4.....8.4...6......3....7....5...   
.......3.9.8.4...........1....1.3..62.....4.....6.......75..2......6.8...1.......   
.......38.9.2...........51.74....6.......37......1......56..2....3...........7...   
.......38.9.2...........51.74....6.......3..7....1......56..2....3..7............     
......4.1..73...........52....8.....42...5...5.......7.6...42......1......8......   
.......41..73...........52....8..3..42.......5....2........426.....1......8......   
........319.2..........9......6..7........2....5.8....27.1.........3..659........ 
.......61...8.....4.....9.....3..78.16.5.....2.........3...........2.4...8..6....

EDIT: removed faulty ones

Havard

[coloin]

You did try hard !

The 15 valid ones here ARE new !

Code: Select all

1 sol.          .......16.......4..5.2.....4...6.3.......82......41...3..5...9.1.4...............  #1     
1 sol.          .......16.......4..5.2.....4...6.3.......82......41......5...9.1.4......3........  #2   
1 sol.          .......21...5...3.4..6.........21...8........5.....6.....4..5...1..7.9...3.......  #3   
1 sol.          .......21.6.8............7..7..21....2....4.......5...5..43.6..1................9  #4   
1 sol.          .......246..8.5...1............4..1..7....3...4.6......2...4.........8.6.....3...  #5     
1 sol.          .......29.3...6........5..8.6....5...53..........2..........15.2...7.4..9........  #6
1 sol.          .......3.4...2.........7..1...3.1.5.7..5.....2.6..........8.2...3.......5.....4..  #7   
1 sol.          ........16..8..........2..3.3....85..2..1.......4.....8.4...6......3....7....5...  #8   
1 sol.          .......3.9.8.4...........1....1.3..62.....4.....6.......75..2......6.8...1.......  #9   
1 sol.          .......38.9.2...........51.74....6.......37......1......56..2....3...........7...  #10   
1 sol.          .......38.9.2...........51.74....6.......3..7....1......56..2....3..7............  #11     
1 sol.          ......4.1..73...........52....8.....42...5...5.......7.6...42......1......8......  #12   
1 sol.          .......41..73...........52....8..3..42.......5....2........426.....1......8......  #13   
1 sol.          ........319.2..........9......6..7........2....5.8....27.1.........3..659........  #14 
1 sol.          .......61...8.....4.....9.....3..78.16.5.....2.........3...........2.4...8..6....  #15 


Canonicalized

Code: Select all

000056000400000030000210000000100095300000000000000001000904000002000000015000070 #1
000056000400000030000210000000100905300000000000000001000904000002000000015000070 #2
100000009000000063800007000036000000000002000000001800040600500000900000700000100 #3
120000000400000000000003005005608900070000000000000200000120004000090000008000001 #4
000006009050100000090000040000740000030000900000000100006000000000093000004000270 #5
100000080000000032709001000000060000000014600038000000000000000000000401005800000 #6
000400009000780000009000605030900000070000010000005000005000000600000400000300070 #7
000006700400080000009000005260001000000000098070000000000590000000000040010000060 #8
000050000406000100000030000200008070000004900030000000008001000000000090000900035 #9
003000000400000020000120060200000000000004000060005070070900000000000408000000350 #10
000056000400000003000120000000000000001300008005000070000007050000000200970800000 #11
100006080000700000009000000000090000860003000030000002000000067000000830002040000 #12
023000000450000000000010600000004050600000900000502000000090000570000020000000003 #13
100000009000000003008007000060000000300560000000000040500390000000600000004000170 #14
100000000050009030700002000030610000000070802000000000000000000002048000000000067 #15

Well done


You need to do a 2off / 2on search of the new ones too !

C

[Havard]

the good news is that these ones are just from the first 500 of the list... So we might expect almost 2000 more, maybe...
EDIT: I'll reduce the optimism slightly. Around 700 is a better estimate.

[wapati]

I guess I just have to try again...

Havard

And again perhaps. Some of those are 16s. (and not valid ones.)

Edited to add: The 16s I checked have valid 17s lurking but that may well make them dups of other 17s.

Edited again: One line has a single clue. Oops.