17-clue and 18-clue Sudoku update

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

Postby JPF » Fri Jul 20, 2007 3:57 pm

gsf, I see your additions too.

The way I’m doing it is very “rustic” and based on Havard’s thread :

I pick two or three “home made” 19s and follow the sequence :
Code: Select all
  initial       op.     final         number                                   
    clues               clues     of puzzles                                   
       19                                                                     
       19    {-2+2}x p     19            N1
       19    {-1+1}x q     19            N2
       19    {-2+1}        18            N3
       18    {-1+1}x r     18            N4                                   
       18    {-2+1}        17                                               
                                                                               

p, q, r are small integers.
N1 and N2 depend a lot on the initial 19.
I adjust p, q, r in order to get N4=20000

Up to now, every run gave me at least one and up to 6 (luckily) new 17s.
With my labtop, it takes 24 hours for each run...

But I got 3 free 17s by doing an exhaustive {-1+1} on the Gordon’s list.
3 new 17s popped up ; each of them had a dual {-1+1} already in the list : one from Gordon, one from JPF, one from gsf:D

PS :
Gordon Royle wrote:Do you have a 17-clue Sudoku puzzle that might be new? Or is it just an isomorphic copy of one of the known ones?
Enter your puzzle here and we'll let you know if it's already in the database, or if it's a new one.

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

Postby gfroyle » Mon Jul 23, 2007 8:03 am

gsf.. what do you mean by "dual" here?

When you say that you did a {-1,+1} do you mean that you removed a clue and then added it back in all possible ways? There shouldn't really be any in the list that allow you to get new ones that way so obviously I have been a bit slack in that regard...

More generally, the DB seems to be growing slowly but steadily .. 5-10ish per day from about 5 regular contributors...

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Mon Jul 23, 2007 10:10 am

gfroyle wrote:When you say that you did a {-1,+1} do you mean that you removed a clue and then added it back in all possible ways?

Yes.
It means that if P={xi} ; i=1,...,81, a puzzle Q={yi} derived from P by a {-1,1} and not equal to P is such that :
yi=xi for at least 79 clues (i.e 79 or 80).

Let's say that f(P, Q)=1 ; i'm trying to avoid the word distance.

For a given P, let F(P) be the set F(P)={ Q | f(P, Q)=1}.
F(P) can be empty or have 1,2 or more elements.

gfroyle wrote:what do you mean by "dual" here?

sorry, dual is not appropriate here.
I meant that by doing a {-1,+1} on your list, I found 3 new puzzles P1, P2, P3 not in the list.
For each Pi, F(Pi) had only 1 element Qi ; and Qi was already in the list.

JPF

PS : by doing a {-2,2} on gsf, you get JPF:)
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Havard » Mon Jul 23, 2007 12:25 pm

the 41000 barrier is broken!

Congratulations to everyone who has contributed!:)

Now lets take down 42000!

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby gsf » Mon Jul 23, 2007 2:13 pm

JPF wrote:PS : by doing a {-2,2} on gsf, you get JPF:)

ha
that may be the case for my recent postings too
I have two background processes generating 20-22 clue puzzles and those are searched
with {-2+1}xN, with N: (#clues - N) = 17
those new ones (of mine) might be good candidates for {-2+2} and maybe some havard/JPF combinations

I took one of the more fruitful 22's and and did a havard-type sequence to get ~4K 18's
and that yielded 5 more 17's -- still don't have a good enough feel for that process to automate it

for the unix perusers: I have a shell script that combines the generation, reduction, and gfroyle db query/update (via wget(1))
running one of these has been worth ~5 new 17 per day
if there is interest I can post the script
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Tue Jul 24, 2007 1:55 am

gsf wrote:[
for the unix perusers: I have a shell script that combines the generation, reduction, and gfroyle db query/update (via wget(1))
running one of these has been worth ~5 new 17 per day
if there is interest I can post the script


Interesting...

So you use wget with the POST fields set appropriately.. did you need to look at the HTML source for the page in order to figure out what the names of the fields were?

I have been pondering adding a "bulk submit" function although this raises some problems - mainly that my time is at a premium at the moment, and that our server has a 30-second time limit for script-initiated processes and if someone downloaded a few hundred then that time limit would silently be exceeded....

Cheers

Gordon

PS Sorry for confusing you with JPF...
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby gfroyle » Tue Jul 24, 2007 1:58 am

Havard wrote:the 41000 barrier is broken!

Congratulations to everyone who has contributed!:)

Now lets take down 42000!

Havard


The 41000 was broken by a sizeable bunch of puzzles from a new submitter (or at least someone using a new pseudonym) Lars-Petter Endresen.

Also another new submitter has appeared ... Jim Wilson

The rate of increase appears to be growing not declining and so maybe there are still plenty of unexplored nooks and crannies in Sudoku Space.

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby gsf » Tue Jul 24, 2007 3:41 am

gfroyle wrote:
gsf wrote:for the unix perusers: I have a shell script that combines the generation, reduction, and gfroyle db query/update (via wget(1))
running one of these has been worth ~5 new 17 per day
if there is interest I can post the script


Interesting...

So you use wget with the POST fields set appropriately.. did you need to look at the HTML source for the page in order to figure out what the names of the fields were?

yes -- probably the biggest strength of the www is the ability to read its source
here is a bulk submit script, no need to modify your www interface
Code: Select all
n=bozo
m=bozo@big.top

u=http://people.csse.uwa.edu.au/gordon/sudokuid.php

cat "$@" |
while   read q
do      a=$(
                wget --output-document=- --quiet --post-data="name=${n}&email=${m}&puzzle=${q}" $u |
                sed -e '/^<font color="red">/!d' -e 's/^<font color="red">//' -e 's/<.*//'
        )
        echo $q '#' $a
done

(change n and m as appropriate)
the script reads puzzles from the standard input or from files listed on the command line
the puzzles must be in 81 char per-puzzle form, space separated or one per line

for my use I change the cat command to
Code: Select all
sudoku -f%#0v "$@"

using my solver to make the script accept most puzzle forms
PS Sorry for confusing you with JPF...

no problem, that's the price of terse posts
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Havard » Tue Jul 24, 2007 9:46 am

gfroyle wrote:
The 41000 was broken by a sizeable bunch of puzzles from a new submitter (or at least someone using a new pseudonym) Lars-Petter Endresen.

Also another new submitter has appeared ... Jim Wilson



Both Lars-Petter and Jim are using a alpha version of a software we are working on.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby gfroyle » Tue Jul 24, 2007 1:40 pm

Code: Select all
 wget --output-document=- --quiet --post-data="name=${n}&email=${m}&puzzle=${q}" $u |
                sed -e '/^<font color="red">/!d' -e 's/^<font color="red">//' -e 's/<.*//'

(change n and m as appropriate)

Don't you need some quotes somewhere around ${n} if your name contains spaces?

G
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby gsf » Tue Jul 24, 2007 2:55 pm

gfroyle wrote:
Code: Select all
 wget --output-document=- --quiet --post-data="name=${n}&email=${m}&puzzle=${q}" $u |
                sed -e '/^<font color="red">/!d' -e 's/^<font color="red">//' -e 's/<.*//'

(change n and m as appropriate)

Don't you need some quotes somewhere around ${n} if your name contains spaces?

good question
I believe space works, but maybe only by the grace of some implementations
to be safe use
Code: Select all
m=bozo%20the%20clown
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Thu Jul 26, 2007 12:47 am

gsf wrote:good question
I believe space works, but maybe only by the grace of some implementations
to be safe use
Code: Select all
m=bozo%20the%20clown


Well I can confirm that wget 1.8.2 (which is on one of my machines) does NOT deal with spaces properly, but wget 1.10.2 does...
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Fri Jul 27, 2007 10:55 am

gsf,

I understand that you are doing a {-2+2} automatically after any post of a new 17 in the gordon's DB.
I think it's very usefull.
But could you wait for a while (let's say one day) before doing it:)

I posted a new one :
Code: Select all
ID#: 41088  Date found: 2007-07-27 14:38:22 (West Australian time)

000000000000001023045060000000000004000000506200007000000640800007000010300000000

After that, I decided to check for any {-1+1} and {-2+2} with your program
But too late:(
Code: Select all
ID#: 41089  Date found: 2007-07-27 15:09:33 (West Australian time) by gsf

000000000000001023045060000000000004000000506100009000000640800007000010300000000

btw, this search was awful. It took me 48 hours to crunch zillions of numbers to get only one 17:(

Are you doing a {-1+1}, {-3+3} as well ?

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

Postby Havard » Fri Jul 27, 2007 11:09 am

JPF wrote:Are you doing a {-1+1}, {-3+3} as well ?
JPF

Havard wrote:The 3-off, 3-on is depressing. On the supercomputer I have been borrowing from Intel, an 8-core Clovertown, one sudoku completes in around 4 hours. And the two 17's I have done this search on, no new ones have popped out. On my laptop (pentium 4, 2.0 Ghz) the same search would take around 60 hours, with the whole list completing close to 300 years... I am sure a few hundered 17's would show up, but it hardly seems worth it, when you can create so many more 17's by making loads of 18's in a few days!:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby gsf » Fri Jul 27, 2007 1:42 pm

JPF wrote:gsf,
I understand that you are doing a {-2+2} automatically after any post of a new 17 in the gordon's DB.
I think it's very usefull.
But could you wait for a while (let's say one day) before doing it:)

I actually felt guilty enough after the last one that I decided to wait to check the
latest entries with {-2+2}{-1+1} as a batch after they've had a chance to sit for a while
if the batch is big enough (say ~1000) the 1 day delay comes for free
btw, this search was awful. It took me 48 hours to crunch zillions of numbers to get only one 17:(
Are you doing a {-1+1}, {-3+3} as well ?

like Havard I'm staying away from {-3+3}
its time to think more about the properties of low 20's clue puzzles, if any, that make good seeds
for {-2+1}xN derivations to 17's
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General