17-clue and 18-clue Sudoku update

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

Postby gfroyle » Thu May 17, 2007 1:18 pm

Red Ed wrote:Can you tell/remind us how your search works please?


It's a sort of local search.

Start with an initial puzzle, and then alter it slightly - maybe change a digit, or possibly make a digit equal to 0 while simultaneously making a 0 equal to another digit.

In string / code terms this means that I am looking at the 81-character strings that differ in either 1 or 2 positions from the original puzzle (i.e. have Hamming distance 1 or 2 to the original).

Then if we are lucky we get a new puzzle, in which case we add to the pile to be processed and continue...

[This seems similar to the 2-on/2-off thing though I haven't quite worked out what the terminology means]


But of course we are not usually lucky and so the whole process dies...

So what I do is to keep any pseudo-puzzle that has "few" completions (say less than 10 or maybe 20) hoping that a subsequent "move" from one of those will land us back onto a real puzzle with a unique completion...

The reason that Ocean's puzzles were "far away" from the other ones was that I had to permit an intermediate pseudo-puzzle with about 50 completions in order to "connect up" with the existing collection.


On a related note, I heard again (by sheer coincidence) from my Japanese correspondent (Noshita Kohei) who sent me a new batch of 204 new puzzles.

So we're closing in on 40000 more rapidly than I thought...


Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby ronk » Thu May 17, 2007 2:47 pm

gfroyle wrote:On a related note, I heard again (by sheer coincidence) from my Japanese correspondent (Noshita Kohei) who sent me a new batch of 204 new puzzles.

So we're closing in on 40000 more rapidly than I thought...

You didn't pick up the last 68 or so 17s that Havard posted here. Also for some reason he never added the 14 1-offs and 2-offs based on those puzzles (that I pm'd to him). They are ...
Code: Select all
...3.....6.....7.....5..........18...34.......2....5..9....6.4....4.7.3.........2
...3.....9.....7.....5..........98...34.......2....5..1....6.4....4.7.3.........2
...3..6.8......7....1..........2..1967.......3...........7.45..8......2......9...
...3.....6.....7.....5..........19...34.......2....5..1....6.4....4.7.3.........2
...7..3....8.......1.............91.7..3.....2....8....4.59..........6.8....4...1
...54....3.1....7.6.............913..8..5.............2..3.6....7....4.5.........
...3.8.2.6.1...4.....5......8.2.........7.1...............6...123.8...........7..
6.4....81...3..........2...2..9..7....1............9...5....3......18..6....4....
...3..6.8......7....1..........2..1967.......4...........6.45..8......2......9...
....4.6...7..8.....1.......9.2...5.....17..3....8.....5....2...4.....8..........7
...8....59.1..............4.8.4.2...3...1.9..............79.1..6...3.....2.......
...9...7.3...6....6...2.....5....3........1.6...8......8.....2.....34......61....
....2.1.46.7.3............59..6..7.....4.....8.........4...2.......9.3...1.......
....2.1.46.7.3............53..6..7.....4.....8.........4...2.......9.3...1.......


A few of the above 82 (=68+14), having also now been found by others, are already in your database. Combining these should result in a new total of at least 39754.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Ocean » Thu May 17, 2007 8:00 pm

Thursday evening puzzle (new 17):
Code: Select all
...............12..34...5...........26...7......8..3.4....6...2...32....1......7.


One apple a day...
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Red Ed » Thu May 17, 2007 9:49 pm

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!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Havard » Thu May 17, 2007 11:17 pm

to avoid confusion, I will just post these that are not in your 39681 list:
Code: Select all
6.4.........8..3...........1...4.....8....5.1.....7.......62.4..3.5.......7.....8
6.4.....8...3.....5............45....1....8........12..3.78.....9......6.......5.
6.4.........2..5..1.........5....4.7....16....9..........57.2..3......6....4.....
...29..7.8...6..............715...........8.4............6..3...9...3.1.4...8....
...2..84....5.....1............4.26..5.3.....7......1.92....3.......7.......1....
.6.2.....1..6....7............5..12.4.9......3.........2....6...7..4........3...4
...2....476.....3.1............7.1...2..6.....4......5...8...2.......6...9.4.....
.......1782..................174..........56.....1.2..437..........96...1........
7..3...6.8.....5.....1......31..........8.4...2..5.......6...3.....4....5......7.
....2.1..4..............76..3...8..4.1.6............2.2.4.....5...71....5........
...3.62..4...........2.....1...4..768.....5.............6.7..4..2.5.............1
...3.62..4...........2.....1...4..868.....5.............6.7..4..2.5.............1
...3.8.....97......1....6..82.6...........9.47.....1..2......7.....1...........8.
...3.8.2.6.1...4.....5......8.2.........7.1...............6.7.123.8..............
...3.....9.....7.....5..........18...34.......2....5..1....6.4....4.7.3.........2
...37.8...16........5......84....3.......1.........2..5..23......1....6....8.....
...4...175............6.8......326..1.4......7.........2.1.4....8....3...........
...4...38.2..............9.....9.2..5.....1....7.23......5..67.3.8...............
.......7.6....2......4....1.45...2....7.1.......6..8..3..2..6......7...........5.
...4.81..25.......6.........7.3.........5...4.......2.4...2.....3....7.......6.1.
...4.81..25.......6.........7.3.............4....5..2.4...2.....3....7.......6.1.
...4..12.3.5.......6.......7.8....5....1..6..........341....2......85............
...4..2.68..5...........7...62.7...........4..........3......1.....2.9..4.98.....
....4.6...7..8.....1.......6.2...5.....17..3....8.....5....2...4.....8..........7
...4..6...7.8......1.......6.2...5.....17..3.....8....5....2...4.....8..........1
...4...5.3...1.....8....2..6..3.5..1.......8....7.....4.....7......829...........
...4...5.3...1.....8....2..6..3.5..1.......8....7.....4.....7......82.........9..
......8..5.1.6....7.......41...74....8....2............9.2.8..........41...3.....
...4.5..382.....6.............3..4..6...8....2...........9..5......2..8...4...1..
...4.69..1.2......3............2..3..4.9..7......1.....8......56....2.1..........
...4.9...7.5...3.....6.....2...........8...9.3.......514..3.....9.....6.......2..
...43.2...6.2.....1............71....2....4...3.......7......515......8....6.....
...45.3..2...........1.....6.....1..7....2.......8......13...8..8......2.4.....7.
...5...2..8....3...1.......7..4.2......6..1..3.......8..2.8.9..4...............7.
...5...4....8.....6.9...3...1..3..5.....97.....3.......5.1..6..........9......7..
...5...842........1..4....7.....21.6....9.2...8........4.8...........9......3....
...6..1..7...........5....839...........4...7.5.....4.1...78..........9..6....5..
....2.1.46.7.3............53..6..7..8..4...............4...2.......9.3...1.......
....2.1.47.8.3............56..7..8..9..4...............4...2.......6.3...1.......
...5.72...1.......6......3..7..8...4..2...5......1.......3.....8.......1..72.....
...5..31.2.........8.........135............4......8......84..23.2....7....6.....
...5..8...1..7.4..2..........8.......5...8.3....6...2.6...32...........1......5..
...5.1...27.......8...........9..1.46...2..........5...354............2...4.7....
...52.8...41..........3....6.....7..53...4........9.1.2.......3...7...4..........
...53......4.......1....7.....2..1.73..............4..52.....9.....61...8......3.
...53......1...4......2.....8.1.4..........23............6..1..37.....585........
...54....3.1....7.6.............213..8..5.............2..3.6....7....4.5.........
...6...4.19.....2.8....3.......1.8..74........5..........5........42..........1.7
...6..3..12........4...........21.8...4...51.....9......34........3..6..2........
...6..5.7.91..........3....4..2.....2....7.........9...5..9..1.7.......2.......4.
.....41.623........9.......8..7...2.......53.........94.....6.....39........5....
...7...1..4.....3..6.......2..5..6...3....4...............345..7....8...1...6....
...7....83...1..............5......7....4.23...8......2.....14..8.5.6.........3..
...7..28..35...................516..84.....3....2.........3......1...5..2..9.....
...7..3....8.......1.............91.7..3.....2....8....4.59..........68.....4...1
...7..51.83...9............2......4.1.5.3.......9......9....3.6...1.............8
...7.1....9....5............3.58....6......7.....9....7.4..3........69..1.....8..
...6.5..12......4.3..8.......5.2.3...1.......68..........1...7.9.....2...........
...73.......9....84.....6......8.5.67.2........9...........62...9.....7..5.......
...8....59.1..............4.5.4.2...3...1.9..............79.1..6...3.....2.......
6.4....81...3..........2...2..9..7....1............9...5....3......18..5....4....
...1...238.6.............7....5.86...3....1...2..7....1.....5......2..4..........
...1..23..5....4...........7......1.....52.......4....1.4.....9...89.5..3........
.1.23...........47..9......8.2..4.........1..4.........3.6.....7......2.....1.5..
1..2...3....3.8.5.4...........7..1...8....4.9.3...........1.6.........8.7........
1.2...3..4.......2...8......8..9........1.4...5........6.5...8.3......9........6.
1.2.3.....6.4...8..........3...1.2...5..............6.7.....1.3.4.6........5.....
1.2.3.....6.4...8..........3...1...2.5..............6.7.....1.3.4.6........5.....
....1..2.4.....7...8..........5..8.4.2...............5..7....315..6.8......4.....
...1.2.4.75.....3..........3..8.....6.....5........1.6..2.5........76....1.......
.12..4....9.7..38..........3..6..7...4...1...................918........5..3.....
1...26....7....3.............48.....6......5....3....1.3.74......2.....6.......1.
12....7.....35..8..........7...12...5......4............4..6....964...........1..
....12....7....9.......5....6.2...........31.2..4........7..4..3...8....1.5......
1.....2........8.....5......5.3......4.....6.....1.7.....6....37...2.....9.4...5.
1.....2........8.....5......5.3......4.....6.....1.7.....6....37...2......94...5.
1...2.7..3.8..........9....6..1....3.7..5...4............3......4....2.....8.4...
1..2......5....3.......1....36.7...........2..8....5.92......4....83....7........
1..2.7....9....3.....4.....7.4.....2...1..6...............5.89.4.2..........3....
...27...183....5.............1..8.74...3............6...7.4.......6..3..2........
1.2...7.....5..4..3...8.....5...76.4.............1.......2...1..6.4.....8........
1..7..3......3..4.6.....9.......41...4..2....7.......65..6......3.....2..........
....2...8...6...5.9......4.....3.2.74.59.....8.........2..........4.......3...1..
1.....2...8.................52.....4....3.6...4..9...73.....19.7..4........5.....
.12.....9...5...4..........6......3..8...1............5..34....4...6.8...9....1..
1..2....9..8..3.........2..6..14....8.....3........5...3.....1....6...4..5.......
...1..3.2.4.....7.6..5.....1..3....8....6..4...........6..47...3.....1...........
.1....3.........2.....6.......2..1.5.3....4..6..8.........4....9.2....7.8......6.
1.....3....26.......85.....34....1.....2.5.6.................524...3....7........
1..3.......2....5......9.......25.6.34........7..........4..1.3.....6......8..2..
13..........2...6......8.5...8....2.....1.......6..4..4.....1.7......3.....5.3...
13........28.........7....54......76....132...............2.3..5..4.............4
...1..34.62...5.8.............6.......4...7.......2...2...4........3.1..8.......6
..1...3.....4....5.........5.2.1.....4......6.....98...2.64....7.....19..........
.13....4....2.9............9....58..2..6............3.85....2......3...1....4....
.13.4.....8.6...5........2.9..2.5......7..8..........3..4.3.1..2.................
19.....34..4.5...........7..1....5.8...3.7......6.........4.2..6........3........
1.....34..2.7..............5.4....8....21......6.......7....2.3.....5.......4.7..
.135....8....2.7..............1...3.7...6....2......5.6....72........4.....3.....
.13...6......82............8...7....4.6............1...5.1.3.7.9......8....6.....
...8.5.1..2....6...........81.5.........7.9.43.........4..2..........7.......3.8.
...81....1......9.5.....3....76............13..8......3....2....4....6.....7...8.
...9..4.67.....5..1.........4...362.3...1................7...1..6..5............3
9.1.....4.....37......2....5..14.....2....63....8........5....1.8.........2......
6.1.....4.....37......2....5..14.....2....63....8........5....1.8.........2......
9.1.....4.....3.......2.7..5..14.....2....93....8.....6..5....1.8................
..1....7....2.......6.........41.5..76....2..3............67.3.82............4...
..1....7....25.......8........4..5..76....2..3....9........7.3.824...............
..1.8........2.3.........6.32........4.....8........1.78....4.....1.9...5..6.....
..17...........4.........3...8.93.........1.6.......2....64.5..93.......2....5...
..18...........2.6......9..65..9...........143...........1.4.5.92..........7.....
..3...6.2...45..................63..4...7....85.......7.....15....8...4......2...
..3...6.87.....3.....2.........36....4.....2.....9..5.....7.....8.1...4..2.......
9.3..........4..76......1.....2..3..67........1.......2.8...5......74.......6....
..4..28...1.7..............5...........6....7..3...2......243..7......1..6..8....
..43...173...2...........9....56.8..91.............2..4.....6.....1............3.
..47......3......6.......2..5.1..4..........96...7....2...64.........5........71.
..6....25...9.1...8..........5.3.......4..1...2...........65...1....87..4........
..6.7.2.......4.87.5.......8..3.9......5...........6.........957..61.............
..61.....2.......3.....74...7....5..3.........4..........23...6.85...7......4....
6.4....81...3..........2...2..9..7....1............9...5....3......18..6....4....
...81....1......9.5.....3....76............53..8......3....2....4....6.....7...8.
...3.....6.....7.....5..........18...34.......2....5..9....6.4....4.7.3.........2
...3.....9.....7.....5..........98...34.......2....5..1....6.4....4.7.3.........2
...3.....6.....7.....5..........19...34.......2....5..1....6.4....4.7.3.........2
...7..3....8.......1.............91.7..3.....2....8....4.59..........6.8....4...1
...54....3.1....7.6.............913..8..5.............2..3.6....7....4.5.........
...3.8.2.6.1...4.....5......8.2.........7.1...............6...123.8...........7..
....4.6...7..8.....1.......9.2...5.....17..3....8.....5....2...4.....8..........7
...8....59.1..............4.8.4.2...3...1.9..............79.1..6...3.....2.......
....2.1.46.7.3............59..6..7.....4.....8.........4...2.......9.3...1.......

Bringing the list up to 39812. I think these might include ronks, so he should be credited for that. This does not include oceans, unless you have counted him in your 39681.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby coloin » Fri May 18, 2007 7:29 pm

gfroyle wrote:Puzzles #39451 and #39452 (which is the numbers they were given) are "far away" from the other 17-clue puzzles according to how I search for them...


Are these the first puzzles to have this property, if not how many have you got ?

Are you keeping a record of all the puzzles which are related because of a equivalent 15 clue subgrid to be found within another 17 clue puzzle. These are all members of the group of puzzles which can be toured by successive exchanging of 2 clues.

Have you got means to canonicalize the subgrids ?

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby ronk » Fri May 18, 2007 7:48 pm

coloin wrote:Have you got means to canonicalize the subgrids

Interesting question, but when the subgrid has multiple solutions aren't there multiple canonical possibilities?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Fri May 18, 2007 8:05 pm

ronk wrote:
coloin wrote:Have you got means to canonicalize the subgrids

Interesting question, but when the subgrid has multiple solutions aren't there multiple canonical possibilities?

it depends on the canonicalization algorithm
I based mine on the solution grid -- the algorithm basically canonicalizes the solution grid,
which can be done by some fast and efficient code (using techniques similar to the sudoku counting algorithms),
and then maps the puzzle grid onto the canonicalized grid (modulo automorphisms)
to determine the row order minlex canonical form (based on the solution grid)
the drawback for this algorithm is that it won't work on multi-solution subgrids

you can also do row-order minlex on subgrids and ignore the solution grid
this algorithm degrades with the number of clues, but is very efficient for <~20 clues
I used code from Michael Deverin in my solver for subgrid canonicalization
which is used to prune the number of grids visited in the -gaN -goN -grN tour generators

you can use -go0 (dash gee oh zero) on a list of subgrids (e.g., multi solution puzzles) to list
the row-order minlex subgrid canonical grids

I believey the nauty based canonicalization also degrades with number of clues
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Fri May 18, 2007 8:41 pm

gsf wrote:you can also do row-order minlex on subgrids and ignore the solution grid

Duh! I was only considering canonicalizing via the solution grid.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby JPF » Fri May 18, 2007 8:55 pm

Let n be 10^81.
We can define a canonicalization of the subgrids as follows :

A canonicalization c of the set G of the subgrids is a map from G to the set of integers {0,...,n} such that :

for every g1 and g2 of G : g1~g2 <=> c(g1)=c(g2)

~ is the usal symbol for equivalent subgrids .

So, for a given canonicalization c and for each subgrig g, there is only one canonical form c(g) and the number of solutions of g does not matter.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Fri May 18, 2007 11:03 pm

JPF wrote:Let n be 10^81.
We can define a canonicalization of the subgrids as follows :

A canonicalization c of the set G of the subgrids is a map from G to the set of integers {0,...,n} such that :

for every g1 and g2 of G : g1~g2 <=> c(g1)=c(g2)

~ is the usal symbol for equivalent subgrids .

So, for a given canonicalization c and for each subgrig g, there is only one canonical form c(g) and the number of solutions of g does not matter.

oh, maybe I wasn't clear above
your expression is what I had/have in mind (and use in practice)

I used the term subgrid to mean grids with multiple solutions
the subgrid canonicalization algorithm did/does not require multiple solutions to work
so I was loosley assuming subgrids as being grids with < 17 clues => multiple solutions,
not appropriate for solution based canonicalization,
well suited for subgrid canonicalization (in both requirement and efficiency of algorithm)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Sat May 19, 2007 12:59 pm

coloin wrote:Are these the first puzzles to have this property, if not how many have you got ?


No.. some of the ones sent to me by Noshita Kohei were also very distant from others that I had then...

I haven't kept systematic records of that sort of information, mainly because the list of known puzzles keeps growing and so "distant from known puzzles" keeps changing its meaning...

But in general terms it seems that there is a huge bunch of puzzles that are all "relatively close" to each other, and then a large number of much smaller clusters. I'm working on formalizing this concept to get a picture of the entire "17-clue Sudoku puzzle space".

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Sat May 19, 2007 10:14 pm

gfroyle wrote:...
But in general terms it seems that there is a huge bunch of puzzles that are all "relatively close" to each other, and then a large number of much smaller clusters. I'm working on formalizing this concept to get a picture of the entire "17-clue Sudoku puzzle space".

In the Sudoku space thread, there's been a lot of discussions about the definition of a distance (metric).
I'm curious to know the distance you are going to use : the Hamming distance between real puzzles, between canonical forms or something else ?

Thanks.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gfroyle » Sun May 20, 2007 12:44 pm

JPF wrote:I'm curious to know the distance you are going to use : the Hamming distance between real puzzles, between canonical forms or something


It will be something else, based more on an unusual graph-theory concept of distance than on the coding theory concept of distance.

In the thread you mentioned, various options are given for the distance between two puzzles A and B. Now to my mind we clearly want to view a puzzle as representing the entire equivalence class of puzzles that can be obtained by permutations, rotations etc, and so D(A,B) must be invariant under replacing A by A' and B by B'. This means that you are basically forced to take D(A, B) = min { d (A', B') | A' ~ A, B' ~ B }. [This *does* satisfy the triangle inequality so it is a legitimate metric on the set of equivalence classes.]

But this sort of Hamming distance doesn't really give me a good view of how hard it is to find a puzzle given an initial puzzle. Even if two puzzles have large Hamming distance, then provided they can be "connected" via a sequence of intermediate (pseudo) puzzles with a low number of completions then I want to think of them as "close".

So my definition will work pretty much like this: consider a graph defined on all the 17-clue pseudo-puzzles where there is an edge between two puzzles if a single "alter one or two values" move converts one to the other.

Then the "distance" between two puzzles is the lowest value k such that there is a path between them that uses only intermediate pseudo-puzzles with k (or fewer) completions....

Basically I don't care HOW MANY steps I must take, but I do care about how "bad" the intermediate puzzles can get..

It's not really a well formed concept yet, but hopefully you get the idea..

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Sun May 20, 2007 5:45 pm

gfroyle wrote:It's not really a well formed concept yet, but hopefully you get the idea..

Yes, thanks.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General