Making 17's from JPF's 19

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

re: #40582 (submitted with zeroes)

Postby Pat » Sun Jun 17, 2007 3:37 pm

gfroyle wrote:
Havard wrote:
thanks Pat!:) Funny that all the others would enter without the zeroes...

Havard


They don't have to be entered with zeros...

The problem is likely to related to some issues here with the computer on which the database is stored; hopefully these are now resolved..

Gordon

sorry but the problem hasn't been resolved -- just try it again with that same example

Code: Select all
.1.....82.3.4.5.........6............8.3.......65..2....2.........9.1.3.5........


or to illustrate the trouble: you can even truncate it to
Code: Select all
.1.

(just the first 3 characters) and still you get the blank-page response
User avatar
Pat
 
Posts: 3465
Joined: 18 July 2005

Re: re: #40582 (submitted with zeroes)

Postby gfroyle » Sun Jun 17, 2007 10:10 pm

Pat wrote:sorry but the problem hasn't been resolved -- just try it again with that same example


Hmmm... you are right.

I must have introduced a bug when I altered the script .. I will chase it down and fix it up..

Thanks for letting me know..

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Mauricio » Mon Jun 18, 2007 7:10 am

I have implemented too a subvariation of your technique and I have found so far 4 new 17's.

I use my own solver, it is slow compared to other solvers and it will take many hours for me to do a 2off/1on search, so I just use 1off/1on to generate loads of valid puzzles and then I try to remove clues for from them (a sort of 2off/1on).

JPF wrote:My question is : what 19s (or whatever number of clues) are the best ones to start with ?


I don't know the answer to that.

I start from a list of >30 "random" 21's, it is fast to generate them randomly, then I do a nested 1off/1on until I have 50K 21's, it takes aproximately 20 mins to do that. Then I look for 20's in those 21's and from that list of 20's I do a nested 1off/1on to find 50K 20's, it takes ~30 additional mins. Then I look for 19's and so on. Searching for 50K 18's takes me ~3 hrs. It is time now to find some 17's in there.

Here are some interesting twins I found and twins that were already in gordon's list.
Code: Select all
. . .|. . .|. . 1
. . .|. . 2|. . .
. . 3|. . .|. 4 5
-----+-----+-----
. . .|. . .|6 . .
. . .|. 4 .|. . 7
. 2 8|1 . .|. . .
-----+-----+-----
. . .|8 . .|. 3 .
5 . .|. . 7|. . .
7 . .|. . .|2 . .
Code: Select all
. . .|. . .|. . 1
. . .|. . 2|. . .
. . 3|. . .|. 4 5
-----+-----+-----
. . .|. . .|6 . .
. . .|. 4 .|. . 7
. 2 8|1 . .|. . .
-----+-----+-----
. . .|9 . .|. 3 .
5 . .|. . 7|. . .
7 . .|. . .|2 . .

Let's call the above puzzles cell twins, and the following puzzles box twins.
Code: Select all
1 . .|. 5 .|. . .
. . .|1 . .|. 3 .
. . 7|. . .|2 . .
-----+-----+-----
. 5 .|. . 8|. . .
. . .|. . 7|. . 1
6 . .|. . .|. 7 .
-----+-----+-----
. . 9|. . .|8 . .
. 3 .|. . .|. . .
. . .|6 . .|. . 5
Code: Select all
1 . .|. 5 .|. . .
. . .|1 . .|. 3 .
. . 7|. . .|2 . .
-----+-----+-----
. 5 .|. . 8|. . .
. . .|. 7 .|. . 1
6 . .|. . .|. 7 .
-----+-----+-----
. . 9|. . .|8 . .
. 3 .|. . .|. . .
. . .|6 . .|. . 5
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby coloin » Mon Jun 18, 2007 7:08 pm

Well done on devising your own program, and its amazing that we are still finding new 17s even now !

I think a clue which could change value and give a different valid puzzle was aptly termed a "mutable" clue. Excellent searching gave the maximum mutable clue in a puzzle was 8.....[we gave up trying for a 9 !]

The box twin is effectivly a 1off/one on.....but there were some twin puzzles termed sister grids which differ by one unavoidable set.

C
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby Havard » Tue Jun 19, 2007 3:48 pm

coloin wrote:Well done on devising your own program, and its amazing that we are still finding new 17s even now !
C

My guess is that it is lots more to find. I expect 50,000 to be reached by the end of the year!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Tue Jun 19, 2007 4:20 pm

Havard wrote:I expect 50,000 to be reached by the end of the year!:)

To what percentage of Gordon's 18s have you applied the 2-off/1-on?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Tue Jun 19, 2007 9:59 pm

ronk wrote:
Havard wrote:I expect 50,000 to be reached by the end of the year!:)

To what percentage of Gordon's 18s have you applied the 2-off/1-on?


I only did that to one of his 500000 lists. It produced over 30000 different 17's but only very few new ones. My guess was that Gordon has done something similar to his 18's, and that the high number was not a coincidence. It made me want to produce my own 18's instead, which have had a lot higher "new per 17" factor.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby gfroyle » Thu Jun 21, 2007 12:31 pm

Havard wrote:It made me want to produce my own 18's instead, which have had a lot higher "new per 17" factor.
Havard


This is crucial I think because my 18s are heavily associated with the existing collection of 17s.. a lot of my earlier techniques involved hopping between 17s and 18s and back again.

So anything derived from the existing collection of 18s will have much higher than expected overlap with the current 17s.

However it is nice to see that a day rarely passes without another ten or so 17s added to the database by a number of dedicated submitters!

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby gsf » Thu Jun 28, 2007 7:58 pm

apologies for the long note
I'm purging before a two week sans electronic device holiday

thanks to posts and pm's from Havard, coloin, and ronk I was able to track
down a few problems with the -go (off/on tour) code in my solver, especially for the order of
magnitude difference in runtime between my solver and Havard's generation sequence at the top of this thread

define verifier: a backtracking algorithm that verifies that a puzzle has exactly one solution

it turns out that having a fast verifier may encourage lazy programming

Havard uses a DLX verifier which is slightly slower than the small verifier that I use
the main difference is a higher startup cost for the DLX verifier
(that startup cost ends up being a wash for larger problems, but is significant for 9x9 sudoku)

the hard part of off/on tours is the on phase where one or more clues are added to pseudo-puzzles
(puzzles with more than one solution) in order to generate valid 1 solution puzzles

a straightforward way to do this would be
Code: Select all
for i in candidates
   set candidate in puzzle
   verify that the puzzle has one solution
end

Havard provided a hint that instead of #candidates calls to the verifier he amortized the
DLX startup cost by starting up the verifier once, and set/unset each candidate within the verifier

that insight had little effect on my verifier implementation
(because startup cost is not a significant issue)
but the idea of doing one search instead of #candidates stuck

when checking for multiple solutions the verifier backtracking algorithm is allowed to proceed past the first solution:
either it will find no more solutions, which means a valid puzzle, or it will find another solution

the set of all solutions can be modeled as a tree, with candidate assignments at the nodes
this also models the verifier backtrack search tree
early candidate assignments appear higher up in the tree, close to the root
a branch with multiple solutions will have one or more nodes near the root with the same candidate values,
and then fork at a critical candidate (a candidate required for one solution)

each of the candidates that are the same from the root to the critical candidate cannot be a critical candidate
(why? because they were assigned earlier on the branch and the branch still led to more than one solution)

so all of the candidates from the root to the point where the solutions branch can be pruned from
the critical candidate search as the verifier backtracks
this insight, along with a few verifier tweaks, recovered the order of magnitude time loss

once the verifier was fixed I was able to add a better interface that allows multiple
off/on sequences to be combined into one command

for example, Havard's sequence can be specified as
Code: Select all
sudoku -goc{-1+1}x3{-2+1}{-2+2}{-1+1}x9{-2+1} -Ff%2F%8#et%9#an%9#sn jpf-19.dat

(three 1-off/1-on, one 2-off/1-on, one 2-off/2-on, nine 1-off/1-on, and a final 2-off/1-on)
-goc uses the -Fc format to output puzzles grids (the grid with no constraint method stats)
-Ff... lists the elapsed time, #puzzles generated, and #puzzles searched on the standard error

on a linux 3.2Ghz pentium this reported
Code: Select all
  45m23s        6 26286371

~46 min elapsed time
6 puzzles (the same Havard generated)
26,286,371 possibly dup (pseudo) puzzles checked

I have a small catalog (~20 puzzles) of 22's generated by -gH (using the hardest sudoku clue placement formula)
with -q1 rating > 9999 and extracted two new 17's (#40726 #40727) using
Code: Select all
sudoku -go{-2+1}x5 -f'%v # %T' h-22.dat

where each application of {-2+1} drops one clue, so 5 rounds goes from 22 to 17 clues
and the -f format lists the puzzle grid and the time it was found

I then ran this on the two new entries to see if there were any more new ones in the neighborhood
Code: Select all
sudoku -go{-2+2}x2 -Ff%2F%8#et%9#an%9#sn -f'%v # %T' new-17.dat

it ran for ~20m and only produced the original 2 puzzles -- so its a pretty tight neighborhood

you can use -gon... to show what a sequence would do without executing the sequence
some sequences can go on for hours @2Ghz, and some sequences have the potential
to exhaust memory (dup pruning is done at each off/on phase using splay trees on subgrid canonicalized keys)

one (known) caveat -- a recalcitrant bug sometimes omits a small number of puzzles in combined
off/on sequences that would otherwise be listed if the sequence were done separately; if exact
results are required (no omissions) then use separate commands, each with one off/on sequence and optional xN

solver version 2007-06-28 posted
Last edited by gsf on Fri Jun 29, 2007 5:35 am, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Fri Jun 29, 2007 2:09 am

after the previous post I let -go{-2+1}x5 loose on 3 hard 22 clue puzzles,
and after 3h25m and 149916548 puzzle checks @3.2Ghz it produced 8 17's,
one of which was new #40731
so start burning those sleep time cycles on sudoku search instead of screen savers
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Fri Jun 29, 2007 11:41 am

I will !

And I can then have my very own 17 !

for the casual browser gsf's windows executable is here

others available here

What will be the most efficient command line from a set of 18s ?

Will {+2-1} or {+2-2} work for the "max clues" generation ?

C
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby gsf » Fri Jun 29, 2007 1:11 pm

coloin wrote:What will be the most efficient command line from a set of 18s ?

I don't have a feel for the right method of attack
or what sequence has the best chance of generating low clue puzzles
at least its now easy(er) to play with
Will {+2-1} or {+2-2} work for the "max clues" generation ?

it should work in theory but hasn't been tested thoroughly
you have more experience on max clues, so I'll wait for a success/failure post
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Sun Jul 01, 2007 8:52 pm

gsf wrote:so start burning those sleep time cycles on sudoku search instead of screen savers

I will! Just did a {-2+1}{-2+2}{-2+1} on the first 400 of Nick70's Complete Sudoku Collection - Vol. 1. The result was 14 17s, but only one new:
Code: Select all
 *-----------*
 |1.7|.5.|...|
 |...|...|.3.|
 |5..|...|4..|
 |---+---+---|
 |.5.|..8|...|
 |9..|...|..1|
 |...|6..|.7.|
 |---+---+---|
 |..4|...|8..|
 |.3.|...|...|
 |...|.9.|..5|
 *-----------*

Notice the nice ARS - "Almost Rotational Symmetry":D

For some reason I get an error message when I try to access gfroyle's sudoku identifier. Anybody else have this problem?

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Sun Jul 01, 2007 9:44 pm

Yes

I just did a
Code: Select all
sudoku -goc{-2+1}{-1+1}x4{-2+1}{-1+1}x3{-2+1} -Ff%2F%8#et%9#an%9#sn  20.txt

on 5 random 20s

after 24 hours it was still on the third puzzle - and jamming up.....

There were 15 17-puzzles

3 are/were new:D

The identification service is now working !

Code: Select all
'000000709000000000080201000000000000015000020900070000370090000000800014600000000'
'000050700406000000008000000000600008070021000900000500002000000000030000800000064'
'000406000000700000009000000060000300000007010000092500000000076005830000040000000'


There are no 17s within 2off/2on of these

I didnt get any new 17s when I searched 18s or 19s so perhaps the spread out from a 20 is more productive. Perhaps best to do one puzzle at a time !

C
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby JPF » Mon Jul 02, 2007 10:02 pm

It was my turn : #40746, #40752, #40753

Thanks again Havard and gsf:)

[edit]
Here's the log for the last 2 ones.
Start with a 19 clues with an empty box.

Code: Select all
  initial       op.     final         number                                   
    clues               clues     of puzzles                                   
       19                                  1                                   
       19    {-2+2}        19            163                                   
       19    {-1+1}        19           1255                                   
       19    {-2+1}        18             92                                   
       18    {-1+1}x4      18           8593                                   
       18    {-2+1}        17             46                                   
                                                                               
  New 17s                  17              2                                   


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

Previous

Return to General