Values of givens symmetrically identical

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

Values of givens symmetrically identical

Postby m_b_metcalf » Tue Apr 27, 2021 10:01 am

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
Last edited by m_b_metcalf on Tue Apr 27, 2021 11:12 am, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Values of givens symmetrically identical

Postby coloin » Tue Apr 27, 2021 10:32 am

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
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: Values of givens symmetrically identical

Postby m_b_metcalf » Tue Apr 27, 2021 2:22 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Values of givens symmetrically identical

Postby AnotherLife » Tue Apr 27, 2021 4:07 pm

m_b_metcalf wrote:
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
Bogdan
AnotherLife
 
Posts: 172
Joined: 07 January 2021
Location: Moscow, Russia

Re: Values of givens symmetrically identical

Postby eleven » Tue Apr 27, 2021 11:19 pm

m_b_metcalf wrote: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.
eleven
 
Posts: 2785
Joined: 10 February 2008

Re: Values of givens symmetrically identical

Postby m_b_metcalf » Wed Apr 28, 2021 4:51 am

eleven wrote:
m_b_metcalf wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Values of givens symmetrically identical

Postby mith » Tue May 04, 2021 2:02 am

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.
mith
 
Posts: 803
Joined: 14 July 2020

Re: Values of givens symmetrically identical

Postby 999_Springs » Tue May 04, 2021 7:43 am

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
999_Springs
 
Posts: 585
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Values of givens symmetrically identical

Postby m_b_metcalf » Tue May 04, 2021 1:05 pm

mith wrote: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
]
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Values of givens symmetrically identical

Postby 999_Springs » Fri May 07, 2021 1:27 am

999_Springs wrote: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 :cry: 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.
999_Springs
 
Posts: 585
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Values of givens symmetrically identical

Postby coloin » Sat May 08, 2021 4:09 pm

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 !
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: Values of givens symmetrically identical

Postby m_b_metcalf » Sat May 08, 2021 7:25 pm

coloin wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Values of givens symmetrically identical

Postby 999_Springs » Sat May 08, 2021 8:32 pm

m_b_metcalf wrote:
coloin wrote: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
999_Springs
 
Posts: 585
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Values of givens symmetrically identical

Postby coloin » Sat May 08, 2021 8:37 pm

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 !
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: Values of givens symmetrically identical

Postby m_b_metcalf » Sat May 08, 2021 8:47 pm

999_Springs wrote: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.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Next

Return to General