The New Sudoku Players' Forum

[m_b_metcalf]

Occasionally, puzzles are posted where the values of the givens are symmetrical. Symmetry is normally understood to mean s(i, j) = 10-s(10-i, 10-j) (after renumbering when necessary).

I wondered whether puzzles exist where the symmetry means s(i, j) = s(10-i, 10-j). (Perhaps this has been discussed in the distant past, but I can't find any references.) I failed to find one with a unique solution. An example of a pseudo-puzzle with just two solutions is:

Code: Select all

 . 6 1 8 . . 9 . 3
 8 . . 6 . . 2 4 1
 9 . 4 . . . . 8 .
 7 . 5 . . . . 9 .
 . . . . 5 . . . .
 . 9 . . . . 5 . 7
 . 8 . . . . 4 . 9
 1 4 2 . . 6 . . 8
 3 . 9 . . 8 1 6 .

No. of givens =  33

brute found 2 solution(s), 2 or 5 at r1c1

During the search I also found pseudo-puzzles with the maximum possible number of clues, 49 (81 - 8 - 4x3x2), but even they do not have a unique solution:

Code: Select all

 9 5 4 6 . . 3 2 8
 2 8 7 4 . . 9 1 6
 1 3 6 . . 9 5 4 7
 3 9 . . . . 1 . .
 . . . . 9 . . . .
 . . 1 . . . . 9 3
 7 4 5 9 . . 6 3 1
 6 1 9 . . 4 7 8 2
 8 2 3 . . 6 4 5 9

No. of givens =  49

brute found 8 solution(s)

Just for the record.

Mike

[coloin]

Maybe its because its impossible to make a grid solution ... because there is an odd number [9] of clues

Code: Select all

+---+---+---+
|987|6.4|321|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|123|4.6|789|
+---+---+---+  no solution


[m_b_metcalf]

I think the fact is that, for any given solution, there is a second, isomorphic, solution obtained simply by rotation. Thus, the number of solutions is always even and there cannot, therefore, be a unique solution. An example with just two, isomorphic solutions is:

Code: Select all

061800903800600241904000080705000090000050000090000507080000409142006008309008160

261874953857639241934125786725361894418957632693482517586713429142596378379248165
561842973873695241924317685715284396236759814498163527687521439142936758359478162

Solution 2 is solution 1 backwards.

Regards,

Mike

[AnotherLife]

Code: Select all

061800903800600241904000080705000090000050000090000507080000409142006008309008160

261874953857639241934125786725361894418957632693482517586713429142596378379248165
561842973873695241924317685715284396236759814498163527687521439142936758359478162

Hello, Mike,
If you determine r4c5=6 then you get a sudoku rated 7.2 but pretty hard for manual solving. Also, I doubt if it has a one-step solution. I think it is up to you to publish this puzzle because you are the inventor of the pattern.

Best regards,
Bogdan

[eleven]

I think the fact is that, for any given solution, there is a second, isomorphic, solution obtained simply by rotation.

Yes, in a symmetric puzzle with a unique solution you always must get the same solution, when you apply the symmetry (e.g. rotation) - otherwise it would be a second one for the given puzzle. Therfore the solution must have the symmetry too.
As coloin showed, a symmetric solution is not possible, where each digit maps to itself. So you have no or at least 2 solutions for such a puzzle.

[m_b_metcalf]

I think the fact is that, for any given solution, there is a second, isomorphic, solution obtained simply by rotation.

Yes, in a symmetric puzzle with a unique solution you always must get the same solution, when you apply the symmetry (e.g. rotation) - otherwise it would be a second one for the given puzzle. Therfore the solution must have the symmetry too.
As coloin showed, a symmetric solution is not possible, where each digit maps to itself. So you have no or at least 2 solutions for such a puzzle.

Interestingly, during my search I generated probably billions of sample grids and found maybe dozens of examples with the maximum number of 49 symmetric clues (I didn't keep count) but just a single instance of a 2-solution puzzle. So that's a very rare bird.

Mike

[mith]

Trivial to do with a 4x4 of course (and I'd imagine a 16x16 wouldn't be too much harder, just bigger...):

Code: Select all

.1..2.3..3.2..1.

[999_Springs]

6x6 solution grids can also have this property, here is one example, you can get another one by swapping the 4 cells in the middle

123456
465213
236145
541632
312564
654321

observe that this property corresponds exactly to the solution grid being a palindrome when read as a one line string

i still have somewhere on my old laptop a big file of every possible 6x6 sudoku after all the singles are filled in, based on work from mathimagics. there are 542257 of them, and i'll look through them to see if any hard ones have an isomorph that is a palindrome if i can work out how to do it

edit: his 6x6 collection is minlexed by solution grid so all i have to do is find out which of the 49 6x6 solution grids have an isomorph that is a palindrome, which is much easier

[m_b_metcalf]

Trivial to do with a 4x4 of course (and I'd imagine a 16x16 wouldn't be too much harder, just bigger...):

My best so far has 130 symmetric clues, and a further 13 added (marked by a *) to achieve uniqueness:

Code: Select all

  .  .  .  .  1 11* .  .  4 14* .  7  .  .  3  2 
  .  .  2  .  3  7* .  .  . 11*10  .  .  .  1* . 
  3  .  .  .  .  .  .  .  2  9  .  .  .  7  .  . 
  . 10 13  4  9  .  .  .  1  3  .  .  .  . 12  . 
 16  8 14  5 11  9 13  6 15  1  3 10  7  .  2  . 
  1  4  3  2  8  5 15 16  9  7  6 12  . 11  . 10 
  .  .  .  .  4  1 12  3 11  .  . 13  8 16  6  5 
 13 11  .  .  2  . 10  .  5  4* . 16  3  1 15* . 
  .  .  1  3 16  .  .  5  . 10  .  2  6* . 11 13 
  5  6 16  8 13  .  . 11  3 12  1  4  .  .  .  . 
 10  . 11  . 12  6  7  9 16 15  5  8  2  3  4  1 
  .  2  .  7 10  3  1 15  6 13  9 11  5 14  8 16
  6*12  . 16* .  .  3  1  .  .  .  9  4 13 10  .   
  .  .  7  .  . 12* 9  2  .  .  .  .  .  .  .  3 
 11* 9* .  .  . 10  .  .  .  .  .  3  .  2  .  . 
  2  3  .  .  7  .  .  4  .  .  .  1  .  .  .  .      SE 7.3

Hope you like it.

Regards,

Mike

[Edit: Puzzle with more clues and fewer added:

Code: Select all

  7 11  .  3 14  .  .  1  6 15 16  .  .  .  .  .
  .  . 10  .  .  .  6  . 11  1  .  .  .  9  . 16
  9  .  6  .  3  .  5 16  .  . 12  .  7  .  1  .
  1  4 16  . 12  .  .  .  .  .  . 13 14 11  6  .
  6 15  .  .  .  .  .  .  .  .  . 16  . 14  . 12
 11 10 13 16  1  3 14  9  8 12 15  .  .  4  7  5
  .  .  7 12 11  6 13  2 14 10  5  4  .  . 16 15
 14  2  5  4 15  7 16 12  3 11  1  .  .  8 13 10
 10 13  8  .  .  1 11  3 12 16  7 15  4  5  2 14
 15 16  .  .  4  5 10 14  2 13  6 11 12  7  .  .
  5  7  4  .  . 15 12  8  9 14  3  1 16 13 10 11
 12  . 14  . 16  .  .  .  .  .  .  .  .  . 15  6
  .  6 11 14 13  .  .  .  .  .  . 12  . 16  4  1
  .  1  .  7  . 12  .  . 16  5 14  3  .  6  .  .
 16  .  9  .  .  .  1 11  .  6  .  .  .  .  .  .
  .  .  .  .  . 16  .  6  1  .  .  .  .  .  .  .  136 symmetric clues plus 8 added, SE 7.3

]

[999_Springs]

i still have somewhere on my old laptop a big file of every possible 6x6 sudoku after all the singles are filled in, based on work from mathimagics. there are 542257 of them, and i'll look through them to see if any hard ones have an isomorph that is a palindrome if i can work out how to do it

edit: his 6x6 collection is minlexed by solution grid so all i have to do is find out which of the 49 6x6 solution grids have an isomorph that is a palindrome, which is much easier

well this was the biggest waste of time in the universe.

of the 49 6x6 solution grids, 4 have a palindromic isomorph
231465645213123654456321312546564132
123546456213231465564132312654645321
123465456132315246642513231654564321
234165615243123654456321342516561432

i chose to look at the 542257 not-all-singles 6x6s only after all the singles were filled in, because if such a palindromic not-all-singles 6x6 exists, then doing all the singles cannot break the palindromic property since any single will have its counterpart on the other side of the grid meaning that it will be palindromic when you do both singles. that means that i won't miss any palindromic not-all-singles puzzles if i insist on doing all the singles at the start. and of course, gurth's symmetry theorem means that any palindromic puzzle must have a palindromic solution if unique

44144 of the 542257 have a solution that has a palindromic isomorph. 1084 of these 44144 have each digit occurring an even number of times in the puzzle, which is a necessary condition

ZERO of the puzzles have a palindromic isomorph i've checked my code multiple times and am confident that there is no bug and these palindromic not-all-singles 6x6 puzzles don't exist. what a waste of time. next time i get this bored i'll throw toilet paper at a tree instead since that would be a more productive use of my time

i wonder if there is any reason why not-all-singles palindromic 6x6s cannot exist but can't think of one

edit: i checked for near misses. 0 of the 44144 puzzles were 1 clue away from being palindromic. 44 were 2 away, all of which had #3 of the above palindromic grids as their solution. all 44 were singles-only if i add the symmetric counterparts of the 2 extra clues. boring.

[coloin]

Surely its possible to get a palindromic puzzle !!!!
Take a palindromic solution grid [6*6,16*16]
Remove symetrical redundant clues .... until you get a minimal puzzle !

[m_b_metcalf]

Surely its possible to get a palindromic puzzle !!!!
Take a palindromic solution grid [6*6,16*16]
Remove symmetrical redundant clues .... until you get a minimal puzzle !

And where, pray, does the 16x16 palindromic solution grid come from? I ran a highly biased grid generator for hours and the best I got was the grid above with 136 of the 256 clues symmetrical. Maybe someone else has a better idea.

The grid below is band-wise palindromic:

Code: Select all

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  9 10 11 12 13 14 15 16  1  2  3  4  5  6  7  8
  8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9
 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

 13 14 15 16  1  2  3  4  5  6  7  8  9 10 11 12
  4  3  2  1 16 15 14 13 12 11 10  9  8  7  6  5
  5  6  7  8  9 10 11 12 13 14 15 16  1  2  3  4
 12 11 10  9  8  7  6  5  4  3  2  1 16 15 14 13

  2  1  4  3  6  5  8  7 10  9 12 11 14 13 16 15
 10  9 12 11 14 13 16 15  2  1  4  3  6  5  8  7
  7  8  5  6  3  4  1  2 15 16 13 14 11 12  9 10
 15 16 13 14 11 12  9 10  7  8  5  6  3  4  1  2

 14 13 16 15  2  1  4  3  6  5  8  7 10  9 12 11
  3  4  1  2 15 16 13 14 11 12  9 10  7  8  5  6
  6  5  8  7 10  9 12 11 14 13 16 15  2  1  4  3
 11 12  9 10  7  8  5  6  3  4  1  2 15 16 13 14

[999_Springs]

Surely its possible to get a palindromic puzzle !!!!
Take a palindromic solution grid [6*6,16*16]
Remove symmetrical redundant clues .... until you get a minimal puzzle !

And where, pray, does the 16x16 palindromic solution grid come from? I ran a highly biased grid generator for hours and the best I got was the grid above with 136 of the 256 clues symmetrical. Maybe someone else has a better idea.

i did this by hand in five minutes

Code: Select all

1234 5678 9abc defg
5678 9abc defg 1234
9abc defg 1234 5678
defg 1234 5678 9abc

3412 7856 bc9a fgde
7856 bc9a fgde 3412
bc9a fgde 3412 7856
fgde 3412 7856 bc9a

a9cb 6587 2143 edgf
6587 2143 edgf a9cb
2143 edgf a9cb 6587
edgf a9cb 6587 2143

cba9 8765 4321 gfed
8765 4321 gfed cba9
4321 gfed cba9 8765
gfed cba9 8765 4321

if i wanted to get more palindromic 16x16s, including ones that aren't made of 16 4x4 latin squares glued together, i would start with an empty 16x16 grid and randomly fill in opposite pairs of values at the same time, checking for the existence of a solution at each step. i'm pretty sure i could do this by hand by clicking buttons on 1to9only's 16x16 sudoku explainer clone', but i don't have it

coloin, of course that's true and anyone could do that, but what i showed was that all palindromic 6x6 puzzles must be all singles, which makes them really boring

[coloin]

I got this far ... well done ... maybe that method would work !!

Code: Select all

+------------+-------------+-------------+-------------+
| 1  2  3  4 |  5  6  7  8 |  9  10 11 12| 13 14 15 16 |
| 5  6  7  8 |  9 10 11 12 |  13 14 15 16|  1  2  3  4 |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  5  6  7  8 |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  9 10 11 12 |
+------------+-------------+-------------+-------------+
| .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
+------------+-------------+-------------+-------------+
| .  .  .  . | .  .  .  .  | .  .  .  .  | .  .  .  .  |
| .  .  .  . | .  .  .  .  | .  .  .  .  | .  .  .  .  |
| .  .  .  . | .  .  .  .  | .  .  .  .  | .  .  .  .  |
| .  .  .  . | .  .  .  .  | .  .  .  .  | .  .  .  .  |
+------------+-------------+-------------+-------------+
| .  .  .  . |  .  .  .  . |  .  .  .  . | 16 15 14 13 |
| .  .  .  . |  .  .  .  . |  .  .  .  . | 12 11 10  9 |
| .  .  .  . |  .  .  .  . |  .  .  .  . |  8  7  6  5 |
| 16 15 14 13|  12 11 10 9 |  8  7  6  5 |  4  3  2  1 |
+------------+-------------+ ------------+-------------+


yes they must all be double singles .... and sometimes Zero is an important negative result !

[m_b_metcalf]

i did this by hand in five minutes

Code: Select all

1234 5678 9abc defg
5678 9abc defg 1234
9abc defg 1234 5678
defg 1234 5678 9abc

3412 7856 bc9a fgde
7856 bc9a fgde 3412
bc9a fgde 3412 7856
fgde 3412 7856 bc9a

a9cb 6587 2143 edgf
6587 2143 edgf a9cb
2143 edgf a9cb 6587
edgf a9cb 6587 2143

cba9 8765 4321 gfed
8765 4321 gfed cba9
4321 gfed cba9 8765
gfed cba9 8765 4321

if i wanted to get more palindromic 16x16s, including ones that aren't made of 16 4x4 latin squares glued together, i would start with an empty 16x16 grid and randomly fill in opposite pairs of values at the same time, checking for the existence of a solution at each step. i'm pretty sure i could do this by hand by clicking buttons on 1to9only's 16x16 sudoku explainer clone', but i don't have it

Ah, yes, so here's a puzzle, symmetrically minimal:

Code: Select all

  1  .  .  4  .  6  7  .  . 10 11  . 13  .  . 16
  .  .  7  .  .  .  . 12 13  .  .  .  .  2  .  .
  .  .  . 12  . 14  .  .  .  .  3  .  5  .  .  .
  . 14  .  .  1  .  .  4  5  .  .  8  .  . 11  .
  .  4  .  2  .  .  .  .  .  .  . 10 15  . 13  .
  .  8  .  .  .  .  9  .  . 16  .  .  .  .  1  .
 11  .  . 10  . 16 13 14  3  4  1  .  7  .  .  6
 15 16  .  .  3  4  .  2  .  .  5  6  .  .  9 10
 10  9  .  .  6  5  .  .  2  .  4  3  .  . 16 15
  6  .  .  7  .  1  4  3 14 13 16  . 10  .  . 11
  .  1  .  .  .  . 16  .  .  9  .  .  .  .  8  .
  . 13  . 15 10  .  .  .  .  .  .  .  2  .  4  .
  . 11  .  .  8  .  .  5  4  .  .  1  .  . 14  .
  .  .  .  5  .  3  .  .  .  . 14  . 12  .  .  .
  .  .  2  .  .  .  . 13 12  .  .  .  .  7  .  .
 16  .  . 13  . 11 10  .  .  7  6  .  4  .  .  1  Very hard.

and a minimal version (6 more clues removed):

Code: Select all

  1  .  .  4  .  6  7  .  . 10 11  . 13  .  . 16
  .  .  7  .  .  .  . 12 13  .  .  .  .  2  .  .
  .  .  . 12  . 14  .  .  .  .  3  .  5  .  .  .
  . 14  .  .  1  .  .  .  5  .  .  8  .  . 11  .
  .  4  .  2  .  .  .  .  .  .  . 10 15  . 13  .
  .  8  .  .  .  .  9  .  . 16  .  .  .  .  1  .
 11  .  . 10  . 16 13 14  .  4  1  .  7  .  .  6
 15 16  .  .  3  4  .  2  .  .  5  6  .  .  9 10
 10  9  .  .  6  5  .  .  2  .  4  3  .  .  . 15
  6  .  .  7  .  1  4  . 14 13 16  . 10  .  . 11
  .  1  .  .  .  . 16  .  .  9  .  .  .  .  8  .
  .  .  . 15 10  .  .  .  .  .  .  .  2  .  4  .
  . 11  .  .  8  .  .  5  .  .  .  1  .  . 14  .
  .  .  .  5  .  3  .  .  .  . 14  . 12  .  .  .
  .  .  2  .  .  .  . 13 12  .  .  .  .  7  .  .
 16  .  . 13  . 11 10  .  .  7  6  .  4  .  .  1 Even harder.