The New Sudoku Players' Forum

[JPF]

I checked this pattern by filtering through "40 maximal invalid patterns" list and through fully symmetrical invalid patterns. I didn't find an invalid pattern which is superset of this pattern. So, this pattern may be valid.

I have to say that I don't understand the reasoning. Anyway, the best way to prove that a pattern is valid is to show a corresponding puzzle.

JPF

[JPF]

I'm 99.99% sure that they are maximal invalid ("magic") patterns.

I confirm the easiest part of Blue's assertion: If the patterns B1,B3,S1,S2,S3 are invalid, they are maximal invalid.

JPF

[Serg]

Hi, JPF!

I checked this pattern by filtering through "40 maximal invalid patterns" list and through fully symmetrical invalid patterns. I didn't find an invalid pattern which is superset of this pattern. So, this pattern may be valid.

I have to say that I don't understand the reasoning. Anyway, the best way to prove that a pattern is valid is to show a corresponding puzzle.

I just wanted to say that the status of "I-pattern" is unknown (valid/invalid).

I confirm the easiest part of Blue's assertion: If the patterns B1,B3,S1,S2,S3 are invalid, they are maximal invalid.

Do you have proper examples of the valid puzzles?

Serg

[Serg]

Hi, blue!
Congratulations with new findings! At the moment I cannot confirm all published patterns are invalid. I am thinking about possible confirmation...
Do you have full list of maximal invalid patterns for "5 free boxes" case (B3, B1, S2) and "6 free boxes" case (S1, S3)?

Serg

[JPF]

Do you have proper examples of the valid puzzles?

You could have trusted me I was just confirming Blue's assertion...

However, just to please you and as an example, here are the possible extensions of S1+{c}

Code: Select all

+---+---+---+   +---+---+---+   +---+---+---+
|1..|...|.23|   |...|1..|.23|   |...|...|123|
|...|...|.45|   |...|...|.45|   |...|...|.45|
|...|...|.67|   |...|...|.61|   |...|...|.67|
+---+---+---+   +---+---+---+   +---+---+---+
|...|...|632|   |...|...|274|   |...|...|258|
|867|932|514|   |514|827|396|   |253|418|796|
|253|146|798|   |327|964|158|   |678|925|431|
+---+---+---+   +---+---+---+   +---+---+---+
|...|265|489|   |...|489|612|   |...|531|679|
|492|718|356|   |482|671|539|   |765|289|314|
|586|394|271|   |961|253|487|   |391|764|582|
+---+---+---+   +---+---+---+   +---+---+---+
      
+---+---+---+   +---+---+---+   +---+---+---+
|...|...|.12|   |...|...|.12|   |...|...|.12|
|...|...|.34|   |...|...|.34|   |...|...|.34|
|...|...|.56|   |...|...|.56|   |...|...|.56|
+---+---+---+   +---+---+---+   +---+---+---+
|6..|...|578|   |...|7..|681|   |...|...|527|
|451|387|629|   |876|915|243|   |372|815|469|
|987|526|143|   |314|826|579|   |495|762|183|
+---+---+---+   +---+---+---+   +---+---+---+
|...|873|261|   |...|569|327|   |7..|458|391|
|318|265|497|   |625|173|498|   |539|271|648|
|726|914|385|   |793|248|165|   |148|936|275|
+---+---+---+   +---+---+---+   +---+---+---+


To Blue:

I'm 99.99% sure...

What are the missing 0.01%?

JPF

[blue]

Do you have full list of maximal invalid patterns for "5 free boxes" case (B3, B1, S2) and "6 free boxes" case (S1, S3)?

For the "5 free boxes" (4 boxes filled) case ... possibly, but I don't have all of them in one place.
This weekend, I'll look at some old projects, etc., to see what I can put together.

To Blue:

I'm 99.99% sure...

What are the missing 0.01%?

For these 5 patterns, it's mainly the outside possiblity that after hours of my "patterns game" code running on them, some puzzle exists, but was never found.

For patterns in general, there's a possibility of a bugs in the code that "proves" that they really don't have puzzles.
For me, each pattern requires specially tailored code, and alot of it is "copy/paste/edit" code, and sometimes I make mistakes.
There's also a possiblity of logical errors in implemeting the big picture, for a given pattern. Some details below.

If you want to try your hand at writing "proving" code for some patterns ...
First, sorry if I'm about to tell you things you already know ...

The main plan of attack ... if you want things to complete in a reasonable time ... is to

1. Produce every ED way of filling the empty cells of the pattern, that as a puzzle, is a puzzle with at least one solution.
2. For each of those, take one of its solutions, and clear out the empty cells in the pattern, and check whether the result is a puzzle with multiple solutions.
   If it is that, then the "(ED) fill" for the empty cells of the pattern, contains an unavoidable set ... which is what we hope.

If every ED fill (that has an extension to a complete grid), contains an unavoidable set, then the pattern has no valid (single solution) puzzles.
If, in step (2) above, the (2nd) puzzle has a single solution ... then that puzzle is a counterexample to the proposition that the pattern has no valid puzzles.

On the "ED" fills bit: working in the other direction ... suppose the pattern had a valid puzzle, with a unique solution. Then starting with that (hypothetical) (puzzle,solution) pair, you could transform it in ways that preserve the "empty cells" shape, and bring what's in the solution grid in those cells, to a canonical form of your choosing. What's in those cells, in the end, would be one of the "ED fills" (for the empty cells), that would come under consideration in step 1.
This is detail that I don't want to go into, but if you actually had a (puzzle,solution) pair, and did what was outlined here, and took the "canonical empty cells fill" into step 2 ... you would definitly get a "counterexample puzzle", but it likely wouldn't match "puzzle" part of the transformed (puzzle, solution) pair that you started with.

Step 2 above, is basic and too simple to screw up.
Step 1 is where problems can arise.

Usually producing *every* fill for the empty cells, checking whether (as puzzles)they have one or more solutions, and taking the results (as they come) into step 2 ... produces way too many puzzles, given "reasonable" as a time constraint.
You can save time, by only producing puzzles that would be "minlex" with respect to relabelling (only) transformations, but you can still get a lot of puzzles that way.
You could do that, though, and pass the results to a standard "pseudo-puzzle" canonicalizer, check the canonical form against a list that you acculate, and only handle the cases that aren't already in the list.
Issues with that: 1) "pseudo-puzzle" canonicalizing can sometimes take as long as solving and 2) the accumulating list, might not fit in memory.
Ways around that: 1) build up ED fills "in stages", 2) produce ED fill lists for different parts of the empty cells pattern, and piece them together to make complete fills, 3) some combination.

For the "build in stages" bit: for an example, using one of the shapes above, you might start by producing all of the ED fills for the band 1 part of the shape, and then extend those to fills for the full shape. That would be a place where the kind of "logical error" that I mentioned, could creep in. A "canonicalizer" for the band 1 part, would usually look at the possibility of swapping stacks (boxes in this case) 1 & 2. But, the part of the pattern in bands 2&3 under box 1, doesn't match what's under box 2, and you couldn't make it match, by say swapping bands 2&3 and permuting rows in the bands. That's a problem. There are two options, it seems: 1) use a canonicalizer with the stacks 1&2 swap disabled, or 2) use a standard canonicalizer, and for each ED result, try the bands 2&3 fill using the original ED band 1 fill, and same fill with boxes 1&2 swapped.

For the separate ED lists for different parts of the pattern bit: It's tricky, and highly prone to logical errors. It's probably only a last resort when the "memory issue" comes into play. You can use overlapping "parts" (e.g. overlapping in a full box), or isolated parts where cells in one part, see cells in another. It generally means that you forgoe the idea that you will test only an ED list of complete fills, and settle for knowing that for each truly ED fill, at least once, you'll test some version of it.

I'm cutting this short, because it can get really deep, and it isn't easy to explain (I'm finding out).
"Should you choose to accept this mission" ... think carefully and good luck.

Cheers.

[Serg]

Hi!

It can be transformed to subset of "S1" in this family of patterns:

Code: Select all

          B3                          B1                          S2

. . . | . . . | . x x       . . . | . . . | . x x       . . . | . . . | . x x
. . . | . . . | . x x       . . . | . . . | . x x       . . . | . . . | . x x
. . . | . . . | . x x       . . . | . . . | . x x       . . . | . . . | . x x
------+-------+------       ------+-------+------       ------+-------+------
. . . | . . . | x x x       . . . | x x x | x x x       . . . | x x x | x x x
. . . | x x x | x x x       . . . | x x x | x x x       . . . | x x x | x x x
x x x | x x x | x x x       x x x | . . . | x x x       x x x | x x x | x x x
------+-------+------       ------+-------+------       ------+-------+------
x x x | x x x | x x x       x x x | x x x | x x x       x x x | . . . | x x x
x x x | x x x | x x x       x x x | x x x | x x x       x x x | x x x | x x x
x x x | x x x | x x x       x x x | x x x | x x x       x x x | x x x | x x x


          S1                          S3

. . . | . . . | . x x       . . . | . . . | . x x
. . . | . . . | . x x       . . . | . . . | . x x
. . . | . . . | . x x       . . . | . . . | . x x
------+-------+------       ------+-------+------
. . . | . . . | x x x       . . . | x x x | x x x
x x x | x x x | x x x       x x x | . . . | x x x
x x x | x x x | x x x       x x x | x x x | x x x
------+-------+------       ------+-------+------
. . . | x x x | x x x       . . . | x x x | x x x
x x x | x x x | x x x       x x x | x x x | x x x
x x x | x x x | x x x       x x x | x x x | x x x

I'm 99.99% sure that they are maximal invalid ("magic") patterns.
They haven't been confirmed (by Serg), though.

I've done exhaustive search for S1 and S3 patterns (more precisely saying, for the family of patterns, having all boxes, except for B5, exactly as S1/S3 patterns and B5 box being free (this box may have any box pattern)). I can confirm that patterns S1 and S3 are invalid. Moreover, there are no other invalid patterns of this family, having B5 box configuration not being subset of B5 box in S1 or in S3 patterns.

Serg

[Serg]

Hi!
I've done exhaustive search for B1 and B3 patterns (more precisely saying, for the family of patterns, having all boxes, except for B5, exactly as B1/B3 patterns and B5 box being free). I can confirm that patterns B1 and B3 are invalid. Moreover, there are no other invalid patterns of this family, having B5 box configuration not being subset of B5 box in B1 or in B3 patterns.

Serg

[Serg]

Hi!
I've done exhaustive search for S2 pattern (more precisely saying, for the family of patterns, having all boxes, except for B8, exactly as S2 pattern has and B8 box being free). I can confirm that pattern S2 is invalid. Moreover, there are no other invalid patterns of this family, having B8 box configuration not being subset of B8 box in S2 pattern.

Serg

[JPF]

Blue,

thanks for this comprehensive description of your approach in researching the validity of patterns.
I have developed another approach myself, based on ideas developed in problem-solving from the "Patterns Game." I have encountered many of the difficulties mentioned in your text, such as speed of canonicalization, huge sorting, etc., and have developed solutions that are worth what they are worth.
The major disadvantage of my method is that it is not strictly exhaustive.
However, up to now, I have not found any patterns for which my conclusion (valid or invalid) has been proven incorrect.
The general idea is to determine an estimate of the distribution of the number of solutions that puzzles with the given pattern have. From this, the final goal is to find out the minimum value of this distribution. If the minimum value is 1, the pattern is valid, otherwise it is invalid.
The estimation is done recurrently.
It is worth noting that the convergence of the process towards the real distribution is more or less rapid, depending on the pattern in question.

JPF

[dobrichev]

offtopic: Show

jelly beans cause acne

[JPF]

deleted

[coloin]

Thanks for those explanations .....

I may or may not have found a puzzle with this pattern.
So consequently it may be a good test of your methods therefore

Code: Select all

+---+---+---+
|...|...|...|
|123|456|..8|
|5..|..7|.4.|
+---+---+---+
|7..|..3|...|
|8..|..1|..2|
|9..|..4|...|
+---+---+---+
|315|692|...|
|...|...|...|
|...|...|.5.|
+---+---+---+ 8670 sols


[JPF]

valid pattern!

Code: Select all

+---+---+---+
|...|...|...|
|123|456|..7|
|8..|..9|.1.|
+---+---+---+
|9..|..1|...|
|7..|..5|..2|
|3..|..8|...|
+---+---+---+
|459|287|...|
|...|...|...|
|...|...|.8.|
+---+---+---+   1 sol.


Unfortunately, 'my method' is unable to tell whether you have found a puzzle with this pattern or not

JPF

[coloin]

Unfortunately, 'my method' is unable to tell whether you have found a puzzle with this pattern or not JPF

Well done ...
Yes that is the same puzzle which I found ... which makes it more likely that it is the only puzzle with this pattern !