The New Sudoku Players' Forum

[gfroyle]

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

[ronk]

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.

[Ocean]

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...

[Red Ed]

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!

[Havard]

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

[coloin]

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

[ronk]

Have you got means to canonicalize the subgrids

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

[gsf]

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

[ronk]

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

Duh! I was only considering canonicalizing via the solution grid.

[JPF]

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

[gsf]

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)

[gfroyle]

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

[JPF]

...
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

[gfroyle]

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

[JPF]

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

Yes, thanks.

JPF