The New Sudoku Players' Forum

[David P Bird]

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

[Mathimagics]

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

[David P Bird]

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
.

[StrmCkr]

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

[Mathimagics]

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

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!

[StrmCkr]

http://forum.enjoysudoku.com/sudoku-subgrid-canonicalization-tool-t32476.html
http://forum.enjoysudoku.com/canonical-puzzle-form-t3054.html
http://forum.enjoysudoku.com/canonical-form-t5215.html
http://forum.enjoysudoku.com/sudoku-9x9-and-sudocoup-nxn-qwh-solvers-t3009.html

some stuff that might help for canonical form
http://sudopedia.enjoysudoku.com/Canonical_Form.html

[url]
post211356.html#p211356[/url] this post in particular is useful

https://www.degruyter.com/downloadpdf/j/comp.2012.2.issue-2/s13537-012-0011-y/s13537-012-0011-y.pdf

[David P Bird]

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
.

[eleven]

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

[Serg]

Hi, Mathimagics!

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]

Hi, eleven!

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

[eleven]

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.

[Serg]

Hi, Mathimagics!

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]

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

[Mathimagics]

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!

[Mathimagics]

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