The New Sudoku Players' Forum

[gsf]

one of the challenges of patterns game play is puzzle generation
most players keep generation strategies close to the chest
that's good for winning games, but not for learning

I'm ready to do some learning
so here are the two strategies I use
both implemeted in my solver 2008-08-11

the first strategy takes a valid patterns game entry seed-grid
and iteratively selects clues at random and sets them to
alternate candidate values according to the pencilmark grid

Code: Select all

sudoku -n256 -gtp10000.100.60.30 -e "minimal==1&&uniq()" seed-grid

-n256 limits the iterative process to 256 valid entries
(the -gtp... option is defined by the --man option to the solver)

there is a helper script that iterates over the current game entries
for most games after ~3 days this process stabilizes and produces few new entries

the second strategy, used in the past few games, starts with an ordered-grid
with the first 8 clues set to 1..8, left to right, top to bottom
the remaining clue values are iteratively set in minlex order, again using the
pencilmark grid to select candidate values

Code: Select all

sudoku -gtpe.8 -qFNB -e minimal==1 ordered-grid

the output of this process is filtered by

Code: Select all

sudoku -e '(%#Hq)==(%#Dq)'

before being passed to sudoku explainer for rating
this selects puzzles with the hardest rating (%#Hq) equal to the diamond rating (%#Dq)
(the rating in my solver is based on the constraint order, controlled by the -q option)

the second strategy has yet to complete for the recent patterns
but it does seem to generate more high ER puzzles than the first strategy

sudoku explainer is still the bottleneck, by a large margin, for both strategies

[JPF]

one of the challenges of patterns game play is puzzle generation
most players keep generation strategies close to the chest
that's good for winning games, but not for learning

OK, here are my invaluable secrets :

I do an exhaustive search on a seed-puzzle by muting n digits (n=1,2,3) and doing that again and again on the new non isomorphic puzzles generated.
I may also use, as seed puzzles, puzzles from other players…

I don't have any precise rules regarding the number of generated puzzles.
It's essentially linked to the pattern, how things are going on and so on.

I remove the puzzles with an ED=n/single/single, which is easy to do.
And then I sort the puzzles with my own rating program which is unfortunately not correctly correlated to SE-rating.

Most of the time is spent in rating with sudoku explainer…and in canonicalization with gsf's program.

JPF

[tarek]

most players keep generation strategies close to the chest
that's good for winning games, but not for learning

here are my invaluable secrets :

From my side, I think that a person who has won exactly "0" games should keep his secrets to himself

Just to let everybody know, I was the dealer in one Pattern Game ... I had generated 2M+ puzzles of that pattern (with no strategy) prior to the start of the game & still did not win it. This clearly says that a strategy is needed for winning.

tarek

[m_b_metcalf]

one of the challenges of patterns game play is puzzle generation
most players keep generation strategies close to the chest
that's good for winning games, but not for learning

OK, here are my invaluable secrets :

And my worthless ones.

I do an exhaustive search on a seed-puzzle by muting n digits (n=1,2,3) and doing that again and again on the new non isomorphic puzzles generated.
I may also use, as seed puzzles, puzzles from other players…

I do something similar, but only for n = 1 or 2, where n=2 has a much higher yield.

I also have a program that can generate minimal puzzles based on a pattern from scratch. This has a high yield on some patterns and an almost neglibible one on others. The output can be used either for a submission or as a seed, or both.

I don't have any precise rules regarding the number of generated puzzles.
It's essentially linked to the pattern, how things are going on and so on.

In my case I'm rather lazy and rarely pass more that a few thousand to SE in the course of a game. Maybe I'd fare better if I left my computer running overnight.

I remove the puzzles with an ED=n/single/single, which is easy to do.
And then I sort the puzzles with my own rating program which is unfortunately not correctly correlated to SE-rating.

I remove low EP and/or ED ratings very early on, in both programs. I lack a decent way of rating the rest, so I have a mixed bag above a threshold.

Most of the time is spent in rating with sudoku explainer…and in canonicalization with gsf's program.

My programs became significantly faster when I introduced unavoidable sets at every possible point. That means that SE is now the bottleneck. So as not to allow the perfect to become the enemy of the good, I do a primitive canonicalization by renumbering the clues by their order of occurence, left to right, top to bottom. Given that the puzzles all have the same pattern, this appears to be good enough. Apart from SE, I use only my own code and haven't yet tackled a full-blown canonicalization program.

As is clear to everyone, this allows me, in a typical game, to get off to a good start only to be crushed by an avalance of diamonds in the end-game. And I never manage to get the highest rating, so

Back to the drawing board.

Regards,

Mike Metcalf

P.S. I first became aware of Sudoku when I read an article by someone who claimed to have found a puzzle so difficult that his program had taken all night to solve it. I thought, it must be possible to do better than that.

[Kiwy]

As gsf post generation strategies, work fine. THANKS.

The first strategie, seed-grid file can more than one puzzle?
What is -gtp10000.100.60.30 10000 stand for?


under Windows XP, sudoku version:
sudoku (AT&T Research) 2009-03-06
try

Code: Select all

 sudoku  -g  -n3 

no response, but that command was work using old version.


KIWY

[gsf]

As gsf post generation strategies, work fine. THANKS.

The first strategie, seed-grid file can more than one puzzle?
What is -gtp10000.100.60.30 10000 stand for?

60%+/-30% of the clues from the template are selected at pseudo-random
then 10,000 times: clues are added at pseudo-random to fill the template

under Windows XP, sudoku version:
sudoku (AT&T Research) 2009-03-06
try

Code: Select all

 sudoku  -g  -n3 

no response, but that command was work using old version.

thanks, bug fixed in 2009-03-15 just posted

[Kiwy]

windows executable bug report

After Download, the sudoku.exe size is only 48K....

KIWY

[Pat]

84 K

version from 2005.Oct.14

[gsf]

windows executable bug report
After Download, the sudoku.exe size is only 48K....

thanks for spotting this
finally figured out how to build against msvcrt.dll but didn't follow through with it

the just-posted 2009-03-17 size is 399872 bytes
and the build process is set up to avoid the problem in the future

[ronk]

"cat | sed | sort | uniq | sort" of the results for the first 114 games yields these counts of accepted submissions. Only eleven players have reached double-digits.

Code: Select all

   3624 gsf
   2191 m_b_metcalf
   1909 JPF
    809 TTHsieh
    800 Mauricio
    655 champagne
    525 joel64
    313 tarek
    256 Pat
     51 coloin
     31 999_Springs
      9 ronk
      9 mario133
      5 Ruud
      5 Eioru
      4 wintder
      2 g.r.emlin
      1 pseudocoup
      1 draco
      1 claudiarabia

[champagne]

"cat | sed | sort | uniq | sort" of the results for the first 114 games yields these counts of accepted submissions. Only eleven players have reached double-digits.

I guess that the entry barrier is now so high that many potential new players just tried and gave up.

I am prepared to disclose how I am working to-day to promote new entries, but I must confess that I completely changed my strategy over the last games
where I participated.


That one [ronk-moderator edit: game 0115] is special again for me since I entered the game after 2 or 3 days.
As a matter of fact, i try in priority to work on high ratings. The middle field is closed.

However, i have several possible submissions in the lower part of the table although I have been trapped in a stupid error

champagne

[ronk]

I am prepared to disclose how I am working to-day to promote new entries, but I must confess that I completely changed my strategy over the last games
where I participated.

Since you're currently finding some high ERs, I definitely would like to hear whatever you're prepared to disclose.

However, i have several possible submissions in the lower part of the table although I have been trapped in a stupid error

Since one can't trump oneself, playing a pearl can prevent one from playing a diamond (for that same ER). Is there another "trap"?

[champagne]

However, i have several possible submissions in the lower part of the table although I have been trapped in a stupid error

Since one can't trump oneself, playing a pearl can prevent one from playing a diamond (for that same ER). Is there another "trap"?

This is the easiest part to answeer.
there are many traps in that game, most of them due to the stress coming in any game. You have to take care

to produce minimal puzzles,
to submit in the right form,
to take care of all previous submissions older than some seconds ...

Here, I just mixed ED 4.0 and ED 4.4. a kind of dislexy in a quick reading of data. Having seen a "false" new diamond, I submitted the puzzle.

I am prepared to disclose how I am working to-day to promote new entries, but I must confess that I completely changed my strategy over the last games
where I participated.

Since you're currently finding some high ERs, I definitely would like to hear whatever you're prepared to disclose.

This would require long developments, but let me open the door.

When I entered the game, I started generation scanning some specific areas of the solutions field.

It was not so bad, but looking at JPF's performances, I had the feeling that I was mssing something.

I then restarted from the past search for "hardest" puzzles.

Clearly, some players scanned specific patterns (Ocean for example), but most puzzles were found in a -n+n search (generally -2+2).
Coloin for example worked exclusively in that way.

I compared the 2 processes in general and found the "vicinity" search terribly efficient.
Applied to the pattern game it works very well in the way I am doing the search.

I am applying a -2+2 to -5+5 search with specific filters depending on what I am looking for.
I then split the puzzles generated using my solver.
I normally rate all "easy puzzles" (cheap rating).

For high rating, I select puzzles on unclear parameters depending on the "potential" of the pattern.
All filters are using the print size as main filter. It works pretty well.
Other parameters are the level of tagging and the run time.

Next cycle restart from puzzles having the most promising properties (usually the "hardest" of the previous cycle unless I am looking for a start on a pattern, a puzzle solved by singles only).


In game 115, as I started very late, I took as first seed the set of highest rating submitted by other players.

When the pattern has a high potential at generation time, I "prefilter" the generation using a kind of "inline ED selector".

Overall, the results over the last four games I could play has been pretty good.



champagne


EDIT: just to confirm if necessary efficiency of the process, I just got in cache a puzzle rated ED=10.5/10.5/8.8
but I have nothing better than the last from Joel with ED 10.0

[JPF]

Hi gsf,

Sometime ago, I suggested you to make a slight change in your serate program in order to grab the ED part of the rating (r=ER/EP/ED) without calculating ER and EP.
Any progress in this direction?
Thanks,

JPF

[gsf]

Hi gsf,

Sometime ago, I suggested you to make a slight change in your serate program in order to grab the ED part of the rating (r=ER/EP/ED) without calculating ER and EP.
Any progress in this direction?
Thanks,

JPF

yes, that was a good suggestion, and I put it in, can't remember how long its been there now ...
-d, --diamond Terminate rating if the puzzle is not a diamond.
-p, --pearl Terminate rating if the puzzle is not a pearl.
ER==20.0 for terminated ratings