8
$\begingroup$

I have a Sudoku grid with the property that diagonally adjacent elements are distinct (it is also a torus under the same property).

My question is up to isomorphism, is the grid unique?

Here's the grid: $$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 6& 5& 7& 3& 4& 2& 1& 9& 8\\ \hline 9& 8& 1& 5& 6& 7& 4& 3& 2\\ \hline 3& 2& 4& 8& 9& 1& 6& 5& 7\\ \hline 5& 7& 6& 2& 3& 4& 9& 8& 1\\ \hline 8& 1& 9& 7& 5& 6& 3& 2& 4\\ \hline 2& 4& 3& 1& 8& 9& 5& 7& 6\\ \hline 7& 6& 5& 4& 2& 3& 8& 1& 9\\ \hline 1& 9& 8& 6& 7& 5& 2& 4& 3\\ \hline 4& 3& 2& 9& 1& 8& 7& 6& 5\\ \hline \end{array}$$

To explain the diagonal-free property, if we have:

\begin{array}{c|c} a&b\\ \hline c&d\\ \end{array}

then $a\ne d$ and $b\ne c$. This does NOT imply the the whole diagonal is distinct (as in X-factor).

If we wrap the grid into a cylinder, and then bend the tube into a torus, the diagonal property still holds, so, for example, the $9$ on the base row is considered to be diagonally adjacent to the $4$ and $7$ on the top row.

There are two links on OEIS:

Isomorphism in this instance implies we can change the orientation, change the permutations of the numbers, perform row/column swaps as long as the conditions still hold. This can create grids with no internal diagonals but that are not torii, for example (this is my original grid by the way!):

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1&2&3&7&8&9&4&5&6\\ \hline 7&8&9&4&5&6&1&2&3\\ \hline 4&5&6&1&2&3&7&8&9\\ \hline 6&1&2&3&7&8&9&4&5\\ \hline 9&4&5&6&1&2&3&7&8\\ \hline 3&7&8&9&4&5&6&1&2\\ \hline 5&6&1&2&3&7&8&9&4\\ \hline 8&9&4&5&6&1&2&3&7\\ \hline 2&3&7&8&9&4&5&6&1\\ \hline \end{array}$$

We can see that the $2$ on the base line is diagonally related to the $2$ on the top line, and so this grid is not a torus. The torus example is derived from this one using only the operations defined above.

So I am asking if there is a diagonal-free grid with a quintessentially different structure to either of the two grids given here.

ADDENDUM

For reference here is a Sudoku grid with diagonals, from Conceptis Puzzles:

enter image description here

The diagonally adjacent givens are highlighted - there may be more!

$\endgroup$
5
  • $\begingroup$ I don't understand what you mean by «diagonally adjacent elements are distinct» nor by «it is a torus under the same property». In any case, why would it be unique? Is there anything that makes you guess it is? If that is the case, it would useful to explain it; if not, well, dunno. $\endgroup$
    – Mariano Suárez-Álvarez
    May 18, 2015 at 3:33
  • $\begingroup$ The tags game-theory and group -isomorphism are largely unrelated to your question, by the way. $\endgroup$
    – Mariano Suárez-Álvarez
    May 18, 2015 at 3:36
  • 1
    $\begingroup$ Game theory does not deal with games such as sudoku. As for the explanations, please add hem to the question itself. $\endgroup$
    – Mariano Suárez-Álvarez
    May 18, 2015 at 7:30
  • $\begingroup$ In any case, I still don't undestand what you mean, exactly. Are you saying that the contents of two boxes which touch by a vertex are different, or that all complete diagonals and antidiagonals have 9 different elements, so that the sudoku condition holds for rows, columns, 3x3 blocks, diagonals, and antidiagonals? $\endgroup$
    – Mariano Suárez-Álvarez
    May 18, 2015 at 7:31
  • $\begingroup$ @MarianoSuárez-Alvarez; how does 'diagonally adjacent' imply the whole diagonal is distinct? $\endgroup$
    – JMP
    May 18, 2015 at 7:33

1 Answer 1

Reset to default
2
$\begingroup$

In the general case, a grid will be in an isomorphism equivalence class of $9!\cdot 3!^4 \cdot 2$ corresponding to permutations of the symbols, permutations of the rows and columns, and the symmetry of the square which is not already covered by permutation of the rows and columns. I'm only counting $3!^2$ permutations of the rows rather than $9!$ because most of those $9!$ will break one or more of the $3\times 3$ squares with a Sudoku constraint.

I've set a computer program to generate solutions which match the constraints (and the additional constraint that the first row is $123456789$); so far it has found more than $20000$. The first two are

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1& 2& 3& 4& 5& 6& 7& 8& 9\\ \hline 4& 7& 8& 1& 3& 9& 2& 5& 6\\ \hline \textbf{5}& \textbf{9}& 6& 7& 2& 8& 4& 1& 3\\ \hline 6& 3& 4& 8& 1& 5& 9& 7& 2\\ \hline \textbf{9}& \textbf{5}& 2& 3& 4& 7& 1& 6& 8\\ \hline 7& 8& 1& 9& 6& 2& 5& 3& 4\\ \hline 2& 4& 7& 5& 8& 3& 6& 9& 1\\ \hline 3& 1& 9& 6& 7& 4& 8& 2& 5\\ \hline 8& 6& 5& 2& 9& 1& 3& 4& 7\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1& 2& 3& 4& 5& 6& 7& 8& 9\\ \hline 4& 7& 8& 1& 3& 9& 2& 5& 6\\ \hline \textbf{9}& \textbf{5}& 6& 7& 2& 8& 4& 1& 3\\ \hline 6& 3& 4& 8& 1& 5& 9& 7& 2\\ \hline \textbf{5}& \textbf{9}& 2& 3& 4& 7& 1& 6& 8\\ \hline 7& 8& 1& 9& 6& 2& 5& 3& 4\\ \hline 2& 4& 7& 5& 8& 3& 6& 9& 1\\ \hline 3& 1& 9& 6& 7& 4& 8& 2& 5\\ \hline 8& 6& 5& 2& 9& 1& 3& 4& 7\\ \hline \end{array} $$

which, while clearly closely related, I don't believe to be actually isomorphic. And they're certainly not isomorphic to the grid in your question, which has no rectangle whose four corners match diagonally in this way.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .