The New Sudoku Players' Forum

by **Moschopulus** » Thu Jul 06, 2006 9:38 am

Consider a sudoku where the pattern of clues in each box is the same, and the pattern of empty/nonempty boxes also follows the clue pattern. Here's an example given by JPF:

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

Such a sudoku could be called a fractal sudoku.
Another fractal sudoku pattern is

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

Are there any puzzles with this pattern?

There are at most 2^9=512 possible fractal sudoku patterns. JPF asked how many are valid, and how many there are up to equivalence.

Here's a first attempt at some counting. There are 2^3=8 possible patterns for a row (in a 3x3 box). Therefore there are 7^3=343 patterns that have no empty row. Of these, 3^3 -3=78 have an empty column. So 343-78=265 patterns have no empty row and no empty column.

This means there are at most 265 valid patterns, if I have counted right.

But not all these are valid. Some of these have 5 or 6 empty boxes, such as
xoo
oxo
oox
which we know is not possible. I haven't counted these yet.

by **Ocean** » Thu Jul 06, 2006 10:40 am

Interesting concept.

The possible fractal patterns has to be a subset of the possible configurations of empty boxes.
These were found to be:

Code: Select all: XXX 0XX 00X 0XX 0XX 00X 00X XXX XXX XXX X0X X0X XX0 XX0 XXX XXX XXX XXX XX0 XXX XX0

All other box configurations can be achieved from the basic patterns by valid permutations of the boxes (included transposition). Five or more empty boxes did not result in valid sudokus.

Conjecture: All fractal patterns can be achieved from the basic patterns by permutations of columns, rows and boxes (included transposition).

For instance:

Code: Select all: X0X 00X 0X0 is equivalent to XX0 X0X XX0 (The first has higher symmetry, while the latter fits easier into the pattern hierarchy).

(A challenge: prove or disprove this conjecture).

The crucial question for fractal patterns is whether the most 'difficult' patterns are possible. The easier patterns can always be achieved by filling in holes in the more difficult ones.

by **JPF** » Thu Jul 06, 2006 12:37 pm

Ocean wrote:These were found to be:
Code: Select all
XXX 0XX 00X 0XX 0XX 00X 00X XXX XXX XXX X0X X0X XX0 XX0 XXX XXX XXX XXX XX0 XXX XX0

Ocean,
Obviously, I’m missing something.
Why your list of empty boxes doesn’t include :

Code: Select all: 00X 0XX XXX 00X 00X XXX

Thanks
JPF

by **Ocean** » Thu Jul 06, 2006 12:57 pm

JPF wrote:Ocean,
Obviously, I’m missing something.
Why your list of empty boxes doesn’t include :
Code: Select all
00X 0XX XXX 00X 00X XXX

Thanks
JPF

Oh, sorry. I should have pointed to the previous discussions. You are quite correct that these patterns have to be considered. But if we can rely on kjellfp's search program, they can be excluded: No sudoku exists with these patterns.

But: If we also consider puzzles with more than one solution, the whole range of 'empty patterns' should be included!

by **JPF** » Thu Jul 06, 2006 5:39 pm

Ocean wrote:Oh, sorry. I should have pointed to the previous discussions.

Thanks.
I’m stupid. I had read that thread.

Ocean wrote:The crucial question for fractal patterns is whether the most 'difficult' patterns are possible. The easier patterns can always be achieved by filling in holes in the more difficult ones.

You are perfectly right.
I don’t have any proposal for the 4 empty boxes.

Here are examples of the two 3 empty boxes fractals.

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

(3 steppers)

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

Ocean wrote:Conjecture: All fractal patterns can be achieved from the basic patterns by permutations of columns, rows and boxes (included transposition).

Your conjecture is easy to verify as there are only 6 cases to study.
For the last one , for example :

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

C(i,j) is the permutation of columns i and j
R(i,j) is the permutation of rows i and j
B(i,j) is the permutation of bands i and j
S(i,j) is the permutation of stacks i and j

we use these ops which leave the patterns equivalent :
C(2,3) ; C(5,6) ; C(8,9) ; R(1,2) ; R(4,5) ; R(7,8) ; B(1,2) ; S(2,3)
And we get this equivalent pattern :

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

Finally, back to the initial question, there are only 7 (maybe 6 ) non equivalent and valid fractal sudoku patterns ?

JPF

by **JPF** » Fri Jul 07, 2006 8:36 am

The best I could find so far has 2 solutions :

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

[Fully symmetric, 20-8-4-2-1]

Ocean, I know you are an expert to make a valid puzzle from a 2 solutions one.

JPF

by **Moschopulus** » Sat Jul 08, 2006 12:57 pm

Nice work guys.

For the pattern with 4 empty boxes, I thought maybe Ocean found one like that in some other thread but I don't know which.

by **Ocean** » Sat Jul 08, 2006 7:24 pm

JPF wrote:The best I could find so far has 2 solutions :
[...]
Ocean, I know you are an expert to make a valid puzzle from a 2 solutions one.

No immediate success this time.

Your puzzle with two solutions "has" a size-8 minimal unavoidable set. This would give rise to 16 different "almost fractal" puzzles. (Fractal structure with one impurity).

Code: Select all: JPF's puzzle (2-permutable set marked with x). *-----------* |6x2|xx.|8.7| |.3.|...|.1.| |7x8|xx.|9.2| |---+---+---| |...|2.9|...| |...|.6.|...| |...|8.3|...| |---+---+---| |9.1|...|3.4| |.7.|...|.8.| |2.4|xx.|7.6| *-----------*

My earlier "best" achievement in this pattern was a puzzle with 3 solutions. This had a rather large minimal 3-permutable set (34 cells). 3-permutable sets have the property that each cell in such a set always gives either 1 or 3 alternatives for fixing the whole set.

Code: Select all: Three-solution puzzle (the 3-permutable set marked with x). *-----------* |2.3|xxx|4.5| |.1.|xx.|.2.| |6.4|...|7.8| |---+---+---| |xxx|2x4|xxx| |xxx|x1x|xxx| |.xx|5x9|x.x| |---+---+---| |1.9|.xx|6.7| |.5.|xx.|x8x| |4.7|xxx|5.9| *-----------* # # The 42 derived puzzles (fractal structure with one impurity): # 2.39..4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3.8.4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3..14.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.7...2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1..4..2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.89..2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8.6.2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8..12.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...274.......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.41......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.43......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.48......1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.5.....1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4..1....1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4...7...1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4....6..1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.....5.1.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4......61.......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......18......5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.3.....5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1..9....5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1...2...5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1...4...5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1...6...5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.....3.5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.....4.5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.....6.5.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1......25.9...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......539...1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.91..1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.92..1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.93..1.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9..21.9...6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9.5.6.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9..36.7.5.....8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.4...8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5..9..8.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5....18.4.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....824.7...5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.71..5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7.6.5.9 2.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7..25.9

#

The New Sudoku Players' Forum

Fractal Sudoku

Fractal Sudoku