Patterns Game Strategies

Interactive on-site game threads go here

Re: Patterns Game Strategies

Postby coloin » Fri Mar 23, 2012 12:21 am

If it is any help i found 33 ED puzzles with this pattern

Code: Select all
+---+---+---+
|8..|...|7..|
|.1.|..3|.4.|
|..6|...|..5|
+---+---+---+
|...|..1|.2.|
|...|.4.|...|
|.6.|7.5|...|
+---+---+---+
|5..|...|..8|
|.2.|6..|.1.|
|..7|...|5..|
+---+---+---+   


It was rather easier to generate the 2452 [edit - Now 2457] ED puzzles with the extra clue
[edit - Generated by up to [-5+5] but possibly there are a few more]

Code: Select all
+---+---+---+
|3..|...|1..|
|.5.|..8|.7.|
|..4|...|..6|
+---+---+---+
|...|1.2|.8.|
|...|.3.|...|
|.9.|4.5|...|
+---+---+---+
|1..|...|..4|
|.7.|5..|.9.|
|..3|...|6..|
+---+---+---+   


This could well be the same pattern that m_b_metcalf submitted as the next pattern.

C
Last edited by coloin on Mon Apr 02, 2012 11:52 pm, edited 2 times in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Patterns Game Strategies

Postby m_b_metcalf » Fri Mar 23, 2012 2:43 am

coloin wrote:This could well be the same pattern that m_b_metcalf submitted as the next pattern.


But, in fact, it isn't.

Regards,

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

Re: Patterns Game Strategies

Postby dobrichev » Fri Mar 23, 2012 1:09 pm

eleven wrote:
ronk wrote:One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me.


...I noticed, that i got less puzzles to check, when - while filling in digits - i sorted out sub-puzzles, for which there is a mapping (according to the automorphisms of the complete pattern) to a puzzle with smaller minlex form...


ronk wrote:The only thing I'm convinced of is that starting with a sub-pattern of a puzzle's pattern, generating all appropriate non-isomorphic sub-puzzles for that sub-pattern, expanding the generation by upsizing through larger sub-patterns and finally to the original pattern, should produce all non-isomorphic puzzles with that pattern, including the original puzzle (or morphs thereof). [edit: AFAIK, even this has yet to be proven.]


Which transformations are safe to be applied to the intermediate sub-puzzles when targeting morphs eliminations?
There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.
I can't follow the whole experiment but it looks like the root of the evil could be in this detail.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Patterns Game Strategies

Postby Mauricio » Fri Mar 23, 2012 6:00 pm

dobrichev wrote:Which transformations are safe to be applied to the intermediate sub-puzzles when targeting morphs eliminations?
There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.
I can't follow the whole experiment but it looks like the root of the evil could be in this detail.

b) is the only sane choice, though I don't have the motivation to find and explain an example that shows that a) is wrong, but I am sure it is (I would consider a pattern where the cells fill box 1, r1c4 and r4c1 and the subpattern is box1).
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: Patterns Game Strategies

Postby ronk » Fri Mar 23, 2012 6:09 pm

Mauricio wrote:
dobrichev wrote:There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.
b) is the only sane choice ...

I don't think anyone has proposed that a) is the correct choice, at least not after having given the choice some thought.

coloin wrote:If it is any help i found 33 ED puzzles with this pattern
...
It was rather easier to generate the 2452 ED puzzles with the extra clue

Perhaps. Your results would help validate champagne's process if ...
  1. Your process is essentially different from his, and
  2. He obtains the same results.
[edit: add response to coloin]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby eleven » Fri Mar 23, 2012 9:29 pm

I am sorry, that i bothered others with my own confusion. The mistake i made was, that in the same process i calculated the minlex order to 2 different orders of cells, first to the order of the cells in the sub-pattern, then to the order of the cells in the complete pattern.
It is easy to avoid this problem, when you define an assignment order for all cells in forward and always minlex to this.
Then at any step (e.g. when the last of a group of symmetrical clues is added), you can look, if some morph of the sub-puzzle has a lower minlex-order (in the predefined order), and just eliminate it, if this is the case.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby eleven » Mon Mar 26, 2012 10:32 am

Yes, no, yes, no, yes, no, ...
I guess i changed my mind 10 times, how this question should be answered:

Is it possible to enumerate all non equivalent puzzles from a set of all non equivalent sub-puzzles ?

My answer now is no again.

My last thought had been, that if you canonicalize sub-puzzles and complete puzzles to the same order of cells, i.e. find the minimal minlex form for a predefined order (where all sub-puzzle cells come before the rest), then for each complete puzzle there is a morph, for which you can find a numbering of the sub-puzzle cells, which is minimal for the sub-puzzle (just minlex these cells first and then renumber the rest accordingly).
But this is not true, when sub-puzzle cells are in the same unit as complementary cells.

Example:
I defined the cell order as
32,40,48,50,2,6,74,78,18,26,54,62,14,34,46,66,10,16,64,70

For this order this 16-clue sub-puzzle has that minimal minlex form:
Code: Select all
..2...1.......2...4.......6.....1.3.....2.....2.3.4...7.......8...2.......3...5..
..2...1.......2...4.......6.....1.2.....2.....2.3.4...7.......8...1.......3...5..

But this puzzle
Code: Select all
..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..

has as minimal minlex of its sub-puzzle the first one. Its sub-puzzle never can be morphed/renumbered to a minimal one. So if you throw away this first sub-puzzle, you have no chance to find the complete puzzle or an equivalent by adding numbers to any non equivalent sub-puzzles.

Code: Select all
+-------+-------+-------+  +-------+-------+-------+     +-------+-------+-------+
| . . 5 | . . . | 6 . . |  | . . 2 | . . . | 1 . . |    | . . 2 | . . . | 1 . . |
| .17 . | . .13 | .18 . |  | . 1 . | . . 2 | . 4 . |    | . . . | . . 2 | . . . |
| 9 . . | . . . | . .10 |  | 4 . . | . . . | . . 6 |    | 4 . . | . . . | . . 6 |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
| . . . | . . 1 | .14 . |  | . . . | . . 1 | .*3 . |    | . . . | . . 1 | .*2 . |
| . . . | . 2 . | . . . |  | . . . | . 2 . | . . . |    | . . . | . 2 . | . . . |
| .16 . | 3 . 4 | . . . |  | . 2 . | 3 . 4 | . . . |    | . 2 . | 3 . 4 | . . . |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
|11 . . | . . . | . .12 |  | 7 . . | . . . | . . 8 |    | 7 . . | . . . | . . 8 |
| .19 . |15 . . | .20 . |  | . 4 . |*2 . . | . 1 . |    | . . . |*1 . . | . . . |
| . . 7 | . . . | 8 . . |  | . . 3 | . . . | 5 . . |    | . . 3 | . . . | 5 . . |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
     cell order           puzzle with min. sub-puzzle      normalized sub-puzzle
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby ronk » Mon Mar 26, 2012 2:37 pm

eleven wrote:Example:
I defined the cell order as
32,40,48,50,2,6,74,78,18,26,54,62,14,34,46,66,10,16,64,70

So you are using "defined-cell-order minimum lexical order" instead of "row minlex?" If you used row minlex, it would make it much easier for us to follow (and perhaps verify your result.)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby eleven » Mon Mar 26, 2012 5:30 pm

ronk wrote:So you are using "defined-cell-order minimum lexical order" instead of "row minlex?" If you used row minlex, it would make it much easier for us to follow (and perhaps verify your result.)

With row minlex you have 2 different ways of minlexing the sub-puzzle and the complete puzzle. This makes things much more complicated.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby Mauricio » Mon Mar 26, 2012 6:54 pm

What am I misunderstanding?
Code: Select all
. . 2|. . .|1 . .
. 3 .|. . 2|. 4 .
4 . .|. . .|. . 6
-----+-----+-----
. . .|. . 1|. 2 .
. . .|. 2 .|. . .
. 2 .|3 . 4|. . .
-----+-----+-----
7 . .|. . .|. . 8
. 4 .|1 . .|. 3 .
. . 3|. . .|5 . .

has minimal minlex with the predefined order than the puzzle posted.
eleven wrote:But this puzzle
Code: Select all
..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..

Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: Patterns Game Strategies

Postby eleven » Mon Mar 26, 2012 7:38 pm

Now i don't understand.
As i see it this puzzle would be found from the non equivalent sub-puzzle "normalized sub-puzzle" (by adding digits to the other cells), different to the "But this" puzzle.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby ronk » Tue Mar 27, 2012 11:01 am

eleven wrote:But this puzzle
Code: Select all
..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..
has as minimal minlex of its sub-puzzle the first one.

This "puzzle" has multiple solutions. Was that your intent or did something go astray?

eleven wrote:For this order this 16-clue sub-puzzle has that minimal minlex form:
Code: Select all
..2...1.......2...4.......6.....1.3.....2.....2.3.4...7.......8...2.......3...5..
..2...1.......2...4.......6.....1.2.....2.....2.3.4...7.......8...1.......3...5..

So these two sub-minimals are equivalent. Conjectures: Therefore, evaluating all possible combinations of clues for the same additional cells, r28c28 in this instance, should produce the same canonicalized results. Moreover, this would be independent of the chosen canonicalization method.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby ronk » Tue Mar 27, 2012 7:27 pm

I verified champagne's exhaustive finding of 112 puzzles for the pattern of game 0169 with more conventional techniques, i.e., without using his reductions based on symmetry. More precisely, I checked that my 112 puzzles were equivalent to those dobrichev listed here, and assumed that champagne's list of 112 is also equivalent.

My process applied this command to the following template ...

gsfsudoku -gtm.0 -e"uniq(%#mc)" g0169partial.pattern | sed -e"s/ #.*//" > g0169partial.dat

Code: Select all
 .     .   1      | .   .   .   | 2       .   .     
 .     .   .      | .   .   X   | .       .   .     
 23    .   .      | .   .   .   | .       .   134   
------------------+-------------+--------------------
 .     .   .      | .   .   .   | .       X   .     
 .     .   .      | .   .   .   | .       .   .     
 .     X   .      | .   .   X   | .       .   .     
------------------+-------------+--------------------
 12345 .   .      | .   .   .   | .       .   123456
 .     .   .      | X   .   .   | .       .   .     
 .     .   234567 | .   .   .   | 1345678 .   .     

The cells were chosen such that the g0169partial.pattern had the same four automoprhisms as the full pattern.

A home brew program then relabeled clues in order 1,2,3 ... 9 in row order starting at r1c1. It also placed 'X's at the locations still requiring clues, i.e. r28c28, r4c6, r5c5, and r6c4. Explicitly, the command ...

myProgram g0169partial.dat > g0169full.pattern

... produced a file of 782919 templates, the first and last being ...

Code: Select all
..1...2...x...1.x.2.......1.....x.1.....x.....1.x.2...1.......2.x.1...x...2...1..
..1...2...x...1.x.2.......1.....x.2.....x.....1.x.2...1.......2.x.1...x...2...1..
..1...2...x...1.x.2.......1.....x.2.....x.....1.x.2...1.......2.x.2...x...2...1..
...
...
..1...2...x...3.x.4.......5.....x.6.....x.....3.x.7...8.......7.x.6...x...9...6..
..1...2...x...3.x.4.......5.....x.3.....x.....3.x.6...7.......6.x.8...x...9...8..
..1...2...x...3.x.4.......5.....x.3.....x.....3.x.6...7.......6.x.3...x...8...9..

Lastly, the command ...

gsfsudoku -gt -e"valid&&uniq(%#.c)" g0169full.pattern | tee g0169.dat

... produced said 112 puzzles. All are minimal and at least one can be solved with singles only. In actuality, the last step was assigned to six hyper-threads. Despite this, the entire process still took 8 days.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Patterns Game Strategies

Postby eleven » Tue Mar 27, 2012 9:49 pm

Congrats on that, Ron,
since i changed my mind now for the 11th time (there was a flaw, indeed there is a minimal minlex of the 20 clue with a minimal minlex sub-pattern), no objections are left to champagne's or your result. :oops:

The only doubt i still have is that it could be faster to calculate all 21's (with the help of 2 more symmetries).
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Patterns Game Strategies

Postby champagne » Sun Apr 01, 2012 5:21 pm

I don't know so far what to do of it, but, compared to games with (slightly) smaller number of clues, I generated a relatively low number of puzzles with the pattern of the game 170

9 millions compared to several tens millions for recent patterns.

Have we passed the peak number or is it something linked to that pattern ???

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

PreviousNext

Return to Interactive games