Patterns Game Strategies

Interactive on-site game threads go here

Re:

Postby m_b_metcalf » Sun Aug 20, 2017 3:29 pm

Pat wrote:can update 5.8
from game 289

It's not in my records yet: the game's still open.

[Edit] Now done.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby enxio27 » Tue Nov 07, 2017 7:53 pm

<moved>
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby m_b_metcalf » Mon Nov 20, 2017 4:33 pm

enxio27 wrote:::: comment :::
m_b_metcalf wrote:Well, one tried and tested method is, as champagne has already mentioned somewhere, is vicinity searching.

I've seen that mentioned, but I don't understand what it means (that terminology thing again) or how to do a vicinity search.

Well, basically, you take a promising existing puzzle, called the seed, and vary the value(s) of n of its clues (where n is typically 1 to 5), and check whether the result is valid and interesting. When you add filters, for instance to ensure that ED has some minimum value (for instance, not a single), it does become more complicated.

HTH

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby enxio27 » Mon Nov 20, 2017 5:55 pm

m_b_metcalf wrote:Well, basically, you take a promising existing puzzle, called the seed, and vary the value(s) of n of its clues (where n is typically 1 to 5), and check whether the result is valid and interesting. When you add filters, for instance to ensure that ED has some minimum value (for instance, not a single), it does become more complicated.

Can gsf sudoku do this (with the correct parameters)? If not, is there another freely available tool to do it?
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby m_b_metcalf » Mon Nov 20, 2017 5:58 pm

enxio27 wrote:
m_b_metcalf wrote:Well, basically, you take a promising existing puzzle, called the seed, and vary the value(s) of n of its clues (where n is typically 1 to 5), and check whether the result is valid and interesting. When you add filters, for instance to ensure that ED has some minimum value (for instance, not a single), it does become more complicated.

Can gsf sudoku do this (with the correct parameters)? If not, is there another freely available tool to do it?

Sorry, I've no idea. Apart from SE, I've written every line of code I use myself.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby champagne » Mon Nov 20, 2017 6:12 pm

enxio27 wrote:Can gsf sudoku do this (with the correct parameters)? If not, is there another freely available tool to do it?


I don't know about gsf's programs but ...

If you want to play actively in the game and to find your own strategy, I have no problem to share all my execs (windows) and command lines.
Having all the exec keeps many things open

Just to be clear, compared to Mike and Patrice, I am missing all tools collecting data on the web. On my side, this is purely a manual follow up
champagne
2017 Supporter
 
Posts: 6359
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby m_b_metcalf » Mon Nov 20, 2017 8:31 pm

For the sake of completeness, there is a further type of vicinity search, namely a stochastic 'walk' through puzzle space. Choose, say, two values to alter simultaneously. If the result fulfils the criteria you're using, change a further two, and so on. You need to check, of course, that you don't get back to where you started and loop forever.

regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby enxio27 » Wed Nov 22, 2017 3:22 am

champagne wrote:If you want to play actively in the game and to find your own strategy, I have no problem to share all my execs (windows) and command lines.
Having all the exec keeps many things open

Just to be clear, compared to Mike and Patrice, I am missing all tools collecting data on the web. On my side, this is purely a manual follow up

That would be much appreciated! I've been trying to create a file of (what I think are) vicinity puzzles using Excel, but it's extremely clumsy at best.
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby enxio27 » Wed Nov 22, 2017 3:50 am

On another note: When SE is evaluating a file of puzzles, does it stop/hang when it encounters an invalid puzzle?
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby m_b_metcalf » Wed Nov 22, 2017 5:19 am

enxio27 wrote:On another note: When SE is evaluating a file of puzzles, does it stop/hang when it encounters an invalid puzzle?

Yes, it can take a long time to evaluate a puzzle with multiple solutions. Something to be avoided.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby enxio27 » Wed Nov 22, 2017 9:42 pm

m_b_metcalf wrote:
enxio27 wrote:On another note: When SE is evaluating a file of puzzles, does it stop/hang when it encounters an invalid puzzle?

Yes, it can take a long time to evaluate a puzzle with multiple solutions. Something to be avoided.

After evaluating the file of puzzles with Sudocue, I discovered that only three were valid puzzles. I clearly need a better method of generating vicinty puzzles.
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby champagne » Wed Nov 22, 2017 10:12 pm

enxio27 wrote:
champagne wrote:If you want to play actively in the game and to find your own strategy, I have no problem to share all my execs (windows) and command lines.
Having all the exec keeps many things open

That would be much appreciated! I've been trying to create a file of (what I think are) vicinity puzzles using Excel, but it's extremely clumsy at best.


I have doubts that excel could generate millions of puzzles per hour. A 24/25 clues pattern can produce hundred millions of puzzles. If you really want to learn more about the potential of a pattern, either you use other tools (C++ in my case) to test in programs your ideas or you run existing programs and explore different ways to select new sudokus. Sharing my set of programs remains open, a pm or a mail could be a good start.
champagne
2017 Supporter
 
Posts: 6359
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby enxio27 » Thu Nov 23, 2017 3:36 am

champagne wrote:I have doubts that excel could generate millions of puzzles per hour.

My thought was to generate the initial batch (really lots of small batches) using gsf's sudoku, then use something else to do the vicinity search (unless there's a way to get gsf sudoku to do that).

I really don't understand was is meant by -2/+2, etc. in this context. That is probably hampering me, as well.

Sharing my set of programs remains open, a pm or a mail could be a good start.

I appreciate your help. I'll send you a PM, but it may be late this weekend. My family is here for American Thanksgiving (tomorrow), and I am "chief cook and bottle washer".
User avatar
enxio27
 
Posts: 447
Joined: 13 November 2007

Re: Patterns Game Strategies

Postby champagne » Thu Nov 23, 2017 7:21 am

enxio27 wrote:I really don't understand was is meant by -2/+2, etc. in this context. That is probably hampering me, as well.


I'll answer separatly to the pm.

The concept of vicinity means that changing small things has a good chance to give a new solution, often with some unchanged properties.

Small changes can be
a)switching digits (change the digit in "n" cells)
b)switching cells (replace "n" cells by other cells )
c)adding cells or suppressing cells, but then, to have a valid and minimal solution, a) must be done in the same time
d) a mix of these


the -2/+2 notation can be used in a) or b) to express the depth of the search. In the pattern game,the pattern being locked, it is always a) .

with p clues
-1/+1 you have to consider p possibilities to replace the digit by 1to 8 possible digits for the cell
-2/+2 you have to consider{ p+(p-1)/2} possibilities to replace the digit by 1to 8 possible digits for 2 cells

and the number of iterations grows very fast. -3/+3 is still possible for a batch of reasonable size, more than 3 must be done on very small batches but for a single puzzle, a depth of 6 can be tried (maximum IMO).

Each possibility must be tested for validity and minimality (required in the pattern game). At the end, if p the clues number is >=23, a -3+3 pass can generate hundreds valid sudoku per entry.

As the game start with a seed, The vicinity can start around the seed or one can create other seeds by any way (minimal or not, valid or not, the seed is not part of the game, but a valid seed will have a better yield)

Doing so, thousands of puzzles have to be studied with a lot of redundancy, so side tools have to clear redundancy. (usually morphing puzzles to canonical, then putting them in a data base used as filter, with a potential of millions of ED puzzles)
champagne
2017 Supporter
 
Posts: 6359
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby m_b_metcalf » Thu Nov 23, 2017 9:10 am

champagne wrote:c)adding cells or suppressing cells, but then, to have a valid and minimal solution, a) must be done in the same time
[snip]
As the game starts with a seed, the vicinity can start around the seed or one can create other seeds by any way (minimal or not, valid or not, the seed is not part of the game, but a valid seed will have a better yield)

One such way requires c):
    For a new pattern, P, one can compare it with all previously played patterns. For each such pattern, say Q, P will have i clues that Q doesn't have and Q will have j clues that P doesn't have.

    Find that Q for which i + j is a minimum.

    For some or all of the submissions played in the game of pattern Q,
      solve the puzzle

      delete from the puzzle the j clues not in P

      add to the puzzle, from its solution grid, those i additional clues required to form P
    The result, typically with multiple solutions, can now be used as a seed in the new game of P, usually to provide a new set of seeds.

In game 295, i was 0 and j was 1.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9058
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to Interactive games