17-clue and 18-clue Sudoku update

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

Postby Smythe Dakota » Mon Jan 22, 2007 8:10 am

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
Smythe Dakota
 
Posts: 539
Joined: 11 February 2006

Postby ravel » Mon Jan 22, 2007 10:09 am

Smythe Dakota wrote:... 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).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Mon Jan 22, 2007 11:46 am

Red Ed wrote: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
Last edited by coloin on Sat Jan 27, 2007 11:28 am, edited 2 times in total.
coloin
 
Posts: 1695
Joined: 05 May 2005

Postby JPF » Mon Jan 22, 2007 12:11 pm

ravel wrote:
Smythe Dakota wrote:... 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
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Mon Jan 22, 2007 3:02 pm

Smythe Dakota wrote: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...:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby coloin » Mon Jan 22, 2007 5:12 pm

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

Postby Red Ed » Mon Jan 22, 2007 7:52 pm

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

Postby gsf » Mon Jan 22, 2007 9:26 pm

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

Postby coloin » Mon Jan 22, 2007 10:49 pm

Great coding......
This will be interesting
papy wrote: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
coloin
 
Posts: 1695
Joined: 05 May 2005

Postby Smythe Dakota » Tue Jan 23, 2007 4:58 am

udosuk wrote:.... 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
Smythe Dakota
 
Posts: 539
Joined: 11 February 2006

Postby gsf » Tue Jan 23, 2007 8:08 am

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
Last edited by gsf on Tue Jan 23, 2007 12:54 pm, edited 3 times in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Tue Jan 23, 2007 8:50 am

Great work gsf !

gsf wrote:so there are now 36637 17 clue sudoku
36628 + Papys (3)+ Red Ed's (1)+ gsf's(6)= 36638

gsf wrote: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
Last edited by JPF on Tue Jan 23, 2007 5:12 am, edited 2 times in total.
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby RW » Tue Jan 23, 2007 8:58 am

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

Postby Red Ed » Tue Jan 23, 2007 9:02 am

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

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

JPF wrote:Great work gsf !

gsf wrote:so there are now 36637 17 clue sudoku
36628 + Papys (3)+ Red Ed's (1)+ gsf's(6)= 36638

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

PreviousNext

Return to General