Transversals in Sudoku Squares

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

Re: Transversals in Sudoku Squares

Postby David P Bird » Wed Jan 03, 2018 10:24 am

Mathimagics wrote:
David P Bird wrote:I devised it in 2007 in response to a knitting group who wanted a design for an Afghan pattern. It has the properties:
a) that the 9 cells in the same position in each box hold complete 1-9 digit sets for the left and right digits.
b) that every left hand digit is paired once with every right hand digit .
.

Thanks David.

Your properties are essentially the definition of "Orthogonal Sudoku".

If we label the two Sudoku grids A and B (ie grid A = left digits, grid B = right digits), then we find that grid A has NTV = 243 , from which we can obtain 67,158 different orthogonal pairs (Grid B) one of which will (with suitable labelling) will match your example.

Given the high NTV count, I assume that grid A has automorphs. Can anyone confirm?

I can see that your grids have property b) but they don't have property a)

1 2 3 | 4 5 6 | 7 8 9
4 8 7 | 9 2 1 | 5 6 3
9 6 5 | 3 7 8 | 1 2 4
-------------------------
5 3 8 | 2 4 9 | 6 1 7
2 4 9 | 6 1 7 | 8 3 5
7 1 6 | 8 3 5 | 9 4 2
-------------------------
8 7 2 | 5 6 3 | 4 9 1
3 9 1 | 7 8 4 | 2 5 6
6 5 4 | 1 9 2 | 3 7 8

This is your grid from Jan 2nd where I have underlined instances where the same digit occurs in the same positions in different boxes, for example, (3)b1r1c3 and (3)b8r1c3. However, it may be possible to transform it to avoid this.

The Afghan A & B grids have 36 automorphs and B is a morph of A (but I guess that follows automatically).

If you use Excel, I can provide you with a custom worksheet function to canonicalise a solution string (using the Anchor-5 system) to give you automorph counts.
.
David P Bird
2010 Supporter
 
Posts: 983
Joined: 16 September 2008
Location: Middle England

Re: Transversals in Sudoku Squares

Postby Mathimagics » Wed Jan 03, 2018 1:16 pm

David,

My apologies, I didn't read your definition properly! :?

I need to investigate this "Afghan" property further.

WRT canonicalisation, are we talking the same thing? ie: canonical form = "minlex" form
User avatar
Mathimagics
2017 Supporter
 
Posts: 414
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby David P Bird » Wed Jan 03, 2018 3:39 pm

Mathimagics,

The Minilex canonicalisation form for a solution grid forces the top row to 123456789 and picks the transform that give the lowest lexical value for the succeeding rows.
<My Anchor-5 system> forces box 5 to hold 123456789 and forces the position of 5 in the other 8 boxes and then selects the transform with the lowest lexical value. This allows some short cuts to be taken when it is coded into a procedure.
The Excel implementation also counts how many times the canonical form occurs in the 648 possible transforms = the automorph count. This is what I believed most interested you.
Dobrichev has a command line C program <GridChecker> that I believe does the same thing for the mini-lex canonical form.

I have used the 'Afghan' adjective rather loosely. It covers a crocheting method for producing geometrical designs, and the request I responded to asked for a Sudoku based two-colour pattern with 81 squares. My design arose because I wanted to avoid repeating triplets of colours throughout the pattern as would be produced if the most canonical form were used.

David
.
David P Bird
2010 Supporter
 
Posts: 983
Joined: 16 September 2008
Location: Middle England

Re: Transversals in Sudoku Squares

Postby StrmCkr » Wed Jan 03, 2018 5:04 pm

Isn't....
Code: Select all
123456789
45
.
2
as the start... From the full list of lexicon grids if I recall correctly you can fix 12 digits onto a grid ND then anchor one other digit for counts.

then fix 1 digit onto the grid and cycle all permuations (less digit swap)
And noting which combinations return the grid back to the same arrangement placement of cells
But not the starting digits.

These are the automorphism counts.

At least that was my understanding if I'm wrong and that dosen't work I'll delete this post...
Last edited by StrmCkr on Wed Jan 03, 2018 8:04 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Re: Transversals in Sudoku Squares

Postby Mathimagics » Wed Jan 03, 2018 5:47 pm

Hi David

Automorph counts are of interest only because automorph existence seems to correlate with high NTV counts and thus orthogonality. If the NTV = 0 (no transversals) example above has automorphs then this conjectured correlation vanishes. Perhaps you could just check that one for me?

I downloaded GridChecker (v1.23, Win32) but it doesn't run on my box (my cpu is AMD).

Getting back to your "Afghan" example, I am very interested in this form as it might help solve another problem I'm grappling with. I'm surprised that this is not a recognised Sudoku variant, as it is a simple way of providing an extra dimension. For now, let's call a set of corresponding block elements a Pset (corresponding position set).

A SudokuP puzzle is defined as "place a different value in every Row, Column, Block, and Pset".

Mathimagics wrote:If we label the two Sudoku grids A and B (ie grid A = left digits, grid B = right digits), then we find that grid A has NTV = 243 , from which we can obtain 67,158 different orthogonal pairs (Grid B) one of which will (with suitable labelling) will match your example.


Silly me! Yes, one will presumably match, but no amount of relabelling will change the Pset status - each orthogonal Grid B will either have unique values in Psets or not! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 414
Joined: 27 May 2015


Re: Transversals in Sudoku Squares

Postby David P Bird » Wed Jan 03, 2018 8:32 pm

Mathimagics,

Let me start by saying I am a mathematical lightweight who occasionally likes to dabble in the subject. When I try to read the more advanced material, I quickly get lost with the terminology that I don't understand and am forced to give up. You really need a heavyweight such as Dobrichev to help analyse your ideas.

Back in 2007 I considered orthogonal sets of digits in the intersections of a column in each stack and a row in each tier that satisfied the one-of-each Sudoku rule, and called them 'trellis sets'. I found I could identify at least one trellis set in every puzzle and posed the question whether this was universally true. A contributor 'Red Ed' checked this out, using techniques that were beyond my capabilities, and reported that indeed, over 95% of possible solution grids would contain a trellis set or 'silver fish' as he called them. (This exchange was in the UK forum, which is now no more, but it is possible that these names could turn up in a wider search.)

Clearly if a trellis set exists, row and column swaps would allow the member cells to be brought into the same position in each box. What your PSudoku would amount to is a puzzle that was saturated with trellis sets that would allow a host of extra solving techniques to be employed. (Another interesting question is what would be the minimum clue count be for PSudoku firstly when the positions are known and secondly when they have to be deduced because the rows and columns in each band were scrambled?) However, my intuition is that the number of possible puzzles would be so severely restricted that these puzzles would just be curiosities and never make the mainstream.

These observations just about complete my brain dump on this subject!

1. Regarding GridChecker, try using a previous release such as 1.15 which was compiled before Dobrichev switched operating systems – it will probably work. If you can't find it, message me with your e-mail address and I will copy it to you.

2. My canonicalising procedure reports that your grid has an automorph count = 2.

David
.
David P Bird
2010 Supporter
 
Posts: 983
Joined: 16 September 2008
Location: Middle England

Re: Transversals in Sudoku Squares

Postby eleven » Wed Jan 03, 2018 8:46 pm

I understand, that repeating minirows can be beneficial for orthogonality. But i don't yet see that for diagonal symmetric puzzles.
Maybe Serg (pleased to see you again) could check ...
eleven
 
Posts: 1662
Joined: 10 February 2008

Re: Transversals in Sudoku Squares

Postby Serg » Thu Jan 04, 2018 12:24 am

Hi, Mathimagics!
Mathimagics wrote:PS: I still don't have an automorph count/enum function. Can anyone help?

Unfortunately I cannot help you.
There are 2 very popular and useful tools, which can probably be used for puzzles/patterns automorphism counting - "gridchecker" by Mladen Dobrichev and "sudoku" by gsf. I successfully use "gridchecker" for puzzles/patterns canonicalisation, but I don't know how to use it for puzzles automorphism counting. It is very likely that gsf's "sudoku" has possibility of automorphism counting. But one should know magic key sequence to do it. I don't know. Maybe Pat or Tarek or coloin can help - publish command line of "sudoku" tool to count puzzle automorphisms?

Serg
Serg
2017 Supporter
 
Posts: 539
Joined: 01 June 2010
Location: Russia

Re: Transversals in Sudoku Squares

Postby Serg » Thu Jan 04, 2018 12:30 am

Hi, eleven!
eleven wrote:I understand, that repeating minirows can be beneficial for orthogonality. But i don't yet see that for diagonal symmetric puzzles.
Maybe Serg (pleased to see you again) could check ...
Glad to see you too! What do you mean?

Serg
Serg
2017 Supporter
 
Posts: 539
Joined: 01 June 2010
Location: Russia

Re: Transversals in Sudoku Squares

Postby eleven » Thu Jan 04, 2018 6:44 am

Concerning a correlation between grids with automorphisms and orthogonal pairs i first thought of diagonal symmetries and could not find a reason, why orthogonality should be more common there. But obviously it is for multi-automorph puzzles.
I have no tool to find orthogonal pairs. So i hoped, that you could generate a bunch of diagonal symmetric puzzles, and look, how many of them do have orthogonality.
eleven
 
Posts: 1662
Joined: 10 February 2008

Re: Orthogonality - Minimum Transversals

Postby Serg » Thu Jan 04, 2018 11:16 pm

Hi, Mathimagics!
Mathimagics wrote:
Code: Select all
 

  1  2  3  | 4  5  6  | 7  8  9
  4  8  7  | 9  2  1  | 5  6  3
  9  6  5  | 3  7  8  | 1  2  4
  ------------------------------
  5  3  8  | 2  4  9  | 6  1  7
  2  4  9  | 6  1  7  | 8  3  5
  7  1  6  | 8  3  5  | 9  4  2
  ------------------------------
  8  7  2  | 5  6  3  | 4  9  1
  3  9  1  | 7  8  4  | 2  5  6
  6  5  4  | 1  9  2  | 3  7  8
 
 NTV = 17


This yields 6 orthogonal pairs shown below:
. . .

I confirm that published above grid has 17 transversals, which forms 6 orthogonal pairs - namely those you posted.

Serg
Serg
2017 Supporter
 
Posts: 539
Joined: 01 June 2010
Location: Russia

Re: Transversals in Sudoku Squares

Postby Serg » Fri Jan 05, 2018 9:39 pm

Hi, all!
I've done random search for orthogonal grids (10^8 random grids were checked). 5111 orthogonal grids were found. So, I confirm Mathemagics ratio 1:20000 for orthogonal grids random search. Search duration - 12 hours. Minimal number of transversals in a grid - 1, maximal number of transversals in a grid - 159. Minimal number of transversals in orthogonal grid - 18. So, I couldn't beat Mathemagics records for minimal and maximal numbers of transversals in a grid and his record for minimal number of transversals in orthogonal grid.

I've done short random search for "Bird's orthogonal grids" ("Afghan" design by David Bird) - 10^7 random grids were checked. 10 Bird's orthogonal grids only were found. So, I got ratio 1:1000000 for Bird's orthogonal grids random search. I hope to get tomorrow 10^8 random grids search results.

Serg
Serg
2017 Supporter
 
Posts: 539
Joined: 01 June 2010
Location: Russia

Re: Transversals in Sudoku Squares

Postby Mathimagics » Fri Jan 05, 2018 11:10 pm

Hi serg!

Nice work, mate!

I too have confirmed the p(O) estimate of 1 in 20000. See my last post on "Sudoku Enumeration" thread.

Do you have an estimate for p(P), ie: SudokuP?

You might have missed the fact (noted in earlier posts in this thread) that we now know that min NTV = 0 (we found a grid with NO transversals), and max NTV = 279 (which occurs in the most canonical, aka {MC} grid).

I can also report that my search now has identified the new record low NTV for orthogonal grids as 15. That search has been running for several days and tested 1.5 billion grids so far.

Can you describe your method for "Bird's orthogonal grids" search? (aka "Orthog SudokuP", or just "OrthogP")

I presume your 1 in 1,000,000 figure means the chances of a grid being SudokuP and having an orthog pair which is also SudokuP ...


Cheers! 8-)
Last edited by Mathimagics on Sat Jan 06, 2018 1:30 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 414
Joined: 27 May 2015

Re: Transversals in Sudoku Squares

Postby Mathimagics » Fri Jan 05, 2018 11:19 pm

Serg wrote: So, I confirm Mathemagics ratio 1:20000 for orthogonal grids random search.


Now seems an appropriate time to note the reason why my handle (Mathimagics) is spelled the way it is!

Many years ago when I first started fiddling with fractals, I came up with MathImagics. It seemed to be an elegant way of describing the "magical mathematical imagery" in a single handle.

The rest, as they say, is history ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 414
Joined: 27 May 2015

PreviousNext

Return to General