Resolva o Sudoku com o algoritmo X

Neste artigo, consideramos o "Algoritmo X" de Knuth e sua aplicação para resolver o sudoku. A beleza do algoritmo é que o sudoku é resolvido rapidamente sem programar nenhuma técnica avançada de solução.

Tudo começou, de fato, com as tarefas do Projeto Euler , onde obter a resposta, você precisa resolver 50 sudoku. E parece que ele recebeu uma resposta escrevendo um programa para resolver uma pesquisa bastante estúpida, mas de alguma forma havia alguma insatisfação com a velocidade da solução. Depois de ver como as pessoas normais resolvem o sudoku, descobri que o Algoritmo X, inventado por Donald Knut, está sendo usado para isso.

Algoritmo X

Este algoritmo resolve o problema de cobrir com precisão o conjunto. Ou, se desejar, ele coleta um "quebra-cabeça discreto", com informações sobre a forma das peças disponíveis. Mais formalmente:

• Existem muitos
• Há um conjunto de subconjuntos Y deste conjunto
• A tarefa é escolher entre Y esses elementos Y * para que cada elemento de S esteja contido em apenas um dos conjuntos incluídos em Y *
• Ou seja, a união de todos os conjuntos em Y * constitui (cobre) o conjunto S e, ao mesmo tempo em Y *, não há conjuntos que se cruzam em pares

Por exemplo, considere os conjuntos
S = {1, 2, 3, 4, 5} e
Y = { A = {1, 2},
B = {2, 3},
C = {1, 5},
D = {1, 4},
E = {5}}
Os conjuntos B , D e E formam uma cobertura exata do conjunto S.

Para o algoritmo X Knuth, o conjunto Y é representado como uma matriz binária, onde as linhas correspondem aos elementos Y , e A _{i, j} = 1, se S _j estiver em Y _i . I.e. para o exemplo acima:

O algoritmo exato de pesquisa de cobertura é o seguinte:

• Dados de entrada: define S e Y ; Stack conjuntos potencialmente incluídos na cobertura (pode estar vazio inicialmente ou já possui alguns elementos)
  
  1. Se o conjunto S estiver vazio, a tampa desejada estará na pilha.
  2. Se o conjunto Y estiver vazio, a cobertura não foi encontrada.
  3. Estamos procurando o elemento s no conjunto S que está incluído no número mínimo de conjuntos em Y.
  4. Escolha entre Y todas as linhas X contendo s .
  5. Para cada conjunto X, repita 6-9.
  6. Adicione X à pilha como um elemento de cobertura em potencial.
  7. Formamos os conjuntos S ' e Y' : S ' é S do qual todos os elementos contidos em X são removidos, Y' são conjuntos de Y que não se cruzam com X.
  8. Chamamos o algoritmo X para S ' , Y' e Stack .
  9. Se foi encontrado na etapa 7 que a cobertura é impossível, remova o elemento da parte superior da Stack e vá para o próximo X. Se uma solução for encontrada, nós a devolvemos.
  10. Se não houver solução para nenhum X , a tarefa não será resolvida para esta entrada.

Em geral, nada de particularmente complicado. Essencialmente - a busca usual em profundidade. A propósito, observamos que, se você definir inicialmente a pilha como não vazia, o problema poderá ser formulado como "encontre a cobertura exata que inclui elementos que já estão na pilha".

A sutileza é que, na prática, esse algoritmo é usado para problemas em que os conjuntos em Y são "pequenos", ou seja, a matriz é muito esparsa, pelo que, por exemplo, procurar interseções entre colunas durante o armazenamento padrão na forma de uma matriz leva um tempo inaceitavelmente longo.
Portanto, Knut complementa esse algoritmo com um mecanismo de "link de dança" . A matriz é representada na forma de uma lista bidimensional duplamente vinculada: para cada linha da lista, apenas os números das colunas são armazenados, onde essa linha contém unidades. A lista também contém links para o elemento seguinte e anterior em uma linha e coluna. Essa organização permite remover colunas e linhas de uma matriz esparsa durante o tempo O (1) comparado a O ( m * n ) quando armazenado em uma matriz bidimensional.

É interessante que Ali Assaf ofereça uma alternativa ao mecanismo de links de dança usando listas associativas, o que permite implementar o algoritmo X em literalmente várias dezenas de linhas em linguagens de alto nível.

A idéia é armazenar colunas e linhas de matriz em listas associativas. Nas colunas, armazenamos índices de linha, na interseção com a qual existem elementos diferentes de zero, em linhas, respectivamente, índices de coluna. Além disso, armazenaremos índices em linhas de maneira ordenada, em uma matriz, observamos que no algoritmo de Knuth, não é essencialmente necessário modificar linhas, portanto, não é necessária a otimização para excluir rapidamente um elemento de uma linha. Mas as colunas serão definidas na forma de conjuntos, porque quando você exclui uma linha de uma matriz, precisa remover o identificador de todas as colunas (e quando a exclui de todas as colunas, a linha desaparece "por si mesma").

Considere a implementação do algoritmo em Julia.
A matriz do exemplo agora ficará assim:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

Para que o algoritmo funcione, você precisa de uma função que retire linhas que se cruzam com a dada da matriz e uma função que retorne essas linhas ao seu lugar.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

Para que essas duas funções funcionassem como deveriam, era necessário apenas o armazenamento ordenado dos elementos nas linhas da matriz. Na função extract_intersects!() , A cada iteração do loop externo, as linhas que se cruzam com base_row mas não contêm elementos visualizados nas iterações anteriores, são removidas da matriz. Isso garante que, quando inserirmos as colunas em restore_intersects!() Na ordem inversa, no loop mais interno no momento do push!(columns[col], added_row) da chamada push!(columns[col], added_row) a columns[col] column columns[col] já será retornada para a matriz e todas serão excluídas em extract_intersects!() elementos das colunas serão retornados ao seu local original.

Agora o próprio algoritmo X:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

Sudoku

Existe um algoritmo, o assunto é pequeno - apresentar o Sudoku como uma tarefa de encontrar a cobertura exata.

Formulamos os requisitos que devem ser atendidos por um sudoku resolvido:

1. Em cada célula existe um número de 1 a 9 (ou até n ² se quadrados de um tamanho diferente forem resolvidos).
2. Em cada linha, cada número ocorre uma vez.
3. Em cada coluna, cada número ocorre uma vez.
4. Em cada quadrante, cada número ocorre uma vez.

Cada um desses requisitos deve ser cumprido exatamente 1 vez, ou seja, eles formam o conjunto que precisa ser coberto. Possui exatamente 4 n ² elementos (colunas na matriz).

Os subconjuntos que consideramos são formados substituindo um número específico em uma célula específica. Por exemplo, o número 9 na interseção de 1 linha e 4 colunas "cobre" um subconjunto "na célula (1,4) é um número, em 1 linha há um número 9, em 4 colunas há um número 9, em 2 quadrantes há um número 9" (implicando o usual Sudoku 9 × 9).

Depois disso, o algoritmo da solução é escrito trivialmente.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

Vamos verificar um exemplo:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

Parece funcionar, e a velocidade é aceitável.

Deve-se notar que nenhuma técnica específica para Sudoku (como, por exemplo, aqui ou aqui ) não foi estabelecida no algoritmo, exceto por uma representação específica do conjunto desejado e dos elementos de cobertura.