The New Sudoku Players' Forum

by **Serg** » Sat Apr 02, 2011 12:10 pm

Hi, all!
There is well-known Fractal Pattern, having valid puzzles:

Code: Select all: +-----+-----+-----+ |x . 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 think the problem of finding all valid puzzles for this pattern is rather difficult. blue has done exhaustive search for this pattern (by specially written program) and published his results at "Search for maximal pattern, containing both diagonals" in May, 2010. Maybe he was the first who solved this problem. It turns out that this pattern has 7 non-isomorphic valid puzzles only. Here are all valid puzzles posted by blue.

Code: Select all: 120000000450000000009000000000063051000500700000082036000300900000026018000091047 120000000450000000009000000000010080000307201000502607000409806000020040000701502 120000000450000000009000000000302760000010002000406530000090006000804910000501340 120000000450000000009000000000302760000010002000406530000090006000801940000504310 120000000450000000009000000000302560000010002000406730000090006000804910000501340 120000000450000000009000000000302560000010002000406730000090006000801940000504310 120000000450000000009000000000086031000500700000023056000300900000062018000091047

This is the case when random search (generation) doesn't work properly because valid puzzles are very rare (according to my estimates this pattern has about 650 billions non-isomorphic puzzles (valid and not valid)).

blue was so kind to publish algorithm he used for exhaustive search (see cited above thread at setbb.com/sudoku forum). I implemented blue's algorithm and cross-checked results. I've found the same 7 valid puzzles. Here they are in canonicalized form (by gsf's "sudoku" tool, command line: "sudoku -f%#mc my_puzzles.txt >my_puzzles_canon.txt").

Code: Select all: ........1......23.......45...1..2...23.46....57.83......6..4...32.68....81.59.... ........1......23.......45...1..2...23.46....57.83......6..4...32.68....81.95.... ........1......23.......45...1..2...23.46....75.83......6..4...18.59....32.68.... ........1......23.......45...1..2...23.46....75.83......6..4...18.95....32.68.... ........1......23.......45...1..6...23.47....68.39......7..4...15.98....39.75.... ........1......23.......45...1..6...23.47....68.93......7..4...19.58....35.79.... ........1......23.......45...2..4...14.26....56.37......5..8...83.92....92.64....

This is the first puzzle in the list presented in more readable form:

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

So, it took me about 3 months to code program and cross-checked results. Pure CPU time of program running - about 5 hours. The first goal of my posting is to confirm blue's results. But I have the second goal of my posting too. Maybe someone can observe some rules of the puzzles forming. Why are there namely 7 valid puzzles? It is very wondering.

Serg

by **Serg** » Sun Apr 03, 2011 8:22 am

Addendum.
These are all Fractal Pattern's valid puzzles in readable form.

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

Serg

by **dobrichev** » Sun Apr 03, 2011 10:52 am

Hi,

This approach has something in common to my attempts to exploit band completions.

Enumerating 5-clue band completions we found there are 3483430 possibilities covering all 416 bands (the total of 54+5 column in the referenced post).
Exploiting the Fractal Pattern's property that the middle band crosses middle stack with exactly 5 clues located entirely in the crossing box 5, we can enumerate the possible bands that could be completed with these 5 clues. In other words we can filter the 3483430, removing all completions that have clues in more than one band, different than 2+2+1 column and row distribution, and finally the same min-lex pattern.
After filtering, 1265 valid band completions remain. Below is the distribution by band.

Hidden Text: Show

Next task is to cross the bands having valid completions. For simplicity, like blue, I am placing the original box5 at box1.
Stacks are formed by bands after
a) transpose and move to leftmost (convert band to stack), 1 alternative
b) permute boxes, moving each box to the top (3 alternatives, composition of boxes 4,7 doesn't matter)
c) permute rows in box1 (6 alternatives)
d) permute three columns (6 alternatives)
with total 3*6*6=108 stack permutations.

The loops are:

Code: Select all: for each band having valid 5-clue completion { for each stack having valid 5-clue completion and index >= band { for each of three band box permutation { if there is no any valid band completion with clues in box1 for this permutation skip this permutation for each 108 stack permutations { relabel stack matching the values in the crossing box1 form a subgrid with boxes 1,2,3,4,7 fixed (band, current band permutation, stack, current stack permutation) solve the subgrid up to first solution (all subgrids passed this test) for each permuted band completion having clues in box1 and (completion index >= band completion for stack==band) { form a puzzle with band clues in box1 and subgrid's solution in boxes 5,6,8,9 check whether the puzzle has any solution (else there is uncovered UA located entirely in boxes 1,2,3,4,7) for each permuted stack completion where all 5 clues match the permuted band clues { process all completions of the subgrid with boxes 1,2,3,4,7 fixed } } } } } }

I stopped at "process grid" = count grid. 27276660 candidate grids are found in this way for about 4 minutes.
Later each grid should be checked for valid puzzles with the rest of the givens in the Fractal Pattern (original boxes 1,3,7,9 mapped to boxes 5,6,8,9), along with their valid non-isomorphic permutations.

There are possible bugs in my code and my head. I am far not sure the results are correct, but the approach should be right in general.

Cheers,
MD

by **Serg** » Tue Apr 05, 2011 11:29 am

Hi, dobrichev!
I should know much more details of your method to answer something definite about it. Both methods look like rather similar.

Serg

by **dobrichev** » Tue Apr 05, 2011 5:29 pm

Hi,

I modified a more general code for generating puzzles by crossing bands.
The idea is to start from "valid band completions". A valid band completion is a subgrid with givens located in one band and known band completion (one of 416 bands). It is not necessary completion to be minimal (i.e. it can contain redundant givens), but the completion guarantees that all unavoidable sets located entirely within the band are covered.
Extending to 9x9 grid, we can compose it band by band.
In order to narrow the search space, a band is crossed to a stack so the crossing box have the same givens.
More givens in the crossing box are narrowing the search space. An empty crossing box doesn't help at all.

Let cross bands A and B, transposing B to become a stack.
Location of the crossing box doesn't matter (it generates isomorphic grids and puzzles) so we can choose the top left box.
There are 3 choices to select the crossing box from band A.
The row and column transformations of band A doesn't matter.
Relabeling can be done by fixing Box1 to contain 1..9 or, as I did, to leave A in its canonical form and relabel B.
The permutations of rows of the stack B in boxes 4 and 7 doesn't matter.
The rest 108 permutations are described in the above post.
Crossing A to B is isomorphic to crossing B to A, so B >= A additionally truncates the search space.
The next task is to loop over the A and B completions a and b.
When B == A then crossing completion a to completion b is isomorphic to crossing b to a, so at completion level b >= a also works.
Predefined completions a and b are transformed in the same way as A and B respectively.
b not matching a in the crossing box1 are skipped.

At this point we have a subgrid with:
- fixed Band1 and Stack1 cell values;
- fixed givens in Band1 and Stack1.
Unsolved part is to generate valid puzzles which solution grids have the same Band1 and Stack1, givens in Band1 and Stack1 fixed, and more givens in boxes 5,6,8,9 in still unknown positions and with still unknown values.
We can verify that the task is solvable by adding clues in all 36 questionable positions, selecting the values from any valid solution of the puzzle P1 formed by all known 45 cell values in Band1 and Box1. If P1 has no solution, then A and B are incompatible in their respective permutations. Later form another puzzle P2 by emptying in the P1's solution all cells in Band1 and Box1 except the fixed givens. If P2 has multiple solutions, then there are uncovered UA sets located entirely in Band1 and Stack1, which can't be covered by any combination of givens in boxes 5,6,8,9.

At this point all solutions of the puzzle P1 are grid candidates for puzzles.
More complex morphs are skipped by brute force. After A and B are fixed (but not their permutations), I start keeping the identity part of each "successful" grid candidates in cache and skip next occurrences of the grid candidates with the same identity. The identity I am using is the minlex representation of the puzzle P1 with givens (sets a and b) removed. I am not ready to prove whether this is sufficient and never gives false positives, but hope it is.

Up to here it was the generic algorithm.

Now to Fractal Pattern specifics.

All band completions not isomorphic to

Code: Select all: 101 000 000 010 000 000 101 000 000

as described in the above post, are filtered out.

From the 3 possible band A box permutations, only this with candidates a located in Box1 is used.

The positions of the givens within boxes 5,6,8,9 are independent of the rest of the subgrid, and have only 81 non-isomorphic permutations.
Using this shape as a basis

Code: Select all: xxx ... ... xxx ... ... xxx ... ... ... *.* *.* ... .*. .*. ... *.* *.* ... *.* *.* ... .*. .*. ... *.* *.*

the permutations are product of the following independent exchanges:
null, r4<>r5, r5<>r6 (3 choices)
null, r7<>r8, r8<>r9 (3 choices)
null, c4<>c5, c5<>c6 (3 choices)
null, c7<>c8, c8<>c9 (3 choices)
= 3*3*3*3 = 81
These 81 predefined clue position templates are tested against each solution grid.

After fixing a bug, the grid candidates expanded to 49 350 388, and the solver is called 49350388 * 81 = 3 997 381 428 times.

In attempt to understand blue's caching, I tried (w/o actual solving) grid identity as Band1 and Stack1 populated, without removal of the givens in Box1. It resulted in 49 333 619 grids, slightly less than the other identity.

The pass took 13h 30' on my slow machine, confirming the published 7 puzzles.
Without actual solving over the 81 templates, the execution time is less than 4 minutes, including 40 seconds for band completions generation.
The only optimization in the solver is, knowing one of the solutions, to guess to the known solution until it found it, which speeds up the process in this case for about 15%. No small UA sets are generated. Will test whether for 81 puzzles per grid UA testing helps.

MD

by **Serg** » Wed Apr 06, 2011 9:12 pm

Hi, dobrichev!

dobrichev wrote:Enumerating 5-clue band completions we found there are 3483430 possibilities covering all 416 bands (the total of 54+5 column in the referenced post).
Exploiting the Fractal Pattern's property that the middle band crosses middle stack with exactly 5 clues located entirely in the crossing box 5, we can enumerate the possible bands that could be completed with these 5 clues. In other words we can filter the 3483430, removing all completions that have clues in more than one band, different than 2+2+1 column and row distribution, and finally the same min-lex pattern.
After filtering, 1265 valid band completions remain.

Would you clarify some details of finding "n-clue band completitions" (please, define more strictly- what is "band completition")? Let's take a band from 416-bands list (for example, the first band). In what way you find all UAs and choose cells to hit all UAs of the band considered (and what variants of hitting cells set do you take into account)? It would be nice to see an example of a band from 416-bands list processing.

Serg

by **dobrichev** » Wed Apr 06, 2011 10:24 pm

For the case of Fractal Pattern puzzle enumeration, where a batch of 81 puzzles with 25 givens from the same solution grid is tested for uniqueness, using testing again grid's small unavoidable sets increases performance.
The best results are obtained by using only U4 (unavoidable rectangles) where the gain is ~47%. In this case there is no benefit from fast guessing to the known solution. It slightly decreases speed (~ 1%).
The code for U4 generation is posted there.
I also tried with all 2-digit UA generation, and 3-digit 6-cell UA. All combinations of these UA types gave performance gain between 30% and 47%.
The overhead for worst cases is 29% for UA generation + 7% for puzzle scanning for UA before calling the solver.
For the sample of 321508 grids, w/o UA optimization the solver is called 81 times per grid = 26 042 148 times. With optimization the calls are reduced to 13 162 006, or roughly they are halved. For the whole enumeration expected calls are ~1.5 billion.

Cheers,
MD

by **dobrichev** » Wed Apr 06, 2011 11:57 pm

Serg wrote:Hi, dobrichev!
Would you clarify some details of finding "n-clue band completitions" (please, define more strictly- what is "band completition")? Let's take a band from 416-bands list (for example, the first band). In what way you find all UAs and choose cells to hit all UAs of the band considered (and what variants of hitting cells set do you take into account)? It would be nice to see an example of a band from 416-bands list processing.

Hi Serg,
n-clue band completions are a kind of extension of your Investigation of one-band-free patterns, but with no limitation clues to be located in only one box of the questionable unpopulated band.
"Band completion" is a clue combination located entirely in one band, which with addition to the clues outside of this band could generate valid puzzles.
Valid puzzles are those with unique solution.
"n-clue band completion" is band completion consisting of n clues, without requirement for minimality.

Finding the band completions is based on exhaustive search within all possible n clue combinations. The algorithm is based on UA sets and is described in GridChecker, an exhaustive puzzle enumerator. It was several months of work, based on previous work by other people on Checker. All published versions are here.
Below is a copy of one post from the other forum, where it is described how GridChecker works.

Hidden Text: Show

All UA sets located in a band is easy to collect by collecting the solution differences of a puzzle formed by a valid completion of this band, and with all cells in the band cleared. The difference between each 2 solutions is a (not necessarily minimal) UA set. Non-minimal contain smaller UA subsets, which are differences between other two solutions. After removal of non-minimals, only minimal UA remain.
The number of solutions and UA sets for each band are listed in columns 2 and 3 in the table in Bands and low-clue puzzles.

For band completion enumeration I am using an extension coded into GridChecker. I am fixing the 54 clues for the rest of the grid as "givens", and producing the UA only for that band, knowing that all others are hit by the rest 54 clues.
If you can compile the source of GridChecker, I will publish (or send you) the latest version with these extensions. It is easy to trace the logic.

Example in next post. Still don't know how detailed it will be.

Cheers,
MD

by **dobrichev** » Thu Apr 07, 2011 2:32 am

Consider band 261. It participates in 6 of the puzzles for Fractal Pattern.

Code: Select all: 123 456 789 457 189 623 689 732 514 #band 261

Compose a puzzle having at top band 261.

Code: Select all: 123 456 789 457 189 623 689 732 514 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... #puzzle with band 261 at top

Compose a valid solution grid having at top band 261 by solving the above puzzle.

Code: Select all: 123 456 789 457 189 623 689 732 514 214 365 897 365 897 142 798 214 356 532 641 978 841 973 265 976 528 431 #valid grid with band 261 at top

Compose a puzzle from the above grid by removal of all givens in top band

Code: Select all: ... ... ... ... ... ... ... ... ... 214 365 897 365 897 142 798 214 356 532 641 978 841 973 265 976 528 431 #puzzle grid with band 261 emptied

The above puzzle has 156 solutions, and one of them has band 261 at top

Here is the puzzle with some of the solutions

Code: Select all: ...........................214365897365897142798214356532641978841973265976528431 #puzzle 123456789457189623689732514214365897365897142798214356532641978841973265976528431 #band 261 123456789459782613687139524214365897365897142798214356532641978841973265976528431 #band a 123456789687139524459782613214365897365897142798214356532641978841973265976528431 #band b 123456789689732514457189623214365897365897142798214356532641978841973265976528431 #band c ...

Now compare first 27 cells of the rest 155 solutions to band 261 (first listed solution).

Code: Select all: 123456789457189623689732514...................................................... #band 261 123456789459782613687139524...................................................... #band a ...........xx.x.x...xx.x.x....................................................... #unav a 123456789687139524459782613...................................................... #band b .........xx..x.x.xxx..x.x.x...................................................... #unav b 123456789689732514457189623...................................................... #band c .........xxxxxxxxxxxxxxxxxx...................................................... #unav c ...

As we see, unav c has unav b as a subset, therefore it is non-minimal and must be ignored.
Note: Minimality of the UA used is not required, but non-minimal UA don't contribute.

After filtering out the non-minimal UA, from initial 155 UA only the following 19 remain.
Permutable cells are marked with digits, the rest are from band 261.

Code: Select all: 1..4.....4..1.................................................................... 4 .2..5..8..5..8..2................................................................ 6 12...6.8..........68...2.1....................................................... 8 ..3..67.9..7..96.3............................................................... 8 ...........71.9.2...97.2.1....................................................... 8 #unav a ..345.7.9...........973.5.4...................................................... 10 ...4.67.9..7..96....97....4...................................................... 10 .........45..8.6.368..3.5.4...................................................... 10 #unav b ..3.5.7..4.7...6.36...3.5.4...................................................... 11 .23....89....89.23.89.32......................................................... 12 .23.567...57.896...89.32......................................................... 14 ...4.67.9.5..896.3.8.73.5.4...................................................... 14 .23.567..457.8.6.368..32..4...................................................... 16 1..456789....89.236..732514...................................................... 18 .23....894571..6236897..514...................................................... 18 12.4.6.89.571.962.6897..514...................................................... 19 1.34567.9..71.9.236..732514...................................................... 19 1.345.789457.8.6.36897..514...................................................... 20 1..45.78.4.7.896236.9732514...................................................... 20

A "band completion of band 261" is every clue combination that simultaneously hits all these 19 UA.

There are no 2-clue combinations that covered all UA because these 3 UA are mutually disjoint and require at least 3 clues, one for each UA.

Code: Select all: 1..4.....4..1.................................................................... 4 .2..5..8..5..8..2................................................................ 6 ..3..67.9..7..96.3............................................................... 8

Without going to details, there are no 3-clue combinations too, but there are 388 4-clue combinations.
Below are first 3 and last 3 of them, when ordered alphabetically.

Code: Select all: ....5.......1..6.......2... ....5.......1..6...8....... ....5.......1.9....8....... ... 12.........7..............4 12.........7............5.. 12.........7..........3....

Each of these 4-clue combination is cappable to compose a valid puzzle without any additional givens in this band, and they are "band completions".

Each of these 4-clue completions produces 23 non-minimal 5-clue completions by adding an extra clue at each of 23 free positions.
Additionally, there could be 5-clue completions not formed as supersets of any of the 4-clue completion.

Four of the 5-clue completions are related to Fractal Pattern. Here is one of them.

Code: Select all: .....6......18.......73....

in 2-d form

Code: Select all: ... ..6 ... ... 18. ... ... 73. ...

swap rows 1,2

Code: Select all: ... 18. ... ... ..6 ... ... 73. ...

swap columns 5,6

Code: Select all: ... 1.8 ... ... .6. ... ... 7.3 ...

and place it in band 2 to compose Fractal.

This pattern by itself is not valuable, but we additionally know all "non-givens" within the band, which will form the "target grid".

Hope this makes the things more clear.

Some parts of the example are made manually and could have typos.

Don't hesitate to ask for other details if necessary.

Cheers,
MD

by **Serg** » Thu Apr 07, 2011 11:41 am

Hi, dobrichev!
Thank you for detailed description of your method. It is now clear to me. I think your method is based on the same idea as blue's method (as far as I understand it) - decompose the whole pattern by simpler parts, filter out variants with unvaidable sets formed by non-clue cells for each part and finally construct the pattern from previosly analyzed parts. Saying in other words, the main idea is to avoid unavoidable sets as possible during variants analyzing.

I am impressed by your way of finding possible band completitions. It is so difficult! (But maybe not so difficult personally for you because it is based on GridChecker and other tools/results that were previously developed/investigated by yourself.)

Thanks for interesting ideas!

Serg

by **JeJ** » Mon Apr 11, 2011 2:49 am

I don't have anything to contribute to this topic, but I just wanted to thank the people who have posted those fractal patterns, they look very nice in a Sudoku program.

by **Serg** » Thu Apr 21, 2011 3:43 pm

Hi, people!
I've found some intersting properties of Fractal Pattern's valid puzzles. 4 puzzles (totally there exist 7 puzzles) have UA sets of order 4 formed entirely by puzzles' filled cells. These puzzles are posted below (puzzles are posted left, UA sets are posted right).

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

This property implies we can produce another valid puzzle from original puzzle by permuting UA set digits. So, we can produce valid puzzle ("puzzle 1a") from "puzzle 1", being non-isomorphic to original "puzzle 1".

Code: Select all: 3 . 2 . . . 4 . 6 3 . 2 . . . . . . # puzzle 1a . 1 . . . . . 2 . . . . . . . . . . 5 . 7 . . . 8 . 3 . . . . . . . . . . . . 2 . 3 . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . 4 . 5 . . . . . . . . . . . . 2 . 3 . . . 6 . 8 2 . 3 . . . . . . . 6 . . . . . 4 . . . . . . . . . . 8 . 1 . . . 5 . 9 . . . . . . . . .

It turns out that "puzzle 1a" is isomorphic to "puzzle 3", and vice versa, "puzzle 3a" is isomorphic to "puzzle 1". So, by UA set permutation we can produce "puzzle 3" from "puzzle 1" and vice versa. In the same way we can produce "puzzle 4" from "puzzle 2" and vice versa.

It is interesting - have known 17-clues puzzles (39-clues minimal puzzles, etc.) UA sets among their clues? If any, can we use this property to produce other valid puzzles of appropriate type?

Serg

by **ronk** » Thu Apr 21, 2011 4:36 pm

Serg wrote:It is interesting - have known 17-clues puzzles (39-clues minimal puzzles, etc.) UA sets among their clues? If any, can we use this property to produce other valid puzzles of appropriate type?

I presume you mean "UA sets" which are fully populated with clues. That's definitely an interesting property for the fractal, but I'd be surprised if the property even exists in a 17-puzzle.

by **dobrichev** » Thu Apr 21, 2011 5:21 pm

Good observation, ronk.

Known 17's were searched for "twins". Here I counted 96 twins in the Gordon's collection. Now I can't remember what exactly I counted, since there were cases where puzzles A and B are twins, B and C are twins, but A and C are not. So 96 is probably not the pair count but the number of puzzles which have 1 or more twins.

by **Serg** » Fri Apr 22, 2011 8:16 am

Hi, ronk, dobrichev!
Thank you for your replies. dobrichev, thank you for your link. Your results are very interesting for me. I've searched twin puzzles in exactly the same way as you.

dobrichev wrote:Now I can't remember what exactly I counted, since there were cases where puzzles A and B are twins, B and C are twins, but A and C are not. So 96 is probably not the pair count but the number of puzzles which have 1 or more twins.

Sounds somewhat strange... Puzzles A, B, C in your example all have the same completition, aren't they? If so, they all are twins (maybe "multiplies"?).

Serg

[Edited: link to wrongly published new horizontally symmetric 18-clue puzzles was deleted]

The New Sudoku Players' Forum

Valid puzzles for Fractal Pattern

Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

testing against U4 before solving helps

Re: Valid puzzles for Fractal Pattern

Example

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern

Re: Valid puzzles for Fractal Pattern