Código de Sudoku

Los códigos Sudoku son códigos de corrección de errores hacia adelante no lineales que siguen las reglas de los rompecabezas Sudoku y están diseñados para un canal de borrado . Según este modelo, el transmisor envía una secuencia con todos los símbolos de un Sudoku resuelto. El receptor recibe un símbolo correctamente o un símbolo de borrado para indicar que no se recibió. El decodificador obtiene una matriz con entradas faltantes y utiliza las restricciones de los rompecabezas Sudoku para reconstruir una cantidad limitada de símbolos borrados.

Los códigos de Sudoku no son adecuados para uso práctico, pero son objeto de investigación. Cuestiones como la tasa y el rendimiento de error aún se desconocen para dimensiones generales. ^{[ 1 ]}

En un sudoku, se puede encontrar información faltante utilizando diferentes técnicas para reproducir el rompecabezas completo. Este método puede considerarse como la decodificación de un mensaje codificado de sudoku enviado a través de un canal de borrado donde algunos símbolos se han eliminado. Mediante las reglas del sudoku, el decodificador puede recuperar la información faltante. Los sudokus pueden modelarse como un modelo gráfico probabilístico y, por lo tanto, se pueden utilizar métodos de decodificación de códigos de verificación de paridad de baja densidad, como la propagación de creencias .

En el modelo de canal de borrado, un símbolo se transmite correctamente con probabilidad${\displaystyle 1-p_{e}}$o se borra con probabilidad${\displaystyle p_{e}}$(véase la figura \ref{fig:Sudoku3x3channel}). El canal no introduce errores, es decir, ninguna entrada del canal se cambia a otro símbolo. El ejemplo de la figura \ref{fig:Sudoku3x3BSC} muestra la transmisión de un${\displaystyle 3\times 3}$Código de Sudoku. Cinco de los nueve símbolos fueron borrados por el canal. El decodificador aún puede reconstruir el mensaje, es decir, el rompecabezas completo.

Tenga en cuenta que los símbolos enviados a través del canal no son binarios. Para un canal binario, los símbolos (por ejemplo, enteros)${\displaystyle \{1,\ldots ,9\}}$) deben ser mapeados a base 2. Sin embargo, el modelo de canal de borrado binario no es aplicable porque borra solo bits individuales con cierta probabilidad y no símbolos de Sudoku. Si los símbolos del Sudoku se envían en paquetes, el canal puede describirse como un modelo de canal de borrado de paquetes .

Un sudoku es un${\displaystyle N\times N}$Rompecabezas de colocación de números. Se completa de tal manera que en cada columna, fila y subcuadrícula N símbolos distintos aparecen exactamente una vez. El alfabeto típico es el conjunto de los números enteros.${\displaystyle \{1,\ldots ,N\}}$. El tamaño de las subcuadrículas limita el tamaño de los SUDOKU a${\displaystyle N=n^{2}}$con${\displaystyle n\in \mathrm {N}}$Cada sudoku resuelto y cada una de sus subcuadrículas es un cuadrado latino , lo que significa que cada símbolo aparece exactamente una vez en cada fila y columna. En el punto de partida (en este caso, después del canal de borrado), el rompecabezas está solo parcialmente completo, pero tiene una única solución.

Para los códigos de canal también son concebibles otras variedades de sudokus. Se pueden utilizar regiones diagonales en lugar de subcuadrículas cuadradas para investigaciones de rendimiento. ^{[ 2 ]} El sudoku diagonal tiene la ventaja de que su tamaño se puede elegir con mayor libertad. Debido a la estructura de subcuadrícula, los sudokus normales solo pueden tener un tamaño de n², mientras que los sudokus diagonales tienen soluciones válidas para todos los impares.${\displaystyle N}$. ^{[ 2 ]}

Los códigos de Sudoku no son lineales. En un código lineal, cualquier combinación lineal de palabras clave da como resultado una nueva palabra clave válida; esto no se cumple para los códigos de Sudoku. Los símbolos de un Sudoku pertenecen a un alfabeto finito (por ejemplo, números enteros).${\displaystyle \{1,\ldots ,9\}}$Las restricciones de los códigos de Sudoku no son lineales: todos los símbolos dentro de una restricción (fila, línea, subcuadrícula) deben ser diferentes de cualquier otro símbolo dentro de esa restricción. Por lo tanto, no existe una palabra clave compuesta únicamente por ceros en los códigos de Sudoku.

Los códigos de Sudoku pueden representarse mediante un modelo gráfico probabilístico en el que adoptan la forma de un código de verificación de paridad de baja densidad . ^{[ 3 ]}

Existen varios métodos posibles para decodificar los códigos de Sudoku. Algunos algoritmos son desarrollos muy específicos para los códigos de Sudoku. Varios métodos se describen en los algoritmos para resolver Sudoku . Otro método eficiente es el de los enlaces danzantes .

Los métodos de decodificación como la propagación de creencias también se utilizan para códigos de verificación de paridad de baja densidad y son de especial interés. El análisis del rendimiento de estos métodos en códigos de sudoku puede ayudar a comprender mejor los problemas de decodificación para códigos de verificación de paridad de baja densidad. ^{[ 3 ]}

Al modelar los códigos de Sudoku como un modelo gráfico probabilístico, se puede utilizar la propagación de creencias para dichos códigos. La propagación de creencias en el grafo de Tanner o en el grafo factorial para decodificar códigos de Sudoku se analiza en Sayir ^{[ 1 ]} y Moon ^{[ 4 ]} . Este método fue diseñado originalmente para códigos de verificación de paridad de baja densidad. Debido a su generalidad, la propagación de creencias funciona no solo con los códigos clásicos.${\displaystyle 9\times 9}$Sudoku, pero con una variedad de ellos. La decodificación LDPC es un caso de uso común para la propagación de creencias; con ligeras modificaciones, este enfoque puede utilizarse para resolver códigos de Sudoku. ^{[ 4 ]}

La satisfacción de las restricciones mediante un grafo de Tanner se muestra en la figura de la derecha.${\displaystyle S_{n}}$Indica las entradas del sudoku en orden de escaneo de filas.${\displaystyle C_{m}}$denota las funciones de restricción:${\displaystyle m=1,...,9}$asociado con filas,${\displaystyle m=10,...,18}$asociado con columnas y${\displaystyle m=19,...,27}$asociado con el${\displaystyle 3\times 3}$subcuadrículas del Sudoku.${\displaystyle C_{m}}$se define como

${\displaystyle C_{m}(s_{1},s_{2},.....,s_{9})={\begin{cases}1,&{\text{si }}s_{1},s_{2},...,s_{9}{\text{ son distintos}}\\0,&{\text{en otro caso.}}\end{cases}}}$^{[ 4 ]}

Cada célula${\displaystyle S_{n}}$está conectado a 3 restricciones: las restricciones de fila, columna y subcuadrícula. Sayir sugiere una especificación del enfoque general para la propagación de creencias: ^{[ 1 ]} La probabilidad inicial de un símbolo recibido es 1 para el símbolo observado y 0 para todos los demás o uniformemente distribuida en todo el alfabeto si el símbolo se borra. Para el algoritmo de propagación de creencias es suficiente transmitir solo un subconjunto de posibilidades en lugar de distribuciones, ya que la distribución siempre es uniforme sobre el subconjunto. Los candidatos para los símbolos borrados se reducen a un subconjunto del alfabeto a medida que los símbolos se excluyen debido a las restricciones. Todos los valores que son utilizados por otra celda en la restricción, y pares que son compartidos entre otras dos celdas, etc., se eliminan. Los jugadores de Sudoku utilizan este método de exclusión lógica para resolver la mayoría de los rompecabezas de Sudoku.

El objetivo de los códigos de corrección de errores es codificar los datos de tal manera que sean más resistentes a los errores en el proceso de transmisión. El codificador tiene que mapear los datos.${\displaystyle U}$a una cuadrícula de sudoku válida de la cual la palabra clave${\displaystyle X}$¿Podemos tomar, por ejemplo, en orden de escaneo de filas?

$${\displaystyle U=00101\ldots {\stackrel {\text{Codificador}}{\longrightarrow }}{\begin{array}{|c|c|c|}\hline 1&2&3\\\hline 2&3&1\\\hline 3&1&2\\\hline \end{array}}\Rightarrow X=1,2,3,1,2,1,3,1,2}$$

Muestra los pasos necesarios.

Un estándar${\displaystyle 9\times 9}$El sudoku tiene aproximadamente 72,5 bits de información, como se calcula en la siguiente sección. La información después de Shannon es el grado de aleatoriedad en un conjunto de datos. Un lanzamiento de moneda ideal, por ejemplo, tiene una información de${\displaystyle I=\log _{2}2=1}$bit. Para representar el resultado de 72 lanzamientos de moneda se necesitan 72 bits. Un Sudoku contiene aproximadamente la misma información que 72 lanzamientos de moneda o una secuencia de 72 bits. Una secuencia de 81 símbolos aleatorios${\displaystyle \{1,\ldots ,9\}}$tiene${\displaystyle I=81\log _{2}9\approx 256.8}$bits de información. Un código de Sudoku puede considerarse como 72,5 bits de información y 184,3 bits de redundancia. Teóricamente, una cadena de 72 bits se puede mapear a un Sudoku que se envía por el canal como una cadena de 81 símbolos. Sin embargo, no existe una función lineal que mapee una cadena a un código de Sudoku.

Un enfoque de codificación sugerido por Sayir ^{[ 5 ]} es el siguiente:

• Comience con una cuadrícula vacía.
• Realice lo siguiente para todas las entradas de forma secuencial.
• Utilice la propagación de creencias para determinar todos los símbolos válidos para la entrada.
• Si la cardinalidad de símbolos válidos es k>1, entonces convierta la aleatoriedad de origen en un símbolo k-ario y úselo en la celda.

Para un${\displaystyle 4\times 4}$Sudoku La primera entrada se puede llenar con una fuente de cardinalidad 4. En este ejemplo, es 1. Para el resto de esta fila, columna y${\displaystyle 2\times 2}$En la subcuadrícula, este número queda excluido de las posibilidades en el decodificador de propagación de creencias. Para la segunda celda, solo son válidos los números 2, 3 y 4. La fuente debe transformarse en una distribución uniforme entre tres posibilidades y asignarse a los números válidos, y así sucesivamente, hasta que la cuadrícula esté completa.

El cálculo de la tasa de códigos de sudoku no es trivial. Un ejemplo de cálculo de tasa de un${\displaystyle 4\times 4}$El sudoku se muestra arriba. Rellenando línea por línea desde la esquina superior izquierda, solo la primera entrada tiene la máxima información de${\displaystyle \log _{2}4=2}$bits. Cada entrada siguiente no puede ser ninguno de los números utilizados anteriormente, por lo que la información se reduce a${\displaystyle \log _{2}3}$,${\displaystyle \log _{2}2}$y${\displaystyle 0}$para las siguientes entradas, ya que deben ser de los números restantes de la izquierda. En las segundas líneas la información se reduce adicionalmente por la regla de área: celda${\displaystyle 5}$en orden de escaneo de fila solo puede ser un${\displaystyle 3}$o${\displaystyle 4}$a medida que los números${\displaystyle 1}$y${\displaystyle 2}$ya se utilizan en la subcuadrícula. La última fila no contiene ninguna información. Sumando toda la información se obtiene${\displaystyle \log(4*3*2^{5})\approx 8.58}$bits. La tasa en este ejemplo es

$${\displaystyle {\frac {4+3+2*5}{16*4}}\approx 0.27}$$.

El número exacto de cuadrículas de Sudoku posibles según las Matemáticas del Sudoku es${\displaystyle 6.670.903.752.021.072.936.960}$Con la información total de

$${\displaystyle {\begin{aligned}I_{log_{9}}&=\log _{9}6.67*10^{21}\approx 22.87\\I_{log_{2}}&=\log _{2}6.67*10^{21}\approx 72.50\,{\text{bits}}\end{aligned}}}$$

La tasa promedio de un Sudoku estándar es

$${\displaystyle R=I_{9}/9^{2}\approx 0.28}$$.

El número promedio de entradas posibles para una celda es${\displaystyle {\sqrt[{81}]{6.67*10^{21}}}\approx 1.86}$o${\displaystyle \log _{2}{1.86}\approx 0.90\,{\text{bits}}}$de información por celda de Sudoku. Tenga en cuenta que la tasa puede variar entre las palabras clave. ^{[ 5 ]}

Se demostró que el número mínimo de entradas dadas que dan como resultado una solución única es 17. ^{[ 6 ]} En el peor de los casos, tan solo cuatro entradas faltantes pueden dar lugar a soluciones ambiguas. Para un canal de borrado, es muy improbable que 17 transmisiones exitosas sean suficientes para reproducir el rompecabezas. Solo existen alrededor de 50 000 soluciones conocidas con 17 entradas dadas. ^{[ 7 ]}

La evolución de la densidad es un algoritmo de análisis de capacidad desarrollado originalmente para códigos de verificación de paridad de baja densidad en la decodificación por propagación de creencias. ^{[ 8 ]} La evolución de la densidad también se puede aplicar a restricciones de tipo Sudoku. ^{[ 1 ]} Una simplificación importante utilizada en la evolución de la densidad en códigos LDPC es la suficiencia de analizar solo la palabra clave de todos unos. Sin embargo, con las restricciones de Sudoku, esta no es una palabra clave válida. A diferencia de los códigos lineales, la propiedad de equivalencia peso-distancia no se cumple para los códigos no lineales. Por lo tanto, es necesario calcular recursiones de evolución de la densidad para cada posible rompecabezas de Sudoku para obtener un análisis de rendimiento preciso.

Una simplificación propuesta consiste en analizar la distribución de probabilidad de las cardinalidades de los mensajes en lugar de la distribución de probabilidad del mensaje. ^{[ 1 ]} La evolución de la densidad se calcula en los nodos de entrada y en los nodos de restricción (comparar el gráfico de Tanner anterior). En los nodos de entrada se analizan las cardinalidades de las restricciones. Si, por ejemplo, las restricciones tienen las cardinalidades${\displaystyle (1,1)}$entonces la entrada solo puede ser de un símbolo. Si las restricciones tienen cardinalidades${\displaystyle (2,2)}$Entonces ambas restricciones permiten dos símbolos diferentes. Para ambas restricciones, el símbolo correcto está contenido con seguridad; supongamos que el símbolo correcto es${\displaystyle 1}$El otro símbolo puede ser igual o diferente para las restricciones. Si los símbolos son diferentes, se determina el símbolo correcto. Si el segundo símbolo es igual, supongamos que${\displaystyle 2}$Los símbolos de salida son de cardinalidad${\displaystyle 2}$es decir, los símbolos${\displaystyle \left\{1,2\right\}}$. Dependiendo del tamaño del alfabeto (${\displaystyle q}$) la probabilidad de la salida única para las cardinalidades de entrada${\displaystyle (2,2)}$es

$${\displaystyle {\begin{aligned}p_{1}^{(2,2)}=1-{\frac {1}{q-1}}\end{aligned}}}$$

y para una salida de cardinalidad 2

$${\displaystyle {\begin{aligned}p_{2}^{(2,2)}={\frac {1}{q-1}}.\end{aligned}}}$$

Para un estándar${\displaystyle 9\times 9}$Sudoku esto resulta en una probabilidad de${\displaystyle 7/8}$Para obtener una solución única, se realiza un cálculo análogo para todas las combinaciones de cardinalidad. Finalmente, se suman las distribuciones de cardinalidad de salida a partir de los resultados. Cabe destacar que el orden de la cardinalidad de entrada es intercambiable. El cálculo de combinaciones de restricciones no decrecientes es suficiente.

Para los nodos de restricción el procedimiento es algo similar y se describe en el siguiente ejemplo basado en un${\displaystyle 4\times 4}$Sudoku estándar. Las entradas a los nodos de restricción son los posibles símbolos de los nodos de entrada conectados. La cardinalidad 1 significa que el símbolo del nodo fuente ya está determinado. Nuevamente, un análisis no decreciente es suficiente. Supongamos que el valor de salida real es 4 y las entradas tienen cardinalidades${\displaystyle (1,1,2)}$con los símbolos verdaderos 1-2-3. Los mensajes con cardinalidad 1 son${\displaystyle \left\{1\right\}}$y${\displaystyle \left\{2\right\}}$. El mensaje de cardinalidad 2 podría ser${\displaystyle \left\{1,3\right\}}$,${\displaystyle \left\{2,3\right\}}$o${\displaystyle \left\{3,4\right\}}$ya que el símbolo verdadero 3 debe estar contenido. En dos de los tres casos, la salida es el símbolo correcto 4 con cardinalidad 1:${\displaystyle \left\{1\right\}}$,${\displaystyle \left\{2\right\}}$,${\displaystyle \left\{1,3\right\}}$y${\displaystyle \left\{1\right\}}$,${\displaystyle \left\{2\right\}}$,${\displaystyle \left\{2,3\right\}}$En uno de los tres casos, la cardinalidad de salida es 2:${\displaystyle \left\{1\right\}}$,${\displaystyle \left\{2\right\}}$,${\displaystyle \left\{3,4\right\}}$Los símbolos de salida en este caso son:${\displaystyle \left\{3,4\right\}}$. La distribución de cardinalidad de salida final se puede expresar sumando sobre todas las posibles combinaciones de entrada. Para un${\displaystyle 4\times 4}$Sudoku estándar: son 64 combinaciones que se pueden agrupar en 20 no decrecientes. ^{[ 1 ]}

Si la cardinalidad converge a 1, la decodificación está libre de errores. Para encontrar el umbral, la probabilidad de borrado debe incrementarse hasta que el error de decodificación permanezca positivo para cualquier número de iteraciones. Con el método de Sayir ^{[ 1 ],} las recursiones de evolución de densidad pueden utilizarse para calcular umbrales también para códigos de Sudoku hasta un tamaño de alfabeto.${\displaystyle q=8}$.

• Sudoku — Artículo principal sobre Sudoku
• Algoritmos para resolver Sudoku