Patterns Game Strategies

Interactive on-site game threads go here

Postby Pat » Mon Mar 03, 2014 12:33 pm

ssxsssxs wrote:
The principal of "vicinity search" is reasonable. But I am confused on the level of operation.

Can you give me a specific command line sample? Like this in gsf's readme-document:

    sudoku -go... jpf-19.dat
but I don't know what is it in file "jpf-19.dat"
What is it's content?

in gsf's software,
-go{-3+3} would provide a "vicinity search" (remove 3 givens and add 3)

in the example,
the input-file probably contains puzzles with 19 cells given


but for the Patterns Game,
we probably need a "vicinity search" which preserves the given Layout,
something like combining gsf's options -gt and -go
(would be -gto{-3+3} but that's not available)
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Re: Patterns Game Strategies

Postby joel64 » Mon Mar 03, 2014 5:48 pm

ssxsssxs wrote:Why you search so fast? Is there any setting to make sudoku.exe searching faster?



In game 225, I had 17 diamond after 2 hours of treatment (the first after 10 mn) . the problem was: how to place them?

Which is my strategy?

1/ canonicalization by renumbering the clues by their order of occurence, left to right, top to bottom.


2/ systematic use of the canonical form during the search for puzzles starting from the first clues
What reduces considerably the puzzles by eliminating the clones as of the beginning
what enables me to work with a not very powerful computer
joel64
 
Posts: 2879
Joined: 07 December 2009
Location: France

Re: Patterns Game Strategies

Postby ssxsssxs » Sun Mar 09, 2014 2:13 am

gsf:
-gtp10000.100.60.30, What is the range of the place of the number 10000?
User avatar
ssxsssxs
 
Posts: 100
Joined: 22 January 2014

Re: Patterns Game Strategies

Postby ssxsssxs » Sun Apr 20, 2014 8:14 pm

recently, I wrote code by myself. it can do random searching and exhaustive searching. the exhaustive one can only search 9 clues in one day.
I want to turn to the +n/-n search. But I don't know what it is. And what does it mean "combinations of N clues" ?
User avatar
ssxsssxs
 
Posts: 100
Joined: 22 January 2014

Re: Patterns Game Strategies

Postby m_b_metcalf » Wed Apr 23, 2014 11:53 am

ssxsssxs wrote:recently, I wrote code by myself. it can do random searching and exhaustive searching. the exhaustive one can only search 9 clues in one day.
I want to turn to the +n/-n search. But I don't know what it is.

What you probably mean here is a vicinity search on a puzzle with a fixed pattern. Given such a puzzle, you can vary each given in turn to see whether a new, valid puzzle is obtained. You can then vary each compination of two givens in a similar way, and so on. Below is GouinJP's latest 'more' posting and all its depth 1 and 2 children.
The cells changed are shown by the code terminated by asterisks (before canonicalisation).

HTH

Mike
Hidden Text: Show
Code: Select all
000000001002003040050040600000002010004030005010700800003007006070300020900060400 ED=8.1/7.3/3.2
000000001002003040050040200000006010004030005010700800003007002070300060900020400     1   23********1
000000001001002030040030500000001060003020007060800400002008005080200010900050300     1   1932******2
000000001001002030040030500000001060003020007060800900002008005080200010700050300     2   1959******3
000000001001002030040030500000001060003020004050700800002007005070200010900050300     3   1962******4
000000001002003040050040600000002070004030005070100800003001006010900020900060400     4   1984******5
000000001002001030040030500000002060003070004060800100007008005080700020900050300     5   1926******6
000000001002003040050040600000002070004030005080900100003009006090300020700060400     6   1948******7
000000001002003040050040200000006070004030005070800900003008002080300060100020400     7   1923******8
000000001002003040050040600000002070006030005070800900003008006080300020100060400     8   1953******9
000000001002003040050040600000002070004030005070800900003001006080300020100060400     9   1976******10
000000001002003040050040600000007010004030005070200800003002006020300070900060400    10   2362******11
000000001002003040050040600000007010004030005010200800003002006020100070900060400    11   2384******12
000000001002003040050040600000007010004030005060800900003008006080300070200060400    12   2362******13
000000001002003040050040600000007010004030005010800900003001006080300070200060400    13   2376******14
000000001002001030040030500000002010003060007010700800006007005070600020900050300    14   2659******15
000000001002001030040030500000002010003060004010700800006007005080600020900050300    15   2682******16
000000001002003040050040600000002010004070003010800500007008006080700020900060400    16 P 2632******17
000000001002003040050040600000002010004070005010800900007008003080700020600030400    17   2637******18
000000001002003040050040300000002060004070005010600800007006003060700020900030400    18   2648******19
000000001002003040050040300000002010004060005010700800006007003070600090900030400    19 P 2688******20
000000001002003040050040300000002010004060005010700800006007009070600020300090400    20   2637******21
000000001002003040050040600000002010004070005010800900001008006080700020300060400    21   2673******22
000000001002003040050060700000002010006030005010400800003004007040300020900070100    22   2897******23
000000001002003040050060700000002010006030005010400800003004007040300020900070500    23   2897******24
000000001002003040050060700000002010006030005010400800003004007040300020900070400    24   2897******25
000000001002003040050060700000002010006030004010800900003008007080300020400070600    25 P 2859******26
000000001002003040050060700000002010006030005010800900001008007080300020400070600    26   2873******27
000000001002003040050060700000002010006030005010800900005008007080300020400070600    27 P 2873******28
000000001002003040050040600000002010004030007010800900003008005080300020600050400    28 P 3237******29
000000001002003040050040600000002010004030006010700500003007008070300020900080400    29   3237******30
000000001002003040050040600000002010006030007010800500003008006080300020900060400    30   3253******31
000000001002003040050040600000002010004030007070800500003008006080300020900060400    31 P 3262******32
000000001002003040050040600000002010004030007010800500003008009080300020900060400    32 P 3279******33
000000001002003040050040600000002010004030007010800500003008006080700020900060400    33   3284******34
000000001002003040050060700000002010007030005010800600003008007080300020900070400    34   3553******35
000000001002003040050060700000002010004030005010800600003005007080300020900070400    35 P 3576******36
000000001002003040050060700000002080004030005010800900003008007080300020600070400    36   3548******37
000000001002003040050060700000002010004030005010800900003008006080300020600070400    37   3579******38
000000001002003040050040200000002010004030006010600700003006008060300020900080400    38   3759******39
000000001002003040050040200000002010004030005060700800003007006070300020900060400    39   3762******40
000000001002003040050040300000002060004030005010600700003006008060300020900080400    40   3748******41
000000001002003040050040600000002010004030005010600700003008009060300020800090400    41 P 3776******42
000000001002003040050040600000002010007030005010800700003008009080300020600090400    42   3753******43
000000001002003040050040600000007010004030005010800900003001006080300020700060400    43   4676******44
000000001002003040050040600000007010004030005010800900003008006080700020700060400    44   4684******45
000000001002003040050040600000002070008030005010700800003007006070300020900060400    45   4853******46
000000001002003040050040600000002070004030005010700800003007006070300080900060400    46   4888******47
000000001002003040050040600000002070004030005010700800003007006070300020900010400    47   4895******48
000000001002003040050040600000002070004030005010500800003009006090300020700060400    48 P 4864******49
000000001002003040050040600000002070004030005010800900003008006080300010700060400    49 P 4888******50
000000001002003040050040600000002070004030005010800900003008006080300090700060400    50 P 4888******51
000000001002003040050040600000002010006030005010700800003007006080300020900060400    51   5382******52
000000001002003040050040600000002010006030005010700800003007006070500020900060400    52   5384******53
000000001002003040050040600000002010004070005010800900001008006080300020700060400    53   5573******54
000000001002003040050040600000002010004030002010700800003007006070100020900060400    54   5984******55
000000001002003040050040600000002010004030007010700800003007005070300020900060400    55   5979******56
000000001002003040050040600000002010004030007010700800003007006070100020900060400    56   5984******57
000000001002003040050040600000002010004030007010800900003009006080300020700060400    57 P 5976******58
000000001002003040050040600000002010004030005070800900003008006080300020900060400    58 P 6267******59
000000001002003040050040600000002010004030005070800900003005006080300020700060400    59 P 6276******60
000000001002003040050040600000002010004030005010700800003007006090300020800060400    61 P 6782******61
000000001002003040050040600000002010004030005010700800003007006040300020900060700    62   8297******62
000000001002003040050040600000002010004030005010700800003007006060900020900060400    63   8284******63
000000001002003040050040600000002010004030005010700800003007006080300020500060400    64 P 8291******64
000000001002003040050040600000002010004030005010700800003007006070100020100060400    66   8491******65
000000001002003040050040600000002010004030005010700800003007006070500020100060400    67   8491******66
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby ssxsssxs » Wed Apr 23, 2014 2:08 pm

m_b_metcalf wrote:What you probably mean here is a vicinity search on a puzzle with a fixed pattern. Given such a puzzle, you can vary each given in turn to see whether a new, valid puzzle is obtained. You can then vary each compination of two givens in a similar way, and so on. Below is GouinJP's latest 'more' posting and all its depth 1 and 2 children.
The cells changed are shown by the code terminated by asterisks (before canonicalisation).

HTH

Mike
Hidden Text: Show
Code: Select all
000000001002003040050040600000002010004030005010700800003007006070300020900060400 ED=8.1/7.3/3.2
000000001002003040050040200000006010004030005010700800003007002070300060900020400     1   23********1
000000001001002030040030500000001060003020007060800400002008005080200010900050300     1   1932******2
000000001001002030040030500000001060003020007060800900002008005080200010700050300     2   1959******3
000000001001002030040030500000001060003020004050700800002007005070200010900050300     3   1962******4
000000001002003040050040600000002070004030005070100800003001006010900020900060400     4   1984******5
000000001002001030040030500000002060003070004060800100007008005080700020900050300     5   1926******6
000000001002003040050040600000002070004030005080900100003009006090300020700060400     6   1948******7
000000001002003040050040200000006070004030005070800900003008002080300060100020400     7   1923******8
000000001002003040050040600000002070006030005070800900003008006080300020100060400     8   1953******9
000000001002003040050040600000002070004030005070800900003001006080300020100060400     9   1976******10
000000001002003040050040600000007010004030005070200800003002006020300070900060400    10   2362******11
000000001002003040050040600000007010004030005010200800003002006020100070900060400    11   2384******12
000000001002003040050040600000007010004030005060800900003008006080300070200060400    12   2362******13
000000001002003040050040600000007010004030005010800900003001006080300070200060400    13   2376******14
000000001002001030040030500000002010003060007010700800006007005070600020900050300    14   2659******15
000000001002001030040030500000002010003060004010700800006007005080600020900050300    15   2682******16
000000001002003040050040600000002010004070003010800500007008006080700020900060400    16 P 2632******17
000000001002003040050040600000002010004070005010800900007008003080700020600030400    17   2637******18
000000001002003040050040300000002060004070005010600800007006003060700020900030400    18   2648******19
000000001002003040050040300000002010004060005010700800006007003070600090900030400    19 P 2688******20
000000001002003040050040300000002010004060005010700800006007009070600020300090400    20   2637******21
000000001002003040050040600000002010004070005010800900001008006080700020300060400    21   2673******22
000000001002003040050060700000002010006030005010400800003004007040300020900070100    22   2897******23
000000001002003040050060700000002010006030005010400800003004007040300020900070500    23   2897******24
000000001002003040050060700000002010006030005010400800003004007040300020900070400    24   2897******25
000000001002003040050060700000002010006030004010800900003008007080300020400070600    25 P 2859******26
000000001002003040050060700000002010006030005010800900001008007080300020400070600    26   2873******27
000000001002003040050060700000002010006030005010800900005008007080300020400070600    27 P 2873******28
000000001002003040050040600000002010004030007010800900003008005080300020600050400    28 P 3237******29
000000001002003040050040600000002010004030006010700500003007008070300020900080400    29   3237******30
000000001002003040050040600000002010006030007010800500003008006080300020900060400    30   3253******31
000000001002003040050040600000002010004030007070800500003008006080300020900060400    31 P 3262******32
000000001002003040050040600000002010004030007010800500003008009080300020900060400    32 P 3279******33
000000001002003040050040600000002010004030007010800500003008006080700020900060400    33   3284******34
000000001002003040050060700000002010007030005010800600003008007080300020900070400    34   3553******35
000000001002003040050060700000002010004030005010800600003005007080300020900070400    35 P 3576******36
000000001002003040050060700000002080004030005010800900003008007080300020600070400    36   3548******37
000000001002003040050060700000002010004030005010800900003008006080300020600070400    37   3579******38
000000001002003040050040200000002010004030006010600700003006008060300020900080400    38   3759******39
000000001002003040050040200000002010004030005060700800003007006070300020900060400    39   3762******40
000000001002003040050040300000002060004030005010600700003006008060300020900080400    40   3748******41
000000001002003040050040600000002010004030005010600700003008009060300020800090400    41 P 3776******42
000000001002003040050040600000002010007030005010800700003008009080300020600090400    42   3753******43
000000001002003040050040600000007010004030005010800900003001006080300020700060400    43   4676******44
000000001002003040050040600000007010004030005010800900003008006080700020700060400    44   4684******45
000000001002003040050040600000002070008030005010700800003007006070300020900060400    45   4853******46
000000001002003040050040600000002070004030005010700800003007006070300080900060400    46   4888******47
000000001002003040050040600000002070004030005010700800003007006070300020900010400    47   4895******48
000000001002003040050040600000002070004030005010500800003009006090300020700060400    48 P 4864******49
000000001002003040050040600000002070004030005010800900003008006080300010700060400    49 P 4888******50
000000001002003040050040600000002070004030005010800900003008006080300090700060400    50 P 4888******51
000000001002003040050040600000002010006030005010700800003007006080300020900060400    51   5382******52
000000001002003040050040600000002010006030005010700800003007006070500020900060400    52   5384******53
000000001002003040050040600000002010004070005010800900001008006080300020700060400    53   5573******54
000000001002003040050040600000002010004030002010700800003007006070100020900060400    54   5984******55
000000001002003040050040600000002010004030007010700800003007005070300020900060400    55   5979******56
000000001002003040050040600000002010004030007010700800003007006070100020900060400    56   5984******57
000000001002003040050040600000002010004030007010800900003009006080300020700060400    57 P 5976******58
000000001002003040050040600000002010004030005070800900003008006080300020900060400    58 P 6267******59
000000001002003040050040600000002010004030005070800900003005006080300020700060400    59 P 6276******60
000000001002003040050040600000002010004030005010700800003007006090300020800060400    61 P 6782******61
000000001002003040050040600000002010004030005010700800003007006040300020900060700    62   8297******62
000000001002003040050040600000002010004030005010700800003007006060900020900060400    63   8284******63
000000001002003040050040600000002010004030005010700800003007006080300020500060400    64 P 8291******64
000000001002003040050040600000002010004030005010700800003007006070100020100060400    66   8491******65
000000001002003040050040600000002010004030005010700800003007006070500020100060400    67   8491******66



Thank you!
But I don't understand your code.
If I compare these two line:
000000001002003040050040600000002010004030005010700800003007006070300020900060400 ED=8.1/7.3/3.2
000000001002001030040030500000002060003070004060800100007008005080700020900050300 5 1926******6
The number in 19 is "1", and in 26 is "3". Then these two line, a "3" is change to "1", others "3" change to "7", and all

"4" to "3",but how to explain "5" to "4" and "7" to "8"?

If I compare these two line:
000000001002003040050040600000002070004030005070100800003001006010900020900060400 4 1984******5
000000001002001030040030500000002060003070004060800100007008005080700020900050300 5 1926******6
The number in 19 is "1", and in 26 is "3".there is a "3" to "1", other "3" to "7", how to explain "5" to "4", "6"to"5".

My question is what's the detail of vicinity search.
User avatar
ssxsssxs
 
Posts: 100
Joined: 22 January 2014

Postby Pat » Wed Apr 23, 2014 3:17 pm


    hard to compare lines in his report,
    because he posted canonical forms;
    you need to compare before canonicalization
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Postby Pat » Wed Apr 23, 2014 3:24 pm

ssxsssxs wrote:My question is what's the detail of vicinity search.

for the Patterns Game,
say the Layout has 24 cells given,
then 24x23 / 2x1 choices of 2 cells to mutate,
or 24x23x22 / 3x2x1 choices of 3 cells to mutate, ...
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Re:

Postby ssxsssxs » Wed Apr 23, 2014 3:47 pm

Pat wrote:for the Patterns Game,
say the Layout has 24 cells given,
then 24x23 / 2x1 choices of 2 cells to mutate,
or 24x23x22 / 3x2x1 choices of 3 cells to mutate, ...


what kind of mutate?
Change the number in it, from 1 to 9?
how to continue? Back to original grid and chose anoter two cells, or not back, just go on to chose anoter two?
User avatar
ssxsssxs
 
Posts: 100
Joined: 22 January 2014

Re: Patterns Game Strategies

Postby JasonLion » Wed Apr 23, 2014 6:24 pm

To say it a different way:

For every clue, you try replacing that clue with all other possible digits, checking each one to see if it is still valid puzzle. Then you try every pair of clues, replacing both of them with every possible pair of digits, then triples, and so on depending on how much time you have.

This process is often used recursively, i.e. having found a new puzzle that works try the entire process on the new puzzle.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Patterns Game Strategies

Postby ssxsssxs » Wed Apr 23, 2014 10:51 pm

JasonLion wrote:To say it a different way:

For every clue, you try replacing that clue with all other possible digits, checking each one to see if it is still valid puzzle. Then you try every pair of clues, replacing both of them with every possible pair of digits, then triples, and so on depending on how much time you have.

This process is often used recursively, i.e. having found a new puzzle that works try the entire process on the new puzzle.


If it is turn to clue A and clue B to change. (A, B)change to (1, 1), (1, 2), (1, 3),...,(1, 9), (2, 1),(2, 2),..., (9, 9)?
If I found a new valid puzzle, whether the rating of it is good, try the entire process on the new puzzle, or when the rating is good, it can be seen as a new one?
User avatar
ssxsssxs
 
Posts: 100
Joined: 22 January 2014

Re: Patterns Game Strategies

Postby JasonLion » Thu Apr 24, 2014 12:49 am

ssxsssxs wrote:If it is turn to clue A and clue B to change. (A, B)change to (1, 1), (1, 2), (1, 3),...,(1, 9), (2, 1),(2, 2),..., (9, 9)?

Yes. Of course there are various optimizations you can apply to speed that up, but logically you try everything.

ssxsssxs wrote:If I found a new valid puzzle, whether the rating of it is good, try the entire process on the new puzzle, or when the rating is good, it can be seen as a new one?

Yes, and no, sort of. There are many variations. Some people mechanically create every puzzle that meets one fairly broad set of criteria (for example fits the pattern), recusing as many generations on everything that is potentially usable as they have CPU time and then rank/rate/explore them all to find the most interesting ones. Others do a directed search where they try to find a sequences of puzzles where the match with what they really want/rating increases steadily over time. Others use genetic algorithms, running populations of puzzles through various "mutations" and keeping only the most fit. There are many ways to approach it.

One additional step I didn't mention is to canonicalize each puzzle that passes basic criteria so you can check for duplicates with the puzzles you have seen/thought about before. This isn't required, but it speeds things up so much that it is pretty much always worth the effort.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Postby Pat » Sun May 11, 2014 3:22 pm


    in game 229,
    random generation got me as high as
      9.5/9.3/2.6
    -- used it as seed for "vicinity search"
    (mutate any 1-5 of the given cells)
    and reached
      10.6/1.2/1.2
    impressive ?

    others reached higher ratings---
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Re:

Postby champagne » Sun May 11, 2014 3:46 pm

Pat wrote: in game 229, ....


I worked only one day on that game, but with nearly the full power of an i7.

I started as usual with the search of puzzles having a symmetry of given.
This is a very short step (some minutes to some tens of minutes) giving usually a good spread of puzzles, often some of them with "high / very high" ratings.

In that case, I got several puzzles passing ED 9.2, but I was still far from the expected ratings.

I continued as usual with seeds made of highest ratings plus diamonds or pearls.

During the vicinity generation, I use no filter at all and I "quick rate" all new puzzles with my program (which means, as wrote jasonlion that all puzzles are put in canonical form and compared to the database of already known puzzles, but using gridchecker, this is a very very fast step)

I never use the random generation. I have a process to generate seeds in various areas of the field, but in fact, usually I don't have to use it.
champagne
2017 Supporter
 
Posts: 5575
Joined: 02 August 2007
Location: France Brittany

Game 239 high ratings

Postby champagne » Sun Sep 14, 2014 5:34 pm

I open comments on that game here to stay aside the game.

I checked from my game data base 790 puzzles passing the cutoff for the data base of potential hardest.

750 are not in the data base.

More interesting, the highest rating found and several others rating >= SER 11 are new.

Several players have worked on that pattern, likely one of the hardest ever studied.

I can collect all puzzles from others players to see how is the final result (skfr ED >= 10.3 or EP>= 10.5 or ER>=10.8
(in SER mode ED>=10.5 or EP>= 10.7 or EP>= 11)
champagne
2017 Supporter
 
Posts: 5575
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Interactive games