Fractal Sudoku

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

Fractal Sudoku

Postby 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.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby 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.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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!
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby 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

#
Ocean
 
Posts: 442
Joined: 29 August 2005


Return to General