The New Sudoku Players' Forum

[champagne]

Basically, for the me, the game is an interesting way of keeping my hand in at active programming*. Thus, using software from any other source is quite pointless. I've even devised two new filters to keep my use of SE to just the rating of puzzles before submission, avoiding serate as much as possible. If we all use the same programs, the game reduces to determining who happens to be awake when it starts.

Mike Metcalf

* A happy outcome of this was the acceptance of one of my programs for consideration as part of a benchmark. It has passed the initial evaluation and tests and some $$$ have changed hands.

On my side, sudoku programming has been the way to keep my brain active.
I basically would share your views on the limited interest to just uses programs from others.

But it happens that gridchecker fits exactly with part of my needs in the search of hardest and is 2_3 times faster than my own code.

For me the pattern game has been a challenging platform to check the validity of my code. I am not very interested in the game itself, it's consuming to much time and resources.

And the symmetry constraint in the pattern game lead more more to patterns offering a limited interest for the search of highest ratings;

champagne

[eleven]

The game 157 is not yet closed, but on my side, I stopped any work on it 2 days ago.
...
count per ER

Code: Select all

346   10.3
1036   10.4
823   10.5
341   10.6
14   10.7
1   10.8

I have tried that too now with similar results. I only used skfr for rating and got after 2 days

Code: Select all

10.3 1508
10.4 1433
10.5  209
10.6   43

I then rated the 10.6 and "high" 10.5's with ER, which lead to the 10.8 and 21 10.7 (3 diamonds).
The main reason, that i found more puzzles, is probably, that i did not throw away single starters (more than half of my puzzles start with a single) - for the Patterns game it would be better not to do -n+n on them (only a few patterns will have a highest rating with single starters only).
On the other hand i seem to have missed dozens of lower rated diamonds.

My method is old and different to champagne's. I never did more than a -3+3, which leads to short cycles of 1-2 hours. Then with a fast filter i select a small part for rating/expanding (most time consuming part nevertheless). Those to expand (-3+3) are simply sorted after skfr and i take e.g. the top 500 for the next cycle.
I dont need a database for that, just collect the selected puzzles to avoid duplicate rating/expanding (34602 in this case), and those not yet expanded. The other files are overwritten in the next cycle (of course in the Pattern game you could use them for other ratings).
But i use (an adopted version of) the bb-solver and gsf's canonicalization. It would be strange for me to reinvent the wheel by writing this myself too.

In most cases the highest ratings will come very soon (within one day after having enough puzzles to keep it running), because it is very probable, that they are in the regions with most puzzles, where you will get after a few iterations.

btw the puzzle with highest sfkr i found, is not minimal:

Code: Select all

..1..2..3....9..8.4..3..6....35....8.5.....7.8....42....8..1..9.7..8....2..6..8.. skfr=10.7/10.7/3.4

This is another hint for me, that the hardest puzzles will have maximum 24 clues.

[m_b_metcalf]

The 10.8 that I found was obtained by a completely deterministic procedure. As I've mentioned previously, I have a large file of highly-biased solution grids that, depending on a given pattern, can quickly yield some useful puzzles. In this case, I got a 10.3/10.3/9.5 quite soon, and used it as a seed for {-n, +n} processing. This in turn yielded a 10.0 diamond and a 10.1/10.1/10.0 that were fed into another cycle, giving the 10.8.

It's rare that it's so useful, but on the previous game it came up with a gratifying number of diamonds. On most games it's fairly useless.

Regards,

Mike Metcalf

[champagne]

The main reason, that i found more puzzles, is probably, that i did not throw away single starters (more than half of my puzzles start with a single) - for the Patterns game it would be better not to do -n+n on them (only a few patterns will have a highest rating with single starters only).
On the other hand i seem to have missed dozens of lower rated diamonds.

My method is old and different to champagne's. I never did more than a -3+3, which leads to short cycles of 1-2 hours. Then with a fast filter i select a small part for rating/expanding (most time consuming part nevertheless). Those to expand (-3+3) are simply sorted after skfr and i take e.g. the top 500 for the next cycle.
I dont need a database for that, just collect the selected puzzles to avoid duplicate rating/expanding (34602 in this case), and those not yet expanded. The other files are overwritten in the next cycle (of course in the Pattern game you could use them for other ratings).
But i use (an adopted version of) the bb-solver and gsf's canonicalization. It would be strange for me to reinvent the wheel by writing this myself too.

Hi eleven


My process is much closer to your's than expressed here.

I more and more stick to +-3 vicinity expansion and I keep puzzles with singles as well.
Reversely, I likely keep to many puzzles for the next cycle.

In that game, I wanted also to test the process in the situation of a player so

. I looked at the start specifically for diamonds (-D option in skfr)
. And I kept all puzzles, so I needed a database filter.
but as you say, you have also to eliminate morphs.

Hi Mike,

congratulations first for that quick submission of what appeared to be the highest.

I have to confess that your "biased database" is not a clear concept to me

regards

champagne

[m_b_metcalf]

I have to confess that your "biased database" is not a clear concept to me

It's simply based on the notion, since shown to be not very fruitful, that a puzzle with symmetry of the values of the givens will have some interesting properties. The nicest sort of symmetry is shown in this puzzle:

Code: Select all

  . . . . . 1 . 2 3
 . . . . 2 . 4 5 6
 . . . 4 . . 7 1 .
 . . 5 . . 3 . . 4
 . 6 . . . . . 8 .
 7 . . 8 . . 5 . .  9 out 14 identical pairs [c(i,j) = c(10-i,10-j)]
 . 1 7 . . 6 . . .
 6 5 4 . 9 . . . .
 3 2 . 1 . . . . .  ED=9.1/9.0/7.3


where B3 is a reflection of B7. But these are hard to find. It's easier to find ones like this:

Code: Select all

 . . . . . 2 . 7 3
 . . . . 3 . 6 9 2
 . . . 9 . . 8 5 .
 . . 8 . . 6 . . 5
 . 9 . . . . . 1 .
 5 . . 4 . . 2 . .   14 complementary pairs, [c(i,j) + c(10-i,10-j) = 10]
 . 5 2 . . 1 . . .
 8 1 4 . 7 . . . .
 7 3 . 8 . . . . .  ED=9.0/9.0/8.4


and, to this end, it is possible to pre-compute a set of solution grids in which the cells fulfil the property that c(i,j) + c(10-i,10-j) = 10:

Code: Select all

  1  6  9  5  8  2  4  7  3
  4  8  5  1  3  7  6  9  2
  3  2  7  9  6  4  8  5  1
  2  4  8  7  1  6  9  3  5
  6  9  3  2  5  8  7  1  4
  5  7  1  4  9  3  2  6  8
  9  5  2  6  4  1  3  8  7
  8  1  4  3  7  9  5  2  6
  7  3  6  8  2  5  1  4  9

and to use those for matching against a template. This is what I have done, and I use these in a Patterns Game to see whether, for the given pattern, some golden nuggets might be hiding there.

Note that my interest in generating fixed patterns predates the Patterns Game, going back to Christmas 2006.

Hope that helps,

Mike Metcalf

[champagne]

and, to this end, it is possible to pre-compute a set of solution grids in which the cells fulfil the property that c(i,j) + c(10-i,10-j) = 10:
...
and to use those for matching against a template. This is what I have done, and I use these in a Patterns Game to see whether, for the given pattern, some golden nuggets might be hiding there.

Note that my interest in generating fixed patterns predates the Patterns Game, going back to Christmas 2006.

Hope that helps,

Mike Metcalf

thanks Mike,

I have a better idea of what you are doing.

On my side, I start from scratch, looking for "symmetry of given", but, as I already wrote, I don't cover all possibilities

champagne

PS:

As usual, finding first the highest has a part of chance, but clearly the overall process is improving.

I am sure eleven is right when he thinks that expanding high ED is better, but fresh seeds can come out of low ED high ER.
I am convinced that this pays 2 or 3 cycles later.

[champagne]

about game 160

one player consistently winning is basically a challenge for the rest of us to step up our game
I have 6 or so cpus at my disposal and can't keep up with recent high scorers
some of whom I'm guessing are working from a single pc
I am having some success with a search on one pc but it requires a good seed from entries already played
and I probably get some plays out of that due to possible self-trumps by the original entrant

It's true that champagne's new software has brought him an insuperable advantage,
but that was, and is, open for anyone to emulate.

First of all, we have seen several "high scorers" in recent times.
Most of them are much better organised than me to play. The game stays for me a live platform to test new processes.

Is there any "insuperable advantage" in my process.
Surely not. I described with enough details the way I played 157.

All programs used are public (skfr gridchecker and database) and I am prepared to give more details to anybody willing to know what I did.

Mike said clearly he wants to write its own code. I can understand that.

For specific reasons, I started reworking my own code, catching the best of mladen dobritchev's code included in skfr to improve the generation and keep the control on generation parameters.


I played game 160 using that new code (mode +- 1to3) that seems to go faster than gridchecker, but not that much.

It's too early to make it public, but I intend to do it as soon as possible.

I continued to use gridchecker powerful clearing of morphs after generation


So a new player can easily start from that base. That's the common way to make progress in the life.



My tool in the game 160 has been an i7 processor.


As I started late (I was sleeping at the start of the game), I used as first seed the submission number 10 from mike, a 7.1 diamond. (1.5 hour after departure)
BTW my second submission in N° 69


Looping on that seed and adding seeds from a "symmetry of given" generation I saw around mid day signs of saturation.
At 1pm, I considered my goal achieved and I posted (getting a penalty) the highest puzzle I found.

next 2 days, I nearly failed in looking for new seeds of value and other high ratings.

12 hours after departure I had in cache most of the final high ratings and of the diamonds

modulo the entry curve for new players

Surely a good point. Being attractive for new players is a must.

I suggested in the past to give a better incentive on the rarity bonus.

I feel limiting the database of plaid ratings to the last 20? 30? games and making it public would give more chance to newcomers to catch points.

Another measure I would consider would be to forbid successive diamonds from the same player (easy to control for gremlin and forcing players to open the game)

I would suppress the lightning mode, we already go (generally) to fast

And I would consider suppressing the symmetry constraint.

No idea on my side on the 2 bonuses but a risk factor in the game seems to me a good point. Up to now, I feel these bonuses had a good influence



Merrry Christmas to everybody



Champagne

[eleven]

::: comment :::

[ronk-moderator edit: This post and an unspecified number of the subsequent posts were transferred here from the Patterns Game thread. The topic is generally about performing an exhaustive search for puzzles with the pattern of game 0169.]

I made a test for a full scan of the puzzle.

I unhappily filtered puzzles starting with a single, but I did not find any new puzzle with ED 3.4

it's not 100% sure (I have other options in that search), but I bet Patrice has a data base containing all puzzles valid in that pattern (112 if I am right)

Which means that the vicinity process can catch in some conditions all puzzles.

With "full scan" you mean an exhaustive search ? I cant believe that you could be able to do that in 2 days for a 20 clue puzzle. This is a very wide space.
If you did not, i still seriously doubt, that you really found all puzzles in that pattern (you all seem to have a very similar method).

[champagne]

::: comment :::

::: comment :::

I made a test for a full scan of the puzzle.

I unhappily filtered puzzles starting with a single, but I did not find any new puzzle with ED 3.4

it's not 100% sure (I have other options in that search), but I bet Patrice has a data base containing all puzzles valid in that pattern (112 if I am right)

Which means that the vicinity process can catch in some conditions all puzzles.

With "full scan" you mean an exhaustive search ? I cant believe that you could be able to do that in 2 days for a 20 clue puzzle. This is a very wide space.
If you did not, i still seriously doubt, that you really found all puzzles in that pattern (you all seem to have a very similar method).

Well, I really tried to make an exhaustive search.

The process takes benefit of all the "morphing" possibilities offered by the pattern which means:

- using the minimum of digits at the start
- clearing all morphs coming form permutations authorised in the patterns.

The process is also progressive, giving the possibility to continue with parallel batches.

Last but not least, as I mentioned, I activated in that run the elimination of positions generating singles.

All this has to be checked, but the fact that I got all seen puzzles with ED 3.4 let me think that the process is working properly.

Using all the available power, I could activate more than 10 parallel batches in the last step.

champagne

[eleven]

::: comment :::

- clearing all morphs coming form permutations authorised in the patterns.

Does it mean, that you are working on normalized (canonicalized) patterns, when you are adding digits ? If so, how many of them did you encounter ? Do you have a count, how much 20 clue puzzles you have checked at the end ?

[ronk]

::: comment :::

The process takes benefit of all the "morphing" possibilities offered by the pattern which means:

- using the minimum of digits at the start
- clearing all morphs coming form permutations authorised in the patterns.

I interpret this to mean you ...
- assign outright as many givens as possible, and
- minimize the number of possible givens for some cells based on givens and range of possibilities elsewhere, and
- avoid the generation of automorphs by limiting the possible givens in a few key cells

Is this correct, or are you doing more than this to limit the number of generated puzzles?

[coloin]

::: comment :::
The possibility that an exaustive count has been done is interesting.

Wonder if this [multi-solution] pattern has similar puzzles

Code: Select all

1 . . . . . 8 . .
. 3 . . . 9 . 5 .
. . 8 . . . . . 2
. . . . . 3 . 4 .
. . . . 1 . . . .
. 8 . 9 . 5 . . .
7 . . . . . . . 6
. 9 . 8 . . . 3 .
. . 5 . . . 9 . .

- we probably would have been aware of SE>11 puzzles with the sk loop ...... ?

[dobrichev]

::: comment :::

With "full scan" you mean an exhaustive search ? I cant believe that you could be able to do that in 2 days for a 20 clue puzzle. This is a very wide space.
If you did not, i still seriously doubt, that you really found all puzzles in that pattern (you all seem to have a very similar method).

Right.
I ran exhaustive search for about one day and cancelled it prior to first puzzle found. For large patterns the first results usually come after minutes.
I ran searches fixing some of the clues. The least clues I fixed and waited for enumeration to finish was for these 8 clues

Code: Select all

..1...2...3...4.5.6.......7.....3.8.....2.....4.9.5...7.......6.5.8...9...2...1.. #11.8
..1...2...3...4.5.6.......7...........................7.......................... #fix 8 vary 12


The pass produced 452 puzzles, all morphs of the 112s.

[champagne]

waking up, I see many reactions to my post relating to an exhaustive search on the pattern.

I will during the day show in detail what I have done and give comments on why I have that process in my code.

This requires preparation, so I'll just raise a question

Is there already a specific thread on that topic?

If not, Isn't it time to open one and to move all these recent posts in it as a start?

champagne

[champagne]

When I started to make some coding for the pattern game, I worked on a scanning procedure.

As others, I noticed that some measures had to be taken to avoid redundancy in generation.

One measure I took at that time has been to work band per band and to make some cleaning at each step.

I knew that the process was loosing some possibilities, but I did not care, it was not possible anyway to cover the entire field.

That three steps process gave me the opportunity to search in specific areas of the field, choosing interim seeds for the next steps.

Efficiency of the vicinity search and improvements made in it pushed to focus on it. The scan became more or less obsolete.

Moreover, the existing code had some rigidity making it poorly efficient in other tasks I had in mind as

- Finding new seeds if necessary
- Filtering interim results generating low ED
- Extracting interim patterns having some potential as of statistical data on “hardest”




Re coding the generation in my new multi purpose program, I reintroduced a scanning potential with fresh (or stolen) ideas;

Instead or expanding the generation band per band, I introduced a guided progressive generation in a very simple way

I added in the command line a 81 bits field having
‘A’ for already assigned position
‘B’ for positions to assign in that step
Any digit for other positions of the pattern.


I also revised the way to reduce the redundancy through symmetry properties.
In the pattern game, symmetry is currently compulsory, so we always have some possibilities to reduce the search using symmetry

Here, I picked up some ideas in gridcheker’s process.

gridchecker has an option performing very well, that I use in my generation process

gridchecker --pattern --patcanon < inr5.txt > inr5canon.txt

That process take some raw generation on a specific pattern and give back a file cleaned from morphs in a mintext format within the pattern.

I knew from dobrichev that the process had a preliminary phase preparing the task.

I introduced in the process an option to have a “canonical pattern” output.

The process is the following:

a) at the start, using the command line, the program looks for all (valid) permutations of rows and columns leaving the pattern unchanged
This is usually between 1 (the original) and 2 to 8 morphing possibilities at the end;

b) For each puzzle generated, the program applies these morphs to find the (maxtext) canonical form;

At the end of each step,

- the twins found are eliminated
- a filtering process can be applied
- next step can be done on part of the file


There is nothing complex in that. Example done on the game 169 pattern will clarify if necessary

champagne