Qual é o número mínimo de bits necessário para armazenar um quebra-cabeça sudoku?

28

Nota: trata-se do quebra-cabeça padrão do sudoku 9x9. A solução precisa apenas suportar quebra-cabeças legais resolvidos . Portanto, uma solução não precisa suportar células vazias e pode confiar nas propriedades de um quebra-cabeça sudoku resolvido.

Eu estava pensando isso, mas não conseguia pensar em uma resposta com a qual me contentasse. Uma solução ingênua usaria um byte para cada célula (81 células), totalizando 648 bits. Uma solução mais sofisticada armazenaria todo o quebra-cabeça do sudoku em um número de base 9 (um dígito por célula) e exigiria bits.log2(981))=257

Mas ainda pode ser aprimorado, por exemplo, se você souber 8 dos 9 números em uma sub-grade 3x3, poderá deduzir trivialmente o 9º. Você pode continuar com esses pensamentos até o ponto em que essa pergunta se resume a Qual é a quantidade de sudokus resolvidos únicos? Agora você pode usar uma enorme tabela de pesquisa que mapeia cada número binário para um quebra-cabeça sudoku, mas isso não seria uma solução utilizável.

Então, minha pergunta:

Sem usar uma tabela de pesquisa, qual é a quantidade mínima de bits necessária para armazenar um quebra-cabeça sudoku e com qual algoritmo?

orlp
fonte
3
Existe realmente uma diferença qualitativa entre deixar de fora o nono número em uma 3x3, linha ou coluna e apenas armazenar o sudoku mínimo com espaços vazios que tenham essa solução única? "não precisa suportar células vazias" é um arenque vermelho se a solução ideal necessariamente precisa.
Wooble 9/09/11
19
Como existem sudoku resolvidos 6,67 × 10 ^ 21 (“QSCGZ” 2003; Felgenhauer e Jarvis 2005) e log_2 (6,67 × 10 ^ 21) = 72,4…, um limite inferior é de 73 bits (mesmo se você usar a enorme pesquisa de tabela) . Se você não precisar distinguir soluções essencialmente idênticas em termos de simetria, esse limite inferior não se aplicará.
Tsuyoshi Ito
9
Essa pergunta seria um bom concurso de programação.
Peter Shor
1
O limite inferior análogo para soluções essencialmente idênticas é de 33 bits.
Charles
3
Por que você precisa de uma tabela de consulta? Você pode apenas enumerar as soluções Sudoku uma a uma até atingir o número desejado.
Zirui Wang

Respostas:

19

Na mesma linha da resposta da catraca, se você preencher as células não estreladas na matriz a seguir, uma caixa 3x3 de cada vez, sempre escolhendo a próxima caixa a ser preenchida por uma que compartilhe linhas ou colunas com uma caixa que você já preenchido, você obtém um padrão como o seguinte para o número de opções por etapa (preenchendo a caixa do meio superior primeiro, a caixa do canto superior direito, etc.).

Em cada caixa 3x3 após a primeira, depois de preencher uma linha ou coluna da caixa, três dos seis dígitos restantes são localizados em uma única linha. Escolha seus locais primeiro e preencha as três células restantes. (Portanto, a ordem real de quais células preencher pode variar dependendo do que você já sabe, mas o número de opções nunca é maior do que o que mostrei.)

Depois de preencher essas células, todas as estrelas são determinadas.

* * * 9 8 7 6 5 4
* * * 6 5 4 3 3 2
* * * 3 2 1 3 2 1

6 5 4 * * * 6 3 3
3 3 2 * * * 5 3 2
3 2 1 * * * 4 2 1

6 3 3 6 5 4 * * *
5 3 2 3 3 2 * * *
4 2 1 3 2 1 * * *

Se eu calculei corretamente, isso fornece 87 bits. Há algumas economias adicionais a serem obtidas no último bloco 3x3, de acordo com o comentário de Peter Shor: todo valor é localizado em uma das quatro células e cada linha contém pelo menos uma célula com apenas quatro valores possíveis, portanto, certamente os fatores nesse O bloco deve começar com 4 e não 6, mas não entendo os fatores restantes na resposta de Shor.

David Eppstein
fonte
4
Você pode reduzir o número de opções ao preencher a sexta caixa 3x3 também. Esta caixa se torna 4,3,2 / 3,2,1 / 2,1,1 para um total de 83 bits, se eu a calculei corretamente.
Peter Shor
@ Peter - não. Os três números à direita podem ser os mesmos que os acima. Você não sabe que todos eles são distintos. Os números únicos mais garantidos são 3, portanto, a primeira caixa é uma escolha entre seis itens. (Este local é um exemplo É verdade para os outros também..)
Hogan
@ David - passando pelo meu comentário a Peter, eu não acho que seus números estão errados. Na 2ª caixa, 6 5 4 4 3 2 3 2 1acredito que seja 6 5 4 6 5 4 3 2 1o pior caso.
Hogan
Hogan, não, veja a parte na minha resposta sobre "depois de preencher uma linha ou coluna da caixa, você sempre poderá escolher a próxima linha ou coluna a ser preenchida para aquela em que haja no máximo quatro valores possíveis "
David Eppstein
@ David - Vamos rotular os 3 x 3s 1,1 1,2 1,3 indo da esquerda para a direita, de cima para baixo. Vamos rotular os Quadrados A - Eu vou da esquerda para a direita, de cima para baixo. A localização D em 1,3 conhece 3 números no 3x3 em que está (A, B, C) e conhece 3 números em 1,2 (D, E, F), mas não sabe que esses 6 números são diferentes. Eles podem ser os mesmos três números das casas 3,1 e 2,1, portanto, existem no máximo 6 opções.
Hogan
13

continuando com a resposta de @ Peter, aqui está uma lista de piores possibilidades para cada célula, à medida que você a preenche a partir do canto superior esquerdo

9   8   7       6   5   4       3   2   1
6   5   4       6   5   4       3   2   1
3   2   1       3   2   1       3   2   1

6   6   3       6   5   4       3   2   1
5   5   2       5   5   3       3   2   1
4   4   1       4   2   1       3   2   1

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1

isso contribui para 4.24559E + 29 posibilidades ou 99 bits

editar: esqueceu que o último quadrado é totalmente determinado por todos os outros

catraca arrepiante
fonte
Muito agradável!! Permitam-me acrescentar que não está claro para mim que você poderia alcançar essas possibilidades de pior caso para uma solução real de Sudoku (especialmente se você usar um algoritmo sofisticado que usa algumas técnicas de Sudoku para restringir as possibilidades pelas quais os números podem ir em uma célula )
Peter Shor
@ Peter, mas você precisa adicionar os que se estreitam em en e decodificação e percebi que, se você tiver que escolher um e não corrigir a ordem (a maneira mais fácil, mas não realmente ótima), será necessário adicionar isso também à codificação
ratchet freak
Não, se você usar o mesmo algoritmo para descobrir a melhor célula no procedimento de decodificação e codificação, ela fornecerá a mesma célula (já que está trabalhando nos mesmos dados), para que os procedimentos de codificação e decodificação sejam sincronizados, e você não precisa adicionar o pedido à codificação. Essa idéia também faz o algoritmo de compactação de dados LZW funcionar.
Peter Shor
Eu acho que os bits mínimos necessários para armazenar um quebra-cabeça de sudoku válido não são uma função computável (Kolmogorov). No entanto, os 103 bits de Peter / catraca parecem um bom limite.
Marzio De Biasi
2
@Vor: Tecnicamente, a máquina de Turing que gera o número correto de bits quando recebe um quebra-cabeça sudoku, pois a entrada é finita porque o conjunto de entradas é finito; portanto, "quantos bits são necessários para descrever esse quebra-cabeça" é "trivialmente" computável. Estou dizendo que realmente poderíamos encontrar uma máquina de Turing explicitamente (em princípio, os cálculos levariam muito tempo), porque não pode ser mais difícil do que calcular um prefixo finito de um número Omega.
Aaron Sterling
5

Você não precisa de uma tabela de consulta completa para obter uma compressibilidade ideal. Acredito que os computadores modernos que usam uma tabela de consulta bastante razoável possam contar o número de Sudokus restritos , que são Sudokus com alguns dígitos já existentes. Usando isso, veja como você codifica (a decodificação é semelhante).

Corrija uma ordem dos quadrados. Suponha que o número no primeiro quadrado seja . Coloque N 1 como o número de Sudokus cujo primeiro quadrado é menor que d 1 . Seja agora d 2 o número do segundo quadrado. Coloque N 2 como o número de Sudokus cujo primeiro quadrado é d 1 e cujo segundo quadrado é menor que d 2 . E assim por diante. O número codificado é N = Σ i N i .d1N1d1d2N2d1d2N=iNi

Este método de codificação é conhecido como codificação binomial na literatura. Isso deve permitir que você efetivamente (no sentido do mundo real) calcule o índice de qualquer Sudoku e vice-versa. Você precisará de apenas bits, conforme mencionado acima (isso significa que você pode codificar vários deles com esse número médio de bits).72.4

Edit: A página da Wikipedia sobre matemática do Sudoku nos ajuda a esclarecer a imagem. Também é útil uma tabela compilada por Ed Russell .

Acontece que, se você considerar apenas as três principais linhas, haverá essencialmente apenas 44 configurações diferentes a serem consideradas. Na tabela, você pode encontrar o número total de configurações equivalente a qualquer uma delas (assumindo que a linha superior seja 123456789) e o número total de conclusões de cada uma. Dado um Sudoku, eis como calcularíamos seu número ordinal:

  1. Normalize a configuração para que sua linha superior seja 123456789.
  2. Descubra a quais das 44 configurações diferentes ela pertence. O artigo da Wikipedia fornece um algoritmo para isso. A tabela lista o número de classes de equivalência para cada configuração, bem como o número de conclusões.
  3. Determine o número ordinal da configuração das três principais linhas dentro de sua classe de equivalência. Isso pode ser feito de duas maneiras: usando uma lista de toda a classe de equivalência (existem 36288 no total em todas as classes de equivalência) ou encontrando uma maneira de enumerar rapidamente todas elas.
  4. Normalize as linhas restantes classificando as linhas 4-6 e 7-9 pela primeira coluna e, em seguida, classificando esses dois blocos de linhas de maneira arbitrária. Isso reduz o número de conclusões por um fator de 72.
  5. 220
  6. ijkCi,DiCi+jDi+k9!72

Este procedimento é reversível e gerará um Sudoku a partir de um número ordinal. Observe que a enumeração do Sudoku foi reduzida para alguns minutos (em 2006; veja a página de discussão do artigo da Wikipedia) ou menos; portanto, espero que em um computador moderno essa abordagem seja muito prática e demore alguns segundos ou menos.

Yuval Filmus
fonte
2
É possível contar as soluções para o sudoku restrito de forma eficiente? É # P-completo se você generalizar o tamanho e permitir espaços em branco em locais arbitrários.
Tsuyoshi Ito
2
Como mencionei na minha resposta, a codificação aritmética alcançará uma compressão quase ideal para esse cenário.
Peter Shor
1
Você pode estar certo, mas sua afirmação implica que o número de grades de sudoku (6,67 × 10 ^ 21) é fácil de calcular em um computador moderno. É realmente possível calcular, mas é fácil?
Tsuyoshi Ito 12/09
2
Tive essa impressão de um dos papéis que descrevem como fazer o cálculo. Você pode até calcular alguns dos dados "mais pesados" no pré-processamento e armazená-los em uma tabela de tamanho razoável - os ganhos de velocidade podem ser dramáticos. Tanto quanto me lembro, levaram apenas algumas horas, e isso há alguns anos atrás. Agora, suponha que você use uma tabela para torná-la 1000 vezes mais rápida. Além disso, em cada estágio, os números diminuem exponencialmente; portanto, a maior parte do trabalho provavelmente está concentrada no primeiro estágio.
Yuval Filmus
1
@tsuyoshi Acredito que exista alguma versão / extensão dos BDDs que torne o cálculo relativamente simples - eu precisaria fazer um pouco de pesquisa, mas sei que eles foram usados ​​para alguns problemas de contagem combinatória bastante complicados.
Steven Stadnicki 15/09/11
4

Aqui está um algoritmo que eu suspeito que produzirá uma codificação muito boa. Você tem o sudoku finalizado que deseja compactar e digamos que já codificou algumas células dele, então há um sudoku parcial (não necessariamente com uma solução exclusiva) com algumas células preenchidas.

Use um algoritmo fixo para contar quantos números podem ser colocados em cada célula vazia. Encontre a primeira célula lexicograficamente na qual o menor número de números diferentes pode ser colocado e codifique qual desses números entra nela (portanto, se uma célula puder conter apenas 3, 7 ou 9, os 3 serão codificados por "0 ", o 7 por" 1 "e o 9 por" 2 "). Codifique a sequência resultante usando codificação aritmética (que leva em consideração o número de números possíveis que uma célula pode conter).

Não sei quanto tempo durará a sequência binária resultante, mas suspeito que seja muito curta, especialmente se o seu algoritmo para contar quantos números podem ser colocados em uma célula for razoavelmente sofisticado.

Se você tivesse um bom algoritmo que estimasse a probabilidade de cada célula contendo um determinado número, poderia fazer ainda melhor.

Peter Shor
fonte
3

Comentários e críticas são bem-vindos

69.96171.72

1.) Armazenar o quebra-cabeça implica armazenar a solução (informações teoricamente).

t(α)α2t(α)αt(3) =2.444443

Pα4t(α)α2

Mβ×α4β2t(α)α22t(α)α2{0,±1}β=kt(α)α2k

V=MPβ|α2|M{0,±1}

Vβlogα2=2kt(α)α2logα

α=3t(α) =32kt(α)α2logα=69.96k85.86kk=2139.92171.72bits

MP

A.)k2t(α)1

B.)t(α)t(α)kt(α)α4Ct(α)α2α4(3α21)Ct(α)α23t(α)

t(α)α2

C.)k

D.) VVO((Vmax))=O(|α2|)2βlogα2=2kt(α)α2logα

2k2A.)B.)C.)D.)8973

vs
fonte
1

Isso é para relatar uma implementação da codificação compacta completa do sudoku (semelhante à sugestão de Zurui Wang 14/09/11).

A entrada é a linha superior e os 3 primeiros dígitos da 2ª linha. Estes são reduzidos para 1-9! e 1-120 e combinados com <= 4,4x10 ^ 7. Eles são usados ​​como dados para contar lexicograficamente todos os sukokus parciais de 30 dígitos até a sequência correspondente. A contagem final até os 81 dígitos inteiros é feita da mesma maneira. Essas três sequências são armazenadas como números inteiros de 32 bits, com no máximo 26 bits, para que possam ser compactadas ainda mais. Todo o processo leva cerca de 3 minutos, com os primeiros 30 dígitos levando a maior parte do tempo. A decodificação é semelhante - exceto as contagens correspondentes, em vez do sudokus.

Em breve - a revisão inclui os 3 primeiros dígitos da 2ª linha na enumeração de 30 dígitos (código de 2 bits), comparações com a enumeração Jarvis (Jscott, 3/1615)

jscott
fonte
1
FYI: Se você criou duas contas e gostaria de mesclá-las, consulte cstheory.stackexchange.com/help/merging-accounts
DW
0

Eu iria com a seguinte análise simples:

Cada valor pode ser armazenado em 4 bits (varia de 1 a 9, esses três bits permitem até 0 a 16)

9×9=81

8×8

Eu acho que eu poderia reduzi-lo para:

b=log2(v)(n1)

Onde

v

n

Edit: Neo Style: Conheço Latex.

Alfa
fonte
-2

Esse número é diferente para cada Sudoku. Uma das regras do Sudoku é que ele tem exatamente uma solução.

Portanto, se você olhar um exemplo, é a quantidade mínima de dados que você deve armazenar.

Se você trabalha do lado oposto, pode remover dígito por dígito e executar um solucionador no resultado para ver se ele ainda possui exatamente uma solução. Nesse caso, você pode excluir outro dígito. Caso contrário, você deve restaurar esse dígito e tentar outro. Se você não pode, você encontrou um mínimo.

Como a maioria dos quebra-cabeças começa quase vazia, uma codificação de duração da execução provavelmente produzirá bons resultados.

Aaron Digulla
fonte
Essa abordagem gananciosa não atinge necessariamente o mínimo, talvez você precise selecionar cuidadosamente qual dígito remover em cada etapa.
Diego de Estrada
É apenas um exemplo. Google para "geradores de quebra-cabeça sudoku" para obter mais sofisticados.
Aaron Digulla 9/09/11
5
Realmente não vejo por que você esperaria que isso funcionasse particularmente bem. Parece apenas um instinto, e não uma resposta.
Joe Fitzsimons