## Fractal Sudoku

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

### Fractal Sudoku

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

Posts: 256
Joined: 16 July 2005

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   00XXXX   XXX   XXX   X0X   X0X   XX0   XX0XXX   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                    00X0X0  is equivalent to  XX0X0X                    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.
Ocean

Posts: 442
Joined: 29 August 2005

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

Ocean,
Obviously, I’m missing something.
Why your list of empty boxes doesn’t include :
Code: Select all
`00X0XXXXX00X00XXXX`

Thanks
JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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

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!
Ocean

Posts: 442
Joined: 29 August 2005

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

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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

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

Posts: 256
Joined: 16 July 2005

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.92.3.8.4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3..14.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.7...2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1..4..2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.89..2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8.6.2.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8..12.4.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...274.......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.41......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.43......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.48......1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.5.....1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4..1....1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4...7...1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4....6..1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.....5.1.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4......61.......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......18......5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.3.....5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1..9....5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1...2...5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1...4...5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1...6...5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.....3.5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.....4.5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.....6.5.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1......25.9...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......539...1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.91..1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.92..1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.93..1.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9..21.9...6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9.5.6.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9..36.7.5.....8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.4...8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5..9..8.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5....18.4.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....824.7...5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.71..5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7.6.5.92.3...4.5.1.....2.6.4...7.8...2.4.......1.......5.9...1.9...6.7.5.....8.4.7..25.9`

#
Ocean

Posts: 442
Joined: 29 August 2005