17-clue and 18-clue Sudoku update

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

Postby gsf » Tue Jan 23, 2007 9:44 am

RW wrote:
gsf wrote: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
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Tue Jan 23, 2007 10:02 am

Red Ed wrote:
gsf wrote: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)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Tue Jan 23, 2007 2:22 pm

gsf wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Tue Jan 23, 2007 5:41 pm

ronk wrote: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

ronk wrote: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?

gfroyle wrote: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
ronk wrote: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"
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Tue Jan 23, 2007 8:51 pm

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
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby gsf » Tue Jan 23, 2007 11:23 pm

coloin wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Wed Jan 24, 2007 12:11 am

coloin wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Fri Jan 26, 2007 9:54 am

ronk wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Tue Feb 06, 2007 9:47 pm

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
gsf wrote: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
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby RW » Tue Feb 06, 2007 10:06 pm

coloin wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

New 17s

Postby coloin » Tue May 08, 2007 3:36 am

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......
ravel wrote: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
Last edited by coloin on Tue May 15, 2007 9:56 pm, edited 1 time in total.
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby Havard » Fri May 11, 2007 10:38 pm

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
Last edited by Havard on Fri May 11, 2007 8:42 pm, edited 1 time in total.
Havard
 
Posts: 377
Joined: 25 December 2005

Postby coloin » Fri May 11, 2007 10:58 pm

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
Last edited by coloin on Fri May 11, 2007 7:19 pm, edited 3 times in total.
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby Havard » Fri May 11, 2007 11:04 pm

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.
Last edited by Havard on Fri May 11, 2007 8:44 pm, edited 1 time in total.
Havard
 
Posts: 377
Joined: 25 December 2005

Postby wapati » Fri May 11, 2007 11:04 pm

Havard wrote: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.
Last edited by wapati on Fri May 11, 2007 7:43 pm, edited 1 time in total.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

PreviousNext

Return to General