Codificación eficiente de rompecabezas sudoku

16

Especificar cualquier cuadrícula arbitraria de 9x9 requiere dar la posición y el valor de cada cuadrado. Una codificación ingenua para esto podría dar 81 tripletes (x, y, valor), que requieren 4 bits para cada x, y, y valor (1-9 = 9 valores = 4 bits) para un total de 81x4x3 = 972 bits. Al numerar cada cuadrado, se puede reducir la información posicional a 7 bits, dejando caer un bit por cada cuadrado y un total de 891 bits. Al especificar un orden predeterminado, se puede reducir esto más drásticamente a solo 4 bits para cada valor para un total de 324 bits. Sin embargo, un sudoku puede tener números faltantes. Esto proporciona el potencial para reducir el número de números que deben especificarse, pero puede requerir bits adicionales para indicar posiciones. Usando nuestra codificación de 11 bits de (posición, valor), podemos especificar un rompecabezas con pistas con 11n bits, por ejemplo, un rompecabezas mínimo (17) requiere 187 bits. La mejor codificación que he pensado hasta ahora es usar un bit para cada espacio para indicar si está lleno y, de ser así, los siguientes 4 bits codifican el número. Esto requiere 81 + 4 n bits, 149 para un rompecabezas mínimo ( n = 17 ). ¿Existe una codificación más eficiente, preferiblemente sin una base de datos de cada configuración de sudoku válida? (Puntos de bonificación por abordar un n generaldelrompecabezas N × N )11n81+4nn=17nN×N

Se me ocurrió que muchos acertijos serán una rotación de otro, o tendrán una simple permutación de dígitos. Quizás eso podría ayudar a reducir los bits necesarios.

De acuerdo con Wikipedia ,

El número de rejillas de solución Sudoku 9 × 9 clásicas es 6.670.903.752.021.072.936.960 (secuencia A107739 en OEIS), o aproximadamente .6.67×1021

Si hice mis cálculos correctamente ( ), que sale a 73 (72.498) bits de información para una tabla de búsqueda.ln(6,670,903,752,021,072,936,960)ln(2)

Pero:

Se demostró que el número de soluciones esencialmente diferentes, cuando se tienen en cuenta simetrías como la rotación, la reflexión, la permutación y el reencadenamiento, era solo de 5.472.730.538 [15] (secuencia A109741 en OEIS).

Eso da 33 (32.35) bits, por lo que es posible que un método inteligente para indicar qué permutación usar pueda llegar a estar por debajo de los 73 bits completos.

Kevin
fuente
1
Ja, inicialmente publiqué algunas cosas sin pensar en el problema lo suficiente. Lo he eliminado Gran pregunta!
Patrick87
¿Puedes recordarnos cuántos rompecabezas de Sudoku hay, para que sepamos qué tan grande es la brecha entre estas codificaciones fácilmente decodificables y una enumeración de fuerza bruta?
Gilles 'SO- deja de ser malvado'
Debe poder codificar todas las cuadrículas de , por lo que necesita 73 bits (suponiendo una codificación de longitud fija). Ningún "método inteligente para indicar qué permutación usar" le ayudará con eso. 6.67×1021
svick
@sick Desde el punto de vista de la teoría de la información, creo que debe tener razón, pero no puedo entender de dónde provienen los bits adicionales. Hay permutaciones, que son 19 bits, más 3 para espejo y rotación, por lo que 22 más 33 para rompecabezas únicos, hacen 55; ¿De dónde vienen los otros 18? 9!
Kevin

Respuestas:

5

¿Existe una codificación más eficiente, preferiblemente sin una base de datos de cada configuración de sudoku válida?

Si. Puedo pensar en una codificación que mejore su codificación de 149 bits de un rompecabezas mínimo de en 6 o 9 bits, dependiendo de una condición. Esto es sin una base de datos o cualquier registro de otras soluciones o tableros parciales. Aquí va:9×9

Primero, usa bits para codificar un número m con un número mínimo de apariciones en el tablero. Los siguientes 4 bits codifican el número real de veces que aparece m . Los próximos 7 l bits de codificar cada una de las posiciones en las que m aparece.4m4m7m

Los siguientes bits son banderas que indican si las restantes posiciones tienen un número o no (que acaba de omitir las posiciones en que m es). Siempre que uno de estos bits sea , los siguientes 3 bits indican qué número es (en el conjunto ordenado { 1 , ... , 9 } sin m ). Por ejemplo, si m = 4 y los 3 bits son , entonces el número en la posición correspondiente en el tablero es el quinto (contando desde 0) en el conjunto { 1 , 2 , 3 ,81m1{1,,9}mm=4101 , entonces es 6 . Los números j < m se codificarán en binario como j - 1 , mientras que los números j > m se codificarán como j - 2 . Como ya habíamos escritoposiciones , solose agregarán 3 ( n - ) bits para codificar el resto del tablero en este paso.{1,2,3,5,6,7,8,9}6j<mj1j>mj23(n)

Por lo tanto, el número total de bits necesarios para codificar una placa utilizando este procedimiento es

B=4+4+7+(81)+3(n)=89+3+3n.

Para , notamos que puede ser 0 o 1 (en general, n / 9 ). Por lo tanto, B puede ser 140 o 143 dependiendo de si hay un número que no aparece en el tablero.n=17n/9B

n{17,18,19}n=20=0N=92log2NN=16


n=17

.  .  .   .  .  .   .  1  .
4  .  .   .  .  .   .  .  .
.  2  .   .  .  .   .  .  .

.  .  .   .  5  .   4  .  7
.  .  8   .  .  .   3  .  .
.  .  1   .  9  .   .  .  .

3  .  .   4  .  .   2  .  .
.  5  .   1  .  .   .  .  .
.  .  .   8  .  6   .  .  .

m=70111=10001m360100100011100010100100

0110140000000100101100m=71101,2,3,4,5,6,8,9111

// m=7, l=1 and its position on the board.
011100010100100
// Numbers 1 and 4 at the beginning. Note that 1 is encoded 000, and 4 is 011.
0000000100001011
// Numbers 2 and 5.
0000000001001000000000001100
// Numbers 4 and 8. We skip the appearance of 7 and encode 8 as 110.
010110001110
// 3, 1 and 9. 9 is encoded as 111.
00010100000100001111
// 3, 4, 2, 5, 1, 8, 6 and the last empty cells.
0000101000101100100100011000100000000000111001101000

La codificación completa es 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, y el lector puede verificar que la longitud de esa cadena es de hecho 143 :-)

Janoma
fuente