The New Sudoku Players' Forum

[Smythe Dakota]

Just so I can be lazy and not look anything up, do any of the known 17-clue puzzles enjoy diagonal symmetry (a common feature in newspaper puzzles) in the location of the givens? (That is, if there is a given in r1c2, there is also a given in r9c8, and vice versa.)

Bill Smythe

[ravel]

... do any of the known 17-clue puzzles enjoy diagonal symmetry ...

No, gfroyle has checked that, but other kinds of symmetry can be found (see here).

[coloin]

It's awfully tedious

It is tedious because ?
a large search and takes ages just for one puzzle !
b the output is probably a large collection of puzzles and isomorphs already in the list - which have to be compared with gfroyles list
c potentially pointless as we are never going to find a 16

Gordon presumably didnt do the 2-off search exhaustively - for this reason

Having said that......a 4-off search [and more][within this grid] failed to reveal a minimal 18 in/around the grid/puzzle which papy posted. Checker is confirming this.
Edit Checker confirmed that there were no minimal 18s.

Code: Select all

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

This would explain why Gordon didnt find this 17, which begs the question how Papy did ?

C

[JPF]

... do any of the known 17-clue puzzles enjoy diagonal symmetry ...

No, gfroyle has checked that, but other kinds of symmetry can be found (see here).

Have also a look at this Red Ed's thread .

JPF

[udosuk]

Just so I can be lazy and not look anything up, do any of the known 17-clue puzzles enjoy diagonal symmetry (a common feature in newspaper puzzles) in the location of the givens? (That is, if there is a given in r1c2, there is also a given in r9c8, and vice versa.)

Bill, I think the symmetry you referred to should be called "180 degrees rotational symmetry", whereas "diagonal symmetry" should mean "diagonal reflection symmetry" instead, as described in Red Ed's thread shown by JPF above...

But it seemed ravel has somehow caught your meaning despite the incorrect term...

[coloin]

One of papys new 17s

Code: Select all

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

It probably doesnt have minimal 18-puzzles but in a 2-off search three 17- puzzles were found, fairly tediously giving 1-off puzzles only.

Code: Select all

.2.4....9..6.8.........................9.7.....8...61.3....1....9....4.2....6...7 - isomorphic with papys

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

Looking suspiciously isomorphic * this one must be on the list, and from this papy generated the new one.

Would it not be at least more achievable with just a 1-off search ?......[or is this just what papy did ?]

C

[Red Ed]

Looking suspiciously isomorphic * this one must be on the list

Yes, isomorphic, by simple renumbering (following JPF's cue).

and from this papy generated the new one.

Papy said he used untouchables. I take that to mean that it was a truly independent discovery.

[gsf]

Is anyone else bothering to do this #one#two-off search? It's awfully tedious. I wish Gordon had done it for us!

tedious => time to code
I'm running two separate techniques on the entire catalog
should take ~1 day to complete
the seconds one should result in all two-offs
when they're done I'll post the results and methodology

[coloin]

Great coding......
This will be interesting

because one of my method to generate was to eliminate intouchables......

I think papy filtered out the untouchables and exchanged clues in the puzzles which had mutable clues [termed volatile puzzles]. Essentially this is a 1-off search...........he only found 3 which is fair enough for this method.

How many will gsf find........

C

[Smythe Dakota]

.... Bill, I think the symmetry you referred to should be called "180 degrees rotational symmetry" ....

You're right, I meant 180-degree rotational symmetry, not diagonal symmetry. Sorry about that.

Bill Smythe

[gsf]

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

000400000056000100000230000200000930600005000000070000370000005000004600000000000
000406700050700000089000004000090050004000000000000200000000006500200000010000090
003450700000000000890000010005060000700000008000001020000000600010008000000000005
100000700000009030608200000000500600000000190030002000000000000500610000000000020
103000000000000060000007005008000000306000090000042100000600004070000008000300000


the second (and faster) technique used a neighborhood tour:

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. The output is the list
of puzzles, one puzzle per line, containing two space separated fields: the
puzzle in %c form and the partition class ordinal.

each puzzle is canonicalized early to prune tours that have already been done

so there are now 36637 17 clue sudoku

here are the class size (#puzzles) and #classes with that size for the partitions induced by the tour

Code: Select all

1       15774
2       3815
3       1021
4       590
5       253
6       162
7       97
8       59
9       46
10      30
11      26
12      18
13      16
14      8
15      3
16      9
17      5
18      5
19      4
20      4
21      1
22      3
23      1
24      5
25      5
27      2
28      1
30      1
31      2
32      2
33      1
37      1
38      1
41      2
42      1
50      1
55      1
87      1
173     1
560     1
616     1


e.g. "616 1" means that there was 1 class containing 616 puzzles -- take any member
from the class and tour it and it will produce 616 17's
here is the first (in row-normal canonical order) member of the 616 class:

Code: Select all

000000000000009100700200005090004000000000027010000006000000300041000900000670000


here are the number of 17's per grid and the number of grids containing that number

Code: Select all

1  32247
2  1504
3  228
4  80
5  18
6  20
7  7
8  3
9  1
11  1
12  1
14  1
20  1
29  1


[edit]
finally, Red Ed's and three of the new 5 were from new solution grids

Code: Select all

123456789456789123789231564215648937637925841948173256371862495592314678864597312
123456789456789123798132564274593816861274935935618247312965478587341692649827351
123456789457189263869237415218963547346715892795842136531628974674591328982374651
123456789457189263896327514245863197761942358938571426382795641514638972679214835


[JPF]

Great work gsf !

so there are now 36637 17 clue sudoku

36628 + Papys (3)+ Red Ed's (1)+ gsf's(6)= 36638

here are the class size (#puzzles) and #classes with that size for the partitions induced by the tour

Code: Select all

1  32248
2  1504
3  228
4  80
5  18
6  20
7  7
8  3
9  1
11  1
12  1
14  1
20  1
29  1


How does it fit with your 36637 ?
[edit : OK, no answer required, thanks]

JPF

[RW]

6 new 17's popped out

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

RW

[Red Ed]

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.

[gsf]

Great work gsf !

so there are now 36637 17 clue sudoku

36628 + Papys (3)+ Red Ed's (1)+ gsf's(6)= 36638

here are the class size (#puzzles) and #classes with that size for the partitions induced by the tour

Code: Select all

1  32248
2  1504
3  228
4  80
5  18
6  20
7  7
8  3
9  1
11  1
12  1
14  1
20  1
29  1


How does it fit with your 36637 ?
[edit : OK, no answer required, thanks]

I'll answer just to clarify clerical errors (now corrected) in my post
I had counted Red Ed's in the 6 new -- should be 5 new
and the 32248 should be 32247 (a puzzle file comment was counted as data in a big pipeline)
with those fixes the tables add up
thanks