Fully symmetrical invalid patterns

Everything about Sudoku that doesn't fit in one of the other sections

Fully symmetrical invalid patterns

Postby Serg » Wed Feb 15, 2017 10:54 am

Hi, people!
This is result of my exhaustive search: published below fully symmetrical patterns have no valid puzzles.
Code: Select all
        F1                    F2                    F3                    F4                    F5

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 . . .

F1 pattern was published in 2010 at setbb.com site. I am not sure that I was the first publisher of this pattern, but I haven't seen independent confirmation of this result. The rest patterns are new. They have recently been discovered. It would be nice to see independent confirmation of these results.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby dobrichev » Wed Feb 15, 2017 6:20 pm

Inspired by this post by JPF I just discovered another fully symmetrical pattern having no valid puzzles

Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Fully symmetrical invalid patterns

Postby Serg » Wed Feb 15, 2017 7:31 pm

Hi, Mladen!
dobrichev wrote:... I just discovered another fully symmetrical pattern having no valid puzzles

Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

You are joking, as usual. Your example is useless, but my 5 patterns can be used for filtering out invalid patterns (mainly - fully symmetrical). All published above patterns are very likely symmetrically maximal. I.e. if one adds some clues to such pattern, provided that resulting pattern will still be fully symmetrical, the pattern will become valid. I think it's no sense to spend time now for checking their maximality.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby Leren » Wed Feb 15, 2017 8:06 pm

I also noticed the "reductio ad absurdum" humor inherent in the blank starting position.

I'm no expert on these things but I understand that you have to have at least 17 clues and 8 different digits in the clues for a valid puzzle to be possible.

If this point is not made, then it seems to me that you could produce lots of other symmetrical patterns with no valid puzzles possible.

If the point is made, then you can drop the blank starting position.

Leren
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: Fully symmetrical invalid patterns

Postby dobrichev » Wed Feb 15, 2017 8:53 pm

Hi Serg,

Congratulations for these nice patterns.

They are large enough not to suffer from low number of clues.

My own project on generation of all possible puzzles within a given pattern was stuck on the automated identification of the symmetries and later reduction of the search space on the base of the symmetries found.
In order to verify your results I should hardcode (and verify) the specifics for each of the patterns symmetries. You know, it is a lot of work, and is sensitive to human errors.

What is the order of magnitude of the computation time you spent for the exhaustive search?

One day, when The Ultimate Theory Of Unavoidable Sets And All Their Possible Generalizations is ready, such verifications would be measured in patterns per second.

One open issue related to your work is the canonicalization of these patterns, keeping the visual symmetries of course.
Not sure whether this has been discussed here, but some start points include moving the givens to center (or periphery, or both) as much as possible, then prefer these locations, then those ones, etc.

Good job, as always!

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Fully symmetrical invalid patterns

Postby Serg » Wed Feb 15, 2017 11:32 pm

Hi, Leren!
Leren wrote:...

I'm no expert on these things but I understand that you have to have at least 17 clues and 8 different digits in the clues for a valid puzzle to be possible.

If this point is not made, then it seems to me that you could produce lots of other symmetrical patterns with no valid puzzles possible.

If the point is made, then you can drop the blank starting position.

I consider all possible (preferably essentially different) puzzles having the set of clues exactly defined by given pattern. For example, F1 pattern "produces" 21-clue puzzles (containing digits in the cells marked by "x" and having free cells marked by "."). If all possible puzzles for given pattern are invalid, I call such pattern "invalid". If at least one puzzle is valid, I call the pattern "valid". Valid puzzles produced by pattern must not be minimal.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby Serg » Thu Feb 16, 2017 12:30 am

Hi, Mladen!
dobrichev wrote:Congratulations for these nice patterns.

Thank you!

dobrichev wrote:My own project on generation of all possible puzzles within a given pattern was stuck on the automated identification of the symmetries and later reduction of the search space on the base of the symmetries found.

Yes, accounting for automorphisms (to my mind) is very complicated task.
dobrichev wrote:In order to verify your results I should hardcode (and verify) the specifics for each of the patterns symmetries. You know, it is a lot of work, and is sensitive to human errors.

Sure. I hoped that someone (very likely - blue or Afmob) can quickly check my results by already existing software.
dobrichev wrote:What is the order of magnitude of the computation time you spent for the exhaustive search?

Timing varies in rather wide range. F2 pattern was searched through for 30 minutes, F3 pattern was searched through for 88 hours. Unfortunately I have no universal searching program and forced to adapt my code to given pattern. Sometimes code optimization requres longer time than code execution. So those timings are not optimized.
"Searching engine" is based on JCZSolver. It works well, thanks to its coauthors! Thanks to you, Mladen, for Gridchecker. It is absolutеly indispensable tool for debugging such programs and crosschecking results.
dobrichev wrote:One day, when The Ultimate Theory Of Unavoidable Sets And All Their Possible Generalizations is ready, such verifications would be measured in patterns per second.

Well, well, well ...
dobrichev wrote:One open issue related to your work is the canonicalization of these patterns, keeping the visual symmetries of course.
Not sure whether this has been discussed here, but some start points include moving the givens to center (or periphery, or both) as much as possible, then prefer these locations, then those ones, etc.

Yes, it is important question, and I chose my own metric to present fully symmetrical patterns. Below is cells ordering schema (15 cells have hexadecimal sequence numbers: 1,2,...,9,A,B,C,D,E,F).
Code: Select all
A B C 1 2 . . . .
. D E 3 4 . . . .
. . F 5 6 . . . .
. . . 7 8 . . . .
. . . . 9 . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Metric is 15-digit binary number (cell 1 is accounted as 2^14, cell F is accounted as 2^0 (1)). All isomorphic transformations preserving "full symmetry" are considered to maximize metric. (Frankly speaking, I chose the metric to get common view of Magic Pattern.)
So, all published above patterns were canonicalized according to this metric.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby blue » Thu Feb 16, 2017 2:01 am

Hi Serg,

Nice work again !

Serg wrote:I hoped that someone (very likely - blue or Afmob) can quickly check my results by already existing software.

I'm running some old and unsophisticated code to check that F2-F5 don't have puzzles -- no idea when they'll finish.
I did verify that they will be "symmetrically maximal", if they are truly "invalid".
Puzzles for extensions were found in the blink of an eye, but for the actual shapes, none were found after a few minutes each.

Best Regards,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Fully symmetrical invalid patterns

Postby Serg » Fri Feb 17, 2017 12:39 pm

Hi, blue!
blue wrote:Nice work again !

Thanks! But (I hope) it is just a little bit of more general result coming soon ...

I should explain my mistake concerning F1 pattern. I've just seen some (archived) posts of the thread "Search for maximal patterns containing both diagonals" at setbb.com forum (dated by 2010). It turns out, you was the first who performed exhaustive search for F1 pattern. Some time later I performed exhaustive search for "Man" pattern and publish result - "Man" pattern has no valid puzzles.
Code: Select all
  "Man" pattern

x . . . . . . . x
. x . . . . . x .
. . x . x . x . .
. . . x x x . . .
. . . x x x . . .
. . . x x x . . .
. . x . . . x . .
. x . . . . . x .
x . . . . . . . x

Because "Man" pattern contains F1 pattern as subset, my result was independent confirmation of your result, concerning F1 pattern. Thus there is independent confirmation that F1 pattern has no valid puzzles.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Sat Feb 18, 2017 7:00 pm

Nice results, Serg!

While I haven't worked on Sudokus for quite some time, I was eager to check your results with my old code. I can verify that F1 has no valid puzzles (took about 10 minutes on an I5 2400, one core). Sadly, after 11 hours I got no results for the other patterns (one for each core) so far. So I used another program to estimate the number of ED (essentially different) puzzles one has to check for each pattern and got the following results:

F1: 9.358e6 puzzles (actual number: 9,365,491)
F2: 6.825e9 puzzles
F3: 8.971e8 puzzles
F4: 2.940e8 puzzles
F5: 3.048e9 puzzles

I'm quite surprised that it only took you about half an hour to check all ED puzzles of F2. Did you find some further reductions in the number of ED puzzles?
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Fully symmetrical invalid patterns

Postby blue » Sat Feb 18, 2017 9:40 pm

Hi Afmob,

It's nice to see that you're still around !

For Serg,

My searches finally finished.
F2-F5 were all valid ("invalidity" verified, assuming no bugs in the code).
F3 took the longest ... ~48 hours, after restarting it with some special optimizations for the actual shape.
The other's took 16-18 hours each.

BTW: for F2-F5, I also found puzzles for all of the "single cell" extensions ... making them "truly maximal", in addition to being "symmetrically maximal".
Did you know already know that they'ld be "maximal" in the more general sense ?

Cheers,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re:

Postby Serg » Sat Feb 18, 2017 10:26 pm

Hi, Afmob!
Afmob wrote:...
I'm quite surprised that it only took you about half an hour to check all ED puzzles of F2. Did you find some further reductions in the number of ED puzzles?

Thank you for your confirmation of F1 pattern's invalidity!

Methods I used for patterns F2-F5 varies. All searches were performed on my notebook (single core was used) - HP Compaq 6710b (Intel Core 2 Duo CPU @ 2.4 GHz).

F2 pattern was searched through exactly by blue's method, described in details at setbb.com forum in 2010 (concerning exhaustive search through Fractal Pattern). Key points of this method (in my interpretation).

1. All possible completions (not puzzles) are checked - do they contain unhitted UA sets?

2. First B345 band and B258 stack are filled and checked for unhitted UA sets. If they have no unhitted UA sets, we fill 4 corner boxes (B1,B3,B7,B9). When all corner boxes are filled, we impose on them all possible clue pattern templates (81 templates). Those corner templates are produced from given pattern (F2 pattern) by all permutations of r1,r2,r3,r7,r8,r9 rows and c1,c2,c3,c7,c8,c9 columns.

3. JCZSolver is used in checking completions for unhitted UA sets i 2 steps. First, completion "converted" to puzzle by solving completion by solver, second - the puzzles was solved. If the puzzle has only 1 solution, completion doesn't contain unhitted UA sets.

It takes me 162 seconds to find all 18432 crossings (band+stack), containing B5 box (exactly the same as for Fractal Pattern) and having no unhitted UA sets. Checking those 18432 crossing with corner boxes takes 49 minutes (I was not accurate saying "30 minutes").

Unfortunately this method don't work for F3 pattern. It has too many crossing, containing B5 box and having no unhitted UA sets. So I was forced to change algorithm (it took me a month or more of hard work). The best result was achived when first all crossings w/o unhitted UA sets, containing B2 box (B123 band + B258 stack) were found, then the rest 4 boxes (B4,B6,B7,B9) were checked. Somehow It was faster to change clue pattern templates (81) for those boxes first, then to fill free cells to get completions, check them for unhitted UA sets, etc. Search was done in 88 hours.

Absolutely the same method was used in searching through F4 pattern. I have no time to rewrite isomorphisms checking procedure and comment out the code specific for F3 pattern. Nevertheless, search through F4 pattern was performed in 53 minutes! It was a pleasant surprise for me.

F5 pattern was processed in the same manner as F4 pattern (without rewriting isomorphisms checking procedure), but I was forced to change boxes processing order. First crossings, containing B1 box (B123 band + B147 stack), were processed, then the rest boxes. The search was done for 13 hours.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby Serg » Sun Feb 19, 2017 12:49 pm

Hi, blue!
blue wrote:My searches finally finished.
F2-F5 were all valid ("invalidity" verified, assuming no bugs in the code).
F3 took the longest ... ~48 hours, after restarting it with some special optimizations for the actual shape.
The other's took 16-18 hours each.

Thank you for verification of patterns invalidity! Fantastic! I am spending months to adapt my old code to new applications. But you are able to do it for days.

blue wrote:BTW: for F2-F5, I also found puzzles for all of the "single cell" extensions ... making them "truly maximal", in addition to being "symmetrically maximal".
Did you know already know that they'ld be "maximal" in the more general sense ?

No, I didn't exploring maximality of F2-F5 patterns (pattern F1 isn't maximal). I was planning to check their maximality at later stages (when I shall have the full list of fully symmetrically maximal patterns).
You result about "true" maximality of F2-F5 patterns is very important for me. Your (human) performance breaks my imagine. Good job!

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Sun Feb 19, 2017 1:44 pm

I can also verify that the other patterns have no valid puzzles. F3 took about 31 hours while F5 was the fastest with 18 hours. The estimates were quite accurate apart from F5 which required 4.457e9 ED puzzles to be checked. I probably could have saved some time on F5 if I would have filled the middle box first.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re:

Postby Serg » Sun Feb 19, 2017 2:41 pm

Hi, Afmob!
Afmob wrote:I can also verify that the other patterns have no valid puzzles. F3 took about 31 hours while F5 was the fastest with 18 hours. The estimates were quite accurate apart from F5 which required 4.457e9 ED puzzles to be checked. I probably could have saved some time on F5 if I would have filled the middle box first.

Thank you very much for your help! It is very important for me to be sure that my searching code works well in these cases, because published invalid patterns are just the starting part of my investigation. It is similarly important to see that performance of my searching code is acceptable (there is no any magic way to do such searches in minutes).

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Next

Return to General