Patterns Game Strategies

Interactive on-site game threads go here

Re: Adding one less clue

Postby eleven » Sun Mar 18, 2012 2:34 pm

ronk wrote:Question: All else being equal, is there any reason to expect the run time for exhaustive addition of J clues to N sub-puzzles with K clues to be siginificantly different than adding (J-1) clues to say 9*N sub-puzzles with K+1 clues?

If i understand the question right, i would say no.
Going up to K clues in my opinion essentially has the sense to avoid all equivalents from automorphisms. In my case (going top down) i needed all cells of the first 2 bands for that, but its possible to achieve that with less cells.

Another question is, how you do the {+J} then. As Mike pointed out, you always have to add only one digit (max +1) as a new one for the next cell. Also you can avoid some unnnecessary solver calls, if you remove puzzles with less than 8 digits.
Following this, my final count of solvings needed for an exhaustive search of this pattern was 101 bio. I did not count the ones for the 21 clue pattern.

But maybe i have to give the order of assigning digits another thought. At the end the number of puzzles you have to check should always be the same, shouldn't it ?
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby champagne » Sun Mar 18, 2012 2:41 pm

eleven wrote:
champagne wrote:
eleven wrote:[Added:] (But this way you would not find 20 clues, where a=b)


I agree that adding a clue we loose a=b and we have some in the output.

So, the right process would be to solve the extended pattern plus the specific case a=b in the 20 clues pattern.

Sorry, but this was nonsense. Of course also for each 20 clue with a=b there is a number for Y, which gives a valid 21.


nonsense is like virus, it has a huge capacity for reproduction :D

to come back to the 21 clues test, I expect from the preliminary test a generation speed ratio 1 to 3 compared to the 20 clues.

This is for sure due to the additional symmetry.

In general, to answer to ronk, nothing good should come when we increase the number of clues in that area.

I have to restart the test because I am still generating with the requirement of a minimal puzzle and I did not check that the program is working properly without that option

the 21 clues pattern does not seem very productive either

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby ronk » Sun Mar 18, 2012 3:08 pm

champagne wrote:I have to restart the test because I am still generating with the requirement of a minimal puzzle and I did not check that the program is working properly without that option

So for the game 0169 pattern, there might be more than 112 puzzles when including non-minimals, if any. I don't see why that warrants a retest.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby eleven » Sun Mar 18, 2012 3:24 pm

Maybe the "miracle", that you have to test less puzzles for the 21 than for the 20, just comes from the fact, that there are more "valid" puzzles (where no given contradicts to another in a unit) with 7 digits only for the 20's than for the 21's.
Did you throw away the 7 digits puzzles, or tried to solve them, champagne ?
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby champagne » Sun Mar 18, 2012 3:45 pm

ronk wrote:
champagne wrote:I have to restart the test because I am still generating with the requirement of a minimal puzzle and I did not check that the program is working properly without that option

So for the game 0169 pattern, there might be more than 112 puzzles when including non-minimals, if any. I don't see why that warrants a retest.


I meantime checked the situation.

My concern was for the test on 21 clues. In fact, the program ,as it is, does not check for minimality in that specific case.
I had just launched one batch to see in the 21 clues pattern after the game 170 has been delayed. Restarting that batch would not have been a problem.

But this means also that all puzzles generated with 20 clues were minimal.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby champagne » Sun Mar 18, 2012 3:55 pm

eleven wrote:Maybe the "miracle", that you have to test less puzzles for the 21 than for the 20, just comes from the fact, that there are more "valid" puzzles (where no given contradicts to another in a unit) with 7 digits only for the 20's than for the 21's.
Did you throw away the 7 digits puzzles, or tried to solve them, champagne ?



I don't check so far the final number of digits used in the pattern.
Puzzles are rejected because they have more than one solution.

I am not sure that this would be a significant factor to reduce the run time but!!.

For me the main reasons for a quicker solution are the following.

As I mentioned earlier, it's a fact that the 21 pattern partial resolution with 13 clues assigned gives less seeds that the 20 pattern partial resolution with 12 clues assigned, the missing clue being the added one.

At that point, we have less seeds and more clues assigned in the 21 clues pattern.
We have the same 8 clues to assign in the last step.

The additional clue in the 21 pattern reduces the number of points to check. This is likely the main factor to explain the gap, but I would agree with you that if the ratio is confirmed, something else plays a role.

more puzzles with multiple solutions can be an explanation

champagne

EDIT

as gremlin let us sleep peacefully, I added the control of the number of clues in that specific process (not valid in +-n mode)
I started a second batch with the new code.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby coloin » Sun Mar 18, 2012 9:39 pm

Well ive looked at the 112 16-clue bases - and apologies for being off topic....
The eliminations arnt all SK loops you are right - but they are difficult to see how they are achieved.
A random 16 clue pattern has around 4000000 sol. perhaps

i looked at one
Code: Select all
..1...2...3...4.5.2.......1.....6.3.....1.....5.7.8...8.......9.7.3...4...2...1.. # 506004 sol.


Its hard to see where the eliminations come from
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 45679     4689      1         | 56789     356789    356789    | 2         6789      34        |
| 679       3         6789      | 12        12        4         | 6789      5         678       |
| 2         4689      456789    | 56789     356789    356789    | 34        6789      1         |
+-------------------------------+-------------------------------+-------------------------------+
| 14679     124689    46789     | 12456789  12456789  1256789   | 456789    3         245678    |
| 134679    124689    346789    | 12456789  123456789 12356789  | 456789    126789    245678    |
| 134679    5         346789    | 1246789   12346789  1236789   | 46789     126789    24678     |
+-------------------------------+-------------------------------+-------------------------------+
| 8         146       3456      | 124567    124567    12567     | 3567      267       9         |
| 1569      7         569       | 3         125689    125689    | 568       4         2568      |
| 34569     469       2         | 456789    456789    56789     | 1         678       35678     |
+-------------------------------+-------------------------------+-------------------------------+
actually more eliminations can be derived
+-------------------------------+-------------------------------+-------------------------------+
| 57        4689      1         | 56789     356789    356789    | 2         689       34        |
| 69        3         689       | 12        12        4         | 6789      5         678       |
| 2         4689      57        | 56789     356789    356789    | 34        689       1         |
+-------------------------------+-------------------------------+-------------------------------+
| 14679     1289      46789     | 12456789  12456789  1256789   | 456789    3         245678    |
| 134679    1289      346789    | 12456789  123456789 12356789  | 456789    1289      245678    |
| 134679    5         346789    | 1246789   12346789  1236789   | 46789     1289      24678     |
+-------------------------------+-------------------------------+-------------------------------+
| 8         16        34        | 124567    124567    12567     | 35        267       9         |
| 1569      7         569       | 3         1289      1289      | 68        4         268       |
| 34        69        2         | 456789    456789    56789     | 1         678       35        |
+-------------------------------+-------------------------------+-------------------------------+
the pairs in the corner boxes are difficult to explain
although a 6  @r8c6 gives  a no solution 

thus it has a low sol. count


The most common base of the 112 has the lowest sol. count - 23 of the puzzles had this 16-base
Code: Select all
..1...2...3...4.5.6.......7.....1.3.....2.....5.8.9...2.......6.4.5...8...7...1..  ED=9.1/9.1/3.4
..1...2...3...4.5.6.......7.......3...........5.......2.......6.4.5...8...7...1.. #  138846 sol.


This would have shown us the SK loop if we had looked harder at the time.
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 45        789       1         | 36789     356789    356789    | 2         469       3489      |
| 789       3         289       | 126789    126789    4         | 689       5         189       |
| 6         289       45        | 12389     123589    123589    | 3489      149       7         |
+-------------------------------+-------------------------------+-------------------------------+
| 14789     126789    24689     | 1246789   12456789  1256789   | 456789    3         124589    |
| 134789    126789    234689    | 12346789  123456789 12356789  | 456789    124679    124589    |
| 134789    5         234689    | 12346789  12346789  1236789   | 46789     124679    12489     |
+-------------------------------+-------------------------------+-------------------------------+
| 2         189       3589      | 134789    134789    13789     | 34579     479       6         |
| 139       4         369       | 5         123679    123679    | 379       8         239       |
| 3589      689       7         | 234689    234689    23689     | 1         249       23459     |
+-------------------------------+-------------------------------+-------------------------------+

but there "really" are more

+-------------------------------+-------------------------------+-------------------------------+
| 45        79        1         | 36789     356789    356789    | 2         469       38        |
| 789       3         289       |*1267*    *1267*     4         | 69        5         19        |
| 6         29        45        | 12389     123589    123589    | 38        149       7         |
+-------------------------------+-------------------------------+-------------------------------+
| 14789    *1267*     24689     | 1246789   12456789  1256789   | 456789    3         124589    |
| 134789   *1267*     234689    | 12346789  123456789 12356789  | 456789   *1267*     124589    |
| 134789    5         234689    | 12346789  12346789  1236789   | 46789    *1267*     12489     |
+-------------------------------+-------------------------------+-------------------------------+
| 2         189       35        | 134789    134789    13789     | 45        79        6         |
| 19        4         69        | 5        *1267*    *1267*     | 379       8         239       |
| 35        689       7         | 234689    234689    23689     | 1         29        45        |
+-------------------------------+-------------------------------+-------------------------------+


Thus this has an ultra low sol count.
Note the missing <9> pms in those *1267* - there is no 9 in the original 16 clue base.
Suppose it just cant go there - i,m sure someone can say why

C
Last edited by coloin on Sun Mar 18, 2012 10:34 pm, edited 2 times in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Patterns Game Strategies

Postby eleven » Sun Mar 18, 2012 10:24 pm

Obviously things are more complex than i thought.

One thing is, that what i described above is not sufficient to get non equivalent puzzles only.
Code: Select all
While these sub-Puzzles are non equivalent,
12.3.....3.....1....4......2..1..3......5..4......6..7...........................
12.3.....3.....1....4......2..1..5......6..4......7..8...........................
these are equivalent nevertheless.
12.3.....3.....1....4......2..1..3......5..4......6..7.1.8..2......4..6......7..5
12.3.....3.....1....4......2..1..5......6..4......7..8.1.2..3......4..7......8..6

The next thing is, that if i calculate the non-equivalents for the first 2 boxes with the 21 clue (like i did for the 20 clue), i get more (494508 vs 306283). At least one reason is, that the 21 introduces a 5th number from the beginning. So i get many new sub-puzzles with an addidional digit (which would be eqivalents without the new clue).
Example:
Code: Select all
13/20 clues:
12.3.....3..........4......4..1.........2.........3....4.2.........1.........5...
13/21 clues:
12.3.....34.........5......5..1.........2.........3....5.2.........1.........5...
12.3.....34.........5......5..1.........2.........3....5.2.........1.........6...

When i added the next digit then, the new symmetry only eliminated about 10% of the puzzles (293056 of 3461556).
I let them in to enumerate the puzzles in the same way as for the 20 clue. The result was 175 bio (minus about 10% ?) , which is much more than the 101 bio, i had for the 20 clue.

These numbers are not exact because of remaining equivalents and maybe bugs, but now i assume, that the 21 search would last longer.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby m_b_metcalf » Mon Mar 19, 2012 12:39 am

coloin wrote:For this particular pattern It might even be quicker to generate "all" the 21 clue puzzlles with 5 clues in box 5 [in an "X" pattern] -instead of 4 -


That is (a morph of) JPF's original pattern. At the time, the only ratings found were 7.1, 9.0, 9.8 and 10.7. I gave it a run through one of my existing programs, without any vicinity searches, and got this first off:
Code: Select all
..1...2...3...4.5.6.......7...8.2.3.....6.....5.9.7...7.......1.9.3...4...2...6..   ED=9.0/9.0/3.4   
..1...2...3...4.5.6.......7...6.1.3.....2.....8.7.5...2.......1.4.3...8...7...6..   ED=9.1/9.1/3.4   
..1...2...3...4.5.6.......7...7.1.8.....2.....5.9.3...2.......6.8.5...3...7...1..   ED=9.2/9.2/3.4   
..1...2...3...4.5.6.......7...8.7.3.....1.....5.6.9...7.......6.9.3...4...2...1..   ED=9.3/9.3/3.4   
..1...2...3...4.5.6.......7...5.8.4.....1.....9.2.7...7.......1.5.9...8...2...6..   ED=9.4/9.4/9.1   
..1...2...3...4.5.6.......7...8.7.9.....1.....4.5.3...7.......6.5.9...4...2...1..   ED=9.6/9.6/3.4   
..1...2...3...4.5.6.......7...1.8.4.....2.....9.7.3...2.......6.5.9...8...7...1..   ED=9.9/9.9/9.4   
..1...2...3...4.5.6.......7...5.2.3.....6.....8.9.1...7.......6.5.3...4...2...1..   ED=10.0/10.0/3.4
..1...2...3...4.5.6.......7...2.5.4.....7.....8.9.3...7.......6.4.8...9...2...1..   ED=10.4/10.4/10.4 Diamond
..1...2...3...4.5.6.......7...1.8.9.....7.....4.5.3...2.......6.8.9...3...7...1..   ED=10.5/10.5/10.4
..1...2...3...4.5.6.......7...3.2.4.....7.....8.9.5...2.......6.5.8...9...7...1..   ED=10.6/10.6/10.4
..1...2...3...4.5.6.......7...3.8.9.....2.....4.6.5...7.......6.8.9...3...2...1..   ED=10.7/10.7/10.4
..1...2...3...4.5.6.......7...8.1.3.....7.....4.9.5...2.......1.9.3...8...7...6..   ED=10.8/10.8/10.4
..1...2...3...4.5.6.......7...1.8.3.....6.....4.9.5...2.......1.8.3...9...7...6..   ED=11.0/11.0/10.4
..1...2...3...4.5.6.......7...3.7.8.....6.....4.9.5...2.......1.5.8...3...9...6..   ED=11.3/11.3/3.4

Regards,

Mike Metcalf
Last edited by m_b_metcalf on Mon Mar 19, 2012 12:52 am, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8361
Joined: 15 May 2006
Location: Berlin

Re: Patterns Game Strategies

Postby m_b_metcalf » Mon Mar 19, 2012 12:42 am

dobrichev wrote:Here are all 112 ordered by minlex

Many thanks. Among other things, this confirms that finding the low rating for the initial deal was a matter of chance.

Regards,

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

Re: Patterns Game Strategies

Postby champagne » Mon Mar 19, 2012 7:51 am

eleven wrote:Obviously things are more complex than i thought.


The next thing is, that if i calculate the non-equivalents for the first 2 boxes with the 21 clue (like i did for the 20 clue), i get more (494508 vs 306283).
At least one reason is, that the 21 introduces a 5th number from the beginning.
So i get many new sub-puzzles with an addidional digit (which would be eqivalents without the new clue).

When i added the next digit then, the new symmetry only eliminated about 10% of the puzzles (293056 of 3461556).
I let them in to enumerate the puzzles in the same way as for the 20 clue. The result was 175 bio (minus about 10% ?) , which is much more than the 101 bio, i had for the 20 clue.

These numbers are not exact because of remaining equivalents and maybe bugs, but now i assume, that the 21 search would last longer.



Hi eleven,

No surprise if I disagree with your post. Facts seem against your findings, so the question is why??

=========

First of all, back to the question does the 21 clues pattern contains the 20 clues puzzles.

The final answer is 'yes', but we can add that, as the puzzle has a unique solution, it generates only one puzzle in the 21 clues pattern.
What is not granted is that the canonical form in the 21 clues pattern will fit with the 20 clues pattern.

=========

Now back to the count.

Skipping from 20 clues to 21 clues, we add symmetries. this is a special situation and the count (and the process) has to try to take care of that.
The general strategy, to get the best of the symmetry is to generate first cells having all the symmetries.

Here we get all the symmetries using in a first step rows 1 3 7 9 (8 cells).
The next "good step", to compare both way is to work on box 5.


I first took all clues in that box and got the comparative result already shown:

57990 seeds in 20 clues mode
54339 seeds in 21 clues mode

At that point, 2 remarks.

We are nearly equal for the future (still 8 cells to generate), with a small advantage to the 21 clues pattern with one more assigned
At the end, the new symmetries overcompensated the extension to one more clue.


In fact, cell r5c5 does not contribute to the reduction, so in my final test, I started with 12 cells in 21 clues mode and 15446 seeds.

In the partial treatment you made, you did not at all had benefit of the main symmetry

=====================

the facts subject to a final check that the process is working properly

I prepared 5 batches extending the "pre generation" to 16 clues.
The compression ratio in the third step (filling boxes 1 3 7 9) has been 13%
Each batch contains in average a little more than 2 million puzzles.
5 digits are still unknown including the central digit in box 5.

I started one batch yesterday at noon. It should be covered at more than 2/3 in 24 hours (now quarter to nine)
I started a second batch 13 hours ago and it is covered at more than one third.

At the end, this seems roughly twice as fast as the 20 clues search.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby ronk » Mon Mar 19, 2012 11:34 am

champagne wrote:I prepared 5 batches extending the "pre generation" to 16 clues.
The compression ratio in the third step (filling boxes 1 3 7 9) has been 13%
Each batch contains in average a little more than 2 million puzzles.
5 digits are still unknown including the central digit in box 5.

Would it be possible for you to be more precise? For example, the following [ed: ...] would be unambiguous:

Code: Select all
..B...B...........B.......B...........................B.......B...........B...B.. # step 1, 8 clues in r1379
..A...A...........A.......A...B.B...............B.B...A.......A...........A...A.. # step 2, add 4 clues in b5
..A...A...B.....B.A.......A...A.A...............A.A...A.......A.B.....B...A...A.. # step 3, add 4 clues in b1379


At each step, apply permutations: 1) diagonal and 2) row{13}{79}column{13}{79} ...
... keeping only essentially-different sub-puzzles as inputs for the next step

[edit: per champagne, removed clue addition at r5c5 in step 3]
Last edited by ronk on Mon Mar 19, 2012 12:24 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby champagne » Mon Mar 19, 2012 12:04 pm

ronk wrote:
champagne wrote:I prepared 5 batches extending the "pre generation" to 16 clues.
The compression ratio in the third step (filling boxes 1 3 7 9) has been 13%
Each batch contains in average a little more than 2 million puzzles.
5 digits are still unknown including the central digit in box 5.

Would it be possible for you to be more precise? For example, the following (my guess of what you're doing) would be unambiguous:

Code: Select all
..B...B...........B.......B...........................B.......B...........B...B.. # step 1, 8 clues in r1379
..A...A...........A.......A...B.B...............B.B...A.......A...........A...A.. # step 2, add 4 clues in b5
..A...A...B.....B.A.......A...A.A.......B.......A.A...A.......A.B.....B...A...A.. # step 3, add 5 clues in b13579


At each step, apply permutations: 1) diagonal and 2) row{13}{79}column{13}{79} ...
... keeping only essentially-different sub-puzzles as inputs for the next step


nearly perfect except for r5c5.

Adding r5c5 in such a step does not help. It gives no morph.
So you increase the size of output files without any added value.

It's better to keep such clues for the final step.

Another possibility to check would have been to assign in step 3 the other four clues.
I would expect slightly worse results

Four steps is not a realistic approach, at least with my code.
With a code accepting to process part of the morphs, you could have more flexibility.


champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Patterns Game Strategies

Postby eleven » Tue Mar 20, 2012 4:30 pm

champagne wrote:Here we get all the symmetries using in a first step rows 1 3 7 9 (8 cells).
The next "good step", to compare both way is to work on box 5.


I first took all clues in that box and got the comparative result already shown:

57990 seeds in 20 clues mode
54339 seeds in 21 clues mode

I started a new try to get more serious counts, and i get completely different results.

What i did now is:
Fix the digits in the box 5 to 1-4 or 1-5 resp.
Assign all possible (all which are not "seeing" the same digit and are not higher than the current maximum +1) digits to the 8 cells in r1379.
Calculate the minlex order (in this 12/13 clue pattern).
Only take the sub-puzzle, if this order is smaller than the orders of the 3 (15) mappings according to the 2 (4) automorphisms of the original (20/21 clue) pattern.

This way i got 201635 sub-puzzles for the 20 clue (9530/<5% were equivalent) and 678319 for the 21 clue (73662/<11%).

Added: Ah, i guess i know whats wrong. I have to minlex the morphs too, of course. Will try that.

Added2: I really should not do such things along the way :(

The result now is "better", but still different from champagne's:
20 clue: 30245, 180920 equivalents
21 clue: 40827, 711154

Dont have time to evaluate, if its ok now.
Last edited by eleven on Tue Mar 20, 2012 5:40 pm, edited 1 time in total.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby champagne » Tue Mar 20, 2012 5:05 pm

eleven wrote:
I started a new try to get more serious counts, and i get completely different results.

What i did now is:
Fix the digits in the box 5 to 1-4 or 1-5 resp.
Assign all possible (all which are not "seeing" the same digit and are not higher than the current maximum +1) digits to the 8 cells in r1379.
Calculate the minlex order (in this 12/13 clue pattern).
Only take the sub-puzzle, if this order is smaller than the orders of the 3 (15) mappings according to the 2 (4) automorphisms of the original (20/21 clue) pattern.

This way i got 201635 sub-puzzles for the 20 clue (9530/<5% were equivalent) and 678319 for the 21 clue (73662/<11%).



Interesting

either there is a bug in my process
or in yours
may be in both.


As I wrote to ronk in another post, the central clues brings nothing else than volume.

But using a different path to reach 11 (20 mode) or 12 (21 mode) clues does not help to compare the results.

The 20 clues pattern is much in favour of a start with rows 1379.
If we both follow the same way, we can compare results after 8 clues assigned
(I posted the results after rows 1357 in both modes but in maxtext form).

champagne

PS gremlin being in crazy mode, I finally launched all the batches, but I could be slightly in trouble with puzzles starting by a single
So far I stay in the same line, something equivalent to about one day of the full power of my i7.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Interactive games