La transformación de un cuadrado latino en un sudoku

Question

Puede cualquier $9\times 9$ - latina, la Plaza se transforma en un sudoku, por sólo el intercambio de filas y columnas (se permite la mezcla de fila y de columna intercambios arbitarily y no hay límite para el número de los intercambios) ?

Answer 1

No, esto no se puede:

$$ L= \begin{bmatrix} 8 & 9 & 5 & 4 & 7 & 3 & 6 & 2 & 1 \\ 4 & 3 & 2 & 6 & 9 & 8 & 5 & 1 & 7 \\ 1 & 5 & 3 & 8 & 4 & 2 & 9 & 7 & 6 \\ 3 & 1 & 7 & 9 & 5 & 6 & 4 & 8 & 2 \\ 6 & 2 & 4 & 5 & 3 & 1 & 7 & 9 & 8 \\ 5 & 7 & 1 & 3 & 2 & 4 & 8 & 6 & 9 \\ 9 & 6 & 8 & 2 & 1 & 7 & 3 & 4 & 5 \\ 7 & 8 & 9 & 1 & 6 & 5 & 2 & 3 & 4 \\ 2 & 4 & 6 & 7 & 8 & 9 & 1 & 5 & 3 \\ \end{bmatrix} . $$

Will Jagy's answer implies that if we generate a random Latin square of order $9$, it will very likely not be equivalent to a sudoku by permuting the rows and columns. So I generated a random Latin square $L$ (above) of order $9$, with rows/columns/symbols in $\{1,2,\ldots,9\}$.

We can permute the rows and columns in $9!^2$ ways. However, if we permute e.g. only the first three rows, we preserve sudoku-ness (and non-sudoku-ness). The same thing if we permute the second three rows (i.e., rows $\{4,5,6\}$), the first three columns, and so on.

Let $$G=\langle (1,2),(1,2,3),(4,5),(4,5,6),(7,8),(7,8,9)\rangle \leq S_9.$$ Then $G$ acts on $S_9$ by composition. There are $|S_9|/|G|=9!/(3!)^3=1680$ orbits under this action, so it is sufficient to check $(1680)^2=2822400$ row-column permutation pairs to verify that $L$ no puede ser transformado en un sudoku, por permuting las filas y las columnas. Hice esto en la computadora usando GAP:

L:=
[ [ 8, 9, 5, 4, 7, 3, 6, 2, 1 ], 
  [ 4, 3, 2, 6, 9, 8, 5, 1, 7 ], 
  [ 1, 5, 3, 8, 4, 2, 9, 7, 6 ], 
  [ 3, 1, 7, 9, 5, 6, 4, 8, 2 ], 
  [ 6, 2, 4, 5, 3, 1, 7, 9, 8 ], 
  [ 5, 7, 1, 3, 2, 4, 8, 6, 9 ], 
  [ 9, 6, 8, 2, 1, 7, 3, 4, 5 ], 
  [ 7, 8, 9, 1, 6, 5, 2, 3, 4 ], 
  [ 2, 4, 6, 7, 8, 9, 1, 5, 3 ] ];

G:=Group((1,2),(1,2,3),(4,5),(4,5,6),(7,8),(7,8,9));;
Orbs:=Orbits(G,SymmetricGroup(9),OnRight);;
Reps:=List(Orbs,O->O[1]);;

PermuteRowsMatrix:=function(L,perm)
  return List([1..Size(L)],i->L[i^Inverse(perm)]);
end;;

PermuteColumnsMatrix:=function(L,perm)
  return List([1..Size(L)],i->List([1..Size(L[1])],j->L[i][j^Inverse(perm)]));
end;;

IsSudoku:=function(M)
  local r,c,i,j,S;
  for r in [1..3] do
    for c in [1..3] do
      S:=[];
      for i in [1..3] do
        for j in [1..3] do
          Append(S,[M[3*(r-1)+i][3*(c-1)+j]]);
        od;
      od;
      if(Set(S)<>[1..9]) then return false; fi;
    od;
  od;
  return true;
end;;

for alpha in Reps do
  for beta in Reps do
    M:=PermuteRowsMatrix(PermuteColumnsMatrix(L,beta),alpha);
    if(IsSudoku(M)) then
      Print("This Latin square can be transformed into the following Sudoku square by row/column permutations:\n",M,"\n");
    fi;
  od;
od;

Answer 2

dice 5,524,751,496,156,892,842,531,225,600 nueve por nueve cuadrados latinos, entonces 6,670,903,752,021,072,936,960 sudoku, la proporción de alrededor de un millón. Mientras tanto $9! = 362,880$ $(9!)^2 \approx 1.3168 \cdot 10^{11},$ mucho más grande que un millón. Así, no podemos regla de cualquier cosa por simple conteo; tal vez la más complicada de contar...

Nota: podría ser vale la pena considerar la rectangular tipos, por ejemplo, usted puede hacer un 6 por 6 rompecabezas de seis 2 por 3 rectángulos, cada uno de los cuales es necesario para contener los números del 1 al 6. En esa nota, cualquier $n$ $n$ sudoku compone de (paralelo) 1 $n$ rectángulos es sólo un cuadrado latino, no hay transformación requerida. Esto sugiere que la rectangular tipo de puzzles obtener más restrictivos como los sub-bloques de acercarse a la plaza.

Answer 3

No una respuesta, pero demasiado complicado para un comentario.

Un $9\times 9$ cuadrado latino es un mapa de $S:N\times N\to N$ con determinadas propiedades, donde $N=\{1,2,\dots,9\}$.

$S$ puede ser un Sudoku por permuting columnas y filas, si y sólo si existen dos particiones $$N=U_1\cup U_2\cup U_3 = V_1\cup V_2\cup V_3$$ such that $S(U_i\times V_j)=N$ for all $i,j$.

(Si $S$ ya estaba en el Sudoku de la forma, luego $U_1=V_1=\{1,2,3\}$, $U_2=V_2=\{4,5,6\}$, y $U_3=V_3=\{7,8,9\}$.)

Answer 4

Abundando en mi forma de pensar en el 4x4 caso, así que no es una respuesta.

La latina condición se ocupa de las filas y las columnas. Tenemos que demostrar que la mezcla de las filas (resulta que no hay necesidad de reorganización de las columnas) nos permite tener los cuatro números que aparecen en los bloques de 2x2.

Empezar con un cuadrado latino 4x4. Sin pérdida de generalidad (reproducción aleatoria de los números), podemos suponer que la 1ª fila es 1234. Veamos las dos primeras columnas. Además de tener un 1 y un 2 en la primera fila hay exactamente uno más de 1 y más de 2 en algunas otras filas. Por lo tanto, hay al menos una fila tal que ni el 1 ni el 2 aparece en las dos primeras columnas. En otras palabras, al menos una de las otras filas tiene un 3 y un 4 (en orden) como las dos primeras entradas.

Nos deja el intercambio de las filas de la latina, la plaza mínimamente en forma tal que una fila comenzando con 34 (43) becoms la segunda fila. Una sola swap es suficiente para lograr este objetivo. En este punto de la parte superior izquierda de 2x2 bloque se ha tomado cuidado de. Pero el latín de la propiedad implica entonces que las cuatro entradas en la parte superior derecha e inferior izquierda de 2x2 bloques son todas diferentes. La repetición de la dosis muestra que el mismo tiene para la parte inferior derecha de 2x2 bloque.

Permuting filas no va a cambiar la latina de la propiedad, por lo que las reglas de sudoku en las filas/columnas están siendo observados.