Codificação eficiente de quebra-cabeças sudoku

A especificação de qualquer grade 9x9 arbitrária requer a posição e o valor de cada quadrado. Uma codificação ingênua para isso pode fornecer 81 (x, y, valor) trigêmeos, exigindo 4 bits para cada x, y e valor (1-9 = 9 valores = 4 bits) para um total de 81x4x3 = 972 bits. Ao numerar cada quadrado, é possível reduzir as informações posicionais para 7 bits, diminuindo um pouco para cada quadrado e um total de 891 bits. Ao especificar uma ordem predeterminada, pode-se reduzir drasticamente isso para apenas os 4 bits de cada valor, totalizando 324 bits. No entanto, um sudoku pode ter números ausentes. Isso fornece o potencial de reduzir o número de números que precisam ser especificados, mas pode exigir bits adicionais para indicar posições. Usando nossa codificação de 11 bits de (posição, valor), podemos especificar um quebra-cabeça com pistas com$n$$11n$ bits, por exemplo, um quebra-cabeça mínimo (17) requer 187 bits. A melhor codificação que eu pensei até agora é usar um bit para cada espaço para indicar se ele está preenchido e, se houver, os 4 bits a seguir codificam o número. Isso requer bits, 149 para um quebra-cabeça mínimo ( ). Existe uma codificação mais eficiente, preferencialmente sem um banco de dados de cada configuração válida do sudoku? (Pontos de bônus por abordar um geral do quebra-cabeça )$81+4n$$n=17$$n$$N \times N$

Apenas me ocorreu que muitos quebra-cabeças serão uma rotação de outro ou terão uma permutação simples de dígitos. Talvez isso ajude a reduzir os bits necessários.

Segundo a Wikipedia ,

O número de grades de solução 9 × 9 Sudoku clássicas é 6.670.903.752.021.072.936.960 (sequência A107739 em OEIS) ou aproximadamente .$6.67×10^{21}$

Se eu fiz minha matemática corretamente ( ), isso resulta em 73 (72,498) bits de informações para uma tabela de pesquisa.$\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$

Mas:

O número de soluções essencialmente diferentes, quando são consideradas simetrias como rotação, reflexão, permutação e nova rotulagem, mostrou ser apenas 5.472.730.538 [15] (sequência A109741 em OEIS).

Isso fornece 33 (32,35) bits, portanto, é possível que um método inteligente de indicar qual permutação usar possa ficar abaixo dos 73 bits completos.

Existe uma codificação mais eficiente, preferencialmente sem um banco de dados de cada configuração válida do sudoku?

Sim. Posso pensar em uma codificação melhorando sua codificação de 149 bits de um quebra-cabeça mínimo de em 6 ou 9 bits, dependendo de uma condição. Isto é , sem uma base de dados ou qualquer registo de outras soluções ou placas parciais. Aqui vai:$9\times 9$

Primeiro, você usa bits para codificar um número m com um número mínimo de aparências no quadro. Os próximos 4 bits codificam o número real ℓ de vezes que m aparece. Os próximos 7 l bits de codificar cada uma das posições em que m aparece.$4$$m$$4$$\ell$$m$$7\ell$$m$

Os seguintes bits são sinalizadores indicando se as posições restantes têm um número ou não (você apenas pula as posições em que m está). Sempre que um desses bits estiver , os próximos 3 bits indicarão qual é o número (no conjunto ordenado { 1 , … , 9 } sem m ). Por exemplo, se m = 4 e os 3 bits forem , o número na posição correspondente no quadro é o quinto (contando de 0) no conjunto { 1 , 2 , 3 $81-\ell$$m$1$\{1,\ldots,9\}$$m$$m=4$101 , então é 6 . Os números j < m serão codificados em binário como j - 1 , enquanto os números j > m serão codificados como j - 2 . Como já tínhamos escritoposições ℓ , apenas 3 ( n - ℓ ) bits serão adicionados para codificar o restante da placa nesta etapa.$\{1,2,3,5,6,7,8,9\}$$6$$j<m$$j-1$$j>m$$j-2$$\ell$$3(n-\ell)$

Assim, o número total de bits necessários para codificar uma placa usando este procedimento é

Para , nota-se que ℓ pode ser 0 ou 1 (de um modo geral, ℓ ≤ ⌊ n / 9 ⌋ ). Portanto, B pode ser 140 ou 143, dependendo de um número não aparecer no quadro.$n=17$$\ell$$\ell\leq\lfloor n/9\rfloor$$B$

Vale ressaltar que a solução de Kevin é muito melhor no caso geral. Essa codificação usa no máximo 149 bits apenas para ou para n = 20, desde que ℓ = 0 . Pelo menos, mostra uma idéia geral de como tirar proveito do fato de que N = 9 está muito próximo de 2 ⌊ log 2 N ⌋ (o que significa que tendemos a "perder memória" usando 4 bits por valor, pois 4 bits permitem nós expressamos N = 16 números também.$n\in\{17,18,19\}$$n=20$$\ell=0$$N=9$$2^{\lfloor\log_2N\rfloor}$$N=16$

Exemplo. Considere o quadro a seguir com pistas.$n=17$

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

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

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

Aqui, nenhum número não aparece no quadro e os números 6, 7 e 9 aparecem apenas uma vez. Tomamos ( ) e ℓ = 1 ( ). Lendo as posições da esquerda para a direita e depois de cima para baixo, m aparece na posição 36 ( ). Assim, nossa codificação começa com .$m=7$0111$\ell=1$0001$m$$36$0100100011100010100100

Em seguida, precisamos de sete 0s, um 1e a codificação de 3 bits do número , depois um seguido pela codificação de ae 3 bits de 4 etc. ( ). Eventualmente, pularemos a posição em que m = 7 está e codificaremos 8 como (o sexto número contando de 0 na lista 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 ) e 9 como . A codificação completa é a seguinte:$1$01$4$0000000100101100$m=7$110${1,2,3,4,5,6,8,9}$111

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

A codificação completa é 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, e o leitor pode verificar se o comprimento dessa string é de fato 143 :-)