Em Habré, houve alguns artigos sobre geração de palavras cruzadas. Em um deles,
“As Palavras Cruzadas Mais Complexas Compiladas por um Computador”, foi dito sobre palavras cruzadas muito complexas compostas por um computador, que “precisavam ajudar um pouco” manualmente. O segundo artigo,
“O algoritmo de formação de palavras cruzadas”, fala sobre o algoritmo criado pelo autor para compor palavras cruzadas, e observa que esse “quebra-cabeça mais difícil” permaneceu não conquistado e disse que “talvez esse pico não conquistado inspire alguém a enfrentar outra tempestade!” Bem, você pode aceitar o desafio. O que aconteceu, olhe por baixo do corte.
No começo, darei este jogo de palavras cruzadas mais complicado:
A primeira coisa que você precisa encontrar é uma lista de palavras usadas na compilação deste jogo de palavras cruzadas. Como tal, foram obtidos dois arquivos dos artigos acima - um com palavras em russo e outro com inglês. Então foi necessário resolver a questão principal - qual algoritmo usar para compilar esse jogo de palavras cruzadas. Na verdade, esse jogo de palavras cruzadas não é "complicado" pelo número de palavras, mas pelo número de cruzamentos. É claro que o ataque de força bruta não é adequado aqui, pois levaria muito tempo para examinar todas as opções. No artigo acima mencionado, muitas heurísticas foram consideradas para acelerar o processo de pesquisa; no entanto, esse jogo de palavras cruzadas nunca foi compilado na versão em russo ou em inglês. Você pode continuar criando outras heurísticas para acelerar a solução, mas a maioria delas já foi inventada e implementada nos solucionadores SAT. Portanto, você pode converter a tarefa em um formulário que seja compreensível para os solucionadores SAT e usar um deles.
O que é o solucionador SAT e quais informações ele espera na entrada que considerei no artigo
“Resolvendo o problema de ladrilhos com a ajuda do solucionador SAT usando o exemplo pentamino” . No caso de gerar palavras cruzadas, é necessária uma abordagem ligeiramente diferente para formular o problema de forma conjuntamente normal, que descreverei agora.
A primeira coisa a fazer é classificar todas as palavras da lista em grupos. Cada grupo conterá palavras do mesmo tamanho. Obviamente, para cada palavra na grade de palavras cruzadas, você pode selecionar uma palavra do grupo com o comprimento correspondente. Associamos cada palavra do grupo que pode ser escrita em uma única palavra da grade a uma variável booleana. Essa variável será verdadeira se a palavra especificada do grupo for escrita nessa palavra da grade e, caso contrário, falsa.
Agora, vamos elaborar uma fórmula que descreva nosso problema, ou seja, imporemos restrições a nossas variáveis. Encontre todas as interseções de palavras verticalmente com as palavras horizontalmente. Para cada interseção, determinamos quais pares de palavras são combinados entre si e quais não são. No entanto, surge um problema aqui, uma vez que o número de tais pares pode exceder um milhão para uma interseção. Portanto, usaremos uma abordagem diferente. Classificamos as palavras no grupo que corresponde horizontalmente à palavra por letra, que fica na interseção dessas duas palavras. Faça o mesmo para a palavra verticalmente. Aparentemente, as palavras correspondentes terão a mesma letra no cruzamento. Introduzimos uma variável adicional para cada letra que ocorre em pelo menos uma palavra na horizontal e na vertical. Agora, a condição de as duas palavras serem combinadas entre si é que pelo menos uma dessas variáveis seja verdadeira. Assim, para cada interseção, uma cláusula será adicionada, consistindo em variáveis correspondentes às letras. Agora você precisa associar as variáveis correspondentes a uma letra específica às palavras que contêm essa letra na posição da interseção das palavras. Isso é feito por um conjunto de cláusulas que garantem que as duas variáveis booleanas terão o mesmo valor. E, finalmente, você precisa garantir que não haja palavras idênticas nas palavras cruzadas. Para fazer isso, para cada palavra do banco de dados, adicionamos cláusulas do formulário (não x_i V não x_j), onde x_i é a variável correspondente à sua instância em uma palavra da grade de palavras cruzadas e x_j é a variável correspondente à sua instância em outra palavra da grade de palavras cruzadas.
Gerar esse “quebra-cabeça mais complicado” usando palavras russas leva vários minutos em um Intel 2600K 3,5 GHz com 16 gigabytes de memória. A criação de palavras cruzadas usando palavras em inglês levou cerca de vinte minutos.
Depois disso, tentei outras palavras cruzadas. Por exemplo, consegui compor palavras cruzadas de palavras inglesas e russas na forma de um quadrado de 6 por 6, onde todas as palavras se cruzam.
Em seguida, dou as palavras cruzadas resultantes. Quem quiser pode resolvê-los.
Opção com palavras em russo:1 aeronave de câmera lenta horizontal com nariz abaulado
6 instrumento musical de cordas japonês horizontal
10 Horizontal Na mitologia escandinava, um gigante que emergiu do caos prematuro do abismo do mundo
14 Exílio horizontal do gênero
15 Mineral Horizontal
16 poeta tcheco horizontal (20 c.)
17 Ilha Horizontal no Golfo da Guiné (Guiné Equatorial)
18 boca horizontal, lábios (desatualizados)
19 Ressentimento Horizontal, Raiva
20 Horizontal Apenas um partido político presente
23 maior rio horizontal da Irlanda
24 Roupa de clérigo horizontal
25 Rio Horizontal em Angola e Zaire, afluente esquerdo do rio Kwango
27 Marca horizontal do ônibus húngaro
32 Cidade horizontal e porto na RPDC
35 Sogra horizontal ou sogra
37 Planta horizontal de Solanaceae
38 Horizontal Quem se envolve em cardar lã
41 Nome feminino horizontal (grego bom, gentil)
42 Satélite artificial canadense horizontal
43 Caráter horizontal da ópera de Weber '' Free Shooter ''
44 Cidade horizontal na Eslováquia
46 Gastos horizontais
48 peixes de criação horizontais da família das carpas
50 Horizontal Na mitologia japonesa, a divindade de muitas orelhas de arroz
54 Fósforo cristalino inorgânico horizontal
59 Profeta iraniano horizontal, fundador do maniqueísmo (3 c.)
60 Casas Camponesas Horizontais nas Ilhas das Índias Ocidentais
61 raça horizontal de cães pastor (semelhante a uma raposa)
62 Horizontal (trad.) Estúpido e teimoso tolo
63 Cidade horizontal na região de Orenburg no rio Ural
64 Horizontal Na mitologia grega, um caçador gigante morto por Artemis
65 Cantora e poeta horizontal chilena
66 Horizontal O personagem do teatro folclórico indiano, a imagem de um ator em ruínas, um parasita com um rico patrono
67 Mãe Terra chechena e ingush horizontal
1 Apelido vertical de um dos líderes da revolta popular de 1413 em Paris
2 Sentimento Insatisfeito Vertical
3 paleontologista alemão vertical (1800-1862)
4 Vertical A conquista dos territórios capturados pelos mouros pela população indígena da Península Ibérica
5 Mestre de violão russo vertical
6 Líder militar vertical sueco e russo, general, associado de Pedro I (1667-1717)
7 músico vertical, tocando um instrumento musical
Alto-falante 8 vertical, homem eloquente
9 Vertical Ridge no Japão, Ilha Honshu
Instrumento musical de percussão coreana vertical 10, tambor octogonal
11 Condutor letão vertical (1917-1967)
12 Cordialidade Vertical, Doninha
13 Vertical Na mitologia eslava, o espírito, a personificação da morte
21 gênero de animação vertical que se originou no Japão
22 cátodo da lâmpada de aquecimento com rosca vertical
26 Lago vertical na região de Arkhangelsk
28 rio vertical na Espanha
29 Vertical Pequena floresta de árvores de folha caduca
30 Item Raro Vertical
31 Windmaster belga vertical, inventor do saxofone
32 Moldura pequena vertical
33 Vertical Black
34 Vertical Medida antiga do peso farmacêutico = 62,21 mg
36 Província Vertical em Arábia Saudita
39 Graxa anti-fricção vertical
40 Decoração escultural vertical de capitéis, cornija etc. na forma de caules e folhas estilizados de tal planta
45 Escritor vertical russo, poeta, dramaturgo, roteirista dos filmes de A. Sokurov ('' Moloch '', '' Touro '')
47 Borracha polissulfeto vertical, um tipo de borracha sintética
49 Patologista inglês vertical (Prêmio Nobel 1945)
51 Vertical Na mitologia muçulmana, um gênio com poder especial
52 grito de ganso vertical
53 Vertical Nome feminino (nome grego da deusa da vida pacífica; paz)
54 Grão-mestre de xadrez vertical
55 Vertical Grupo historicamente formado da humanidade, unido por uma origem comum
56 Híbrido vertical de cruzar um camelo de uma só corcova (Dromedar) com uma de duas corcovas (Bactriana), Nar
57 Valor mecânico vertical causando aceleração
58 Escritor japonês vertical (1909-1989, `` Notas do prisioneiro '', `` Luzes no campo '', `` Batalha em Leyte '')
Opção com palavras em inglês:1 Horizontal Um lugar que atrai muitos visitantes
6 Horizontal Qualquer um dos vários peixes da família Carangidae
10 Horizontal Conjunto de fatos dos quais se podem tirar conclusões
14 Nintu Horizontal)
15 Cobertura horizontal do corpo de um animal vivo
16 Horizontal Uma dor maçante persistente (geralmente moderadamente intensa)
17 Horizontal Resposta dos tecidos do corpo a lesões ou irritações
18 Gênero de tipo horizontal dos patos de água doce de Anatidae
19 Horizontal A dinastia que governou grande parte da Manchúria e nordeste da China, de 947 a 1125
20 Horizontal Um composto cristalino branco usado como analgésico e também como antipirético
23 Horizontal Uma cidade no centro da Tanzânia
24 Deus horizontal da morte
25 Massa horizontal em forma e seca, feita de farinha e água e às vezes ovo
27 Horizontal Um membro do povo siouan da Virgínia e Carolina do Norte
32 Horizontal Um forte desejo inquieto
35 Prelado horizontal da África do Sul e líder da luta antiapartheid (nascida em 1931)
37 Horizontal Um documento comercial usado para solicitar que alguém forneça algo em troca de pagamento
38 Mosquitos cortantes horizontais
41 Horizontal Uma cidade antiga no norte de Portugal
42 Horizontal Uma cabana esquimó
43 Mecanismo de rotação horizontal na forma de uma roda giratória montada universalmente que oferece resistência a curvas em qualquer direção
44 Horizontal A capital do Bahrain
46 Horizontal O ato de dar uma tonalidade leve ao cabelo
48 gênero Tipo Horizontal do Majidae
50 Horizontal Qualquer uma das várias plantas do gênero Camassia
54 macas voadoras horizontais
59 Horizontal A colheita inteira pode ser colhida de uma só vez
60 Horizontal Uma lei aprovada pelo Congresso dos EUA para impedir que funcionários sejam feridos ou contraiam doenças durante o emprego
61 Horizontal Um bloco pesado de ferro ou aço sobre o qual os metais quentes são modelados martelando
62 estadista inglês horizontal que se opôs ao divórcio de Henrique VIII de Catarina de Aragão e foi preso e decapitado
63 Horizontal Um homem que corteja uma mulher
64 jogador de beisebol horizontal dos Estados Unidos
65 Horizontal Um olhar secreto
66 Horizontal Pequena gaivota delgada, com asas estreitas e cauda bifurcada
67 Horizontal Conhecido por uvas e azeitonas e azeite
1 Líder revolucionário francês vertical (nascido na Suíça) que foi líder em derrubar os girondistas e foi esfaqueado até a morte em seu banho por Charlotte Corday (1743-1793)
2 Vertical anual para ervas perenes da região do Mediterrâneo
3 Videira arbustiva tropical do sudeste asiático vertical com frutos apimentados
4 Ani vertical
5 Vertical A primeira luz do dia
6 Título vertical para o ex-monarca hereditário do Irã
7 Vertical Um fotógrafo que opera uma câmera de filme
8 Vertical Uma cidade no sul da Turquia, no rio Seyhan
9 Vertical Uma região árida com pouca ou nenhuma vegetação
10 pintor espanhol surrealista vertical (1904-1989)
11 Vertical Qualquer um dos vários compostos solúveis em água com um sabor amargo e capaz de tornar o tornassol vermelho e reagir com uma base para formar um sal
12 Vertical Nativo ou habitante da Tailândia
13 Vertical (no gnosticismo), um poder ou natureza divina que emana do Ser Supremo e desempenha vários papéis na operação do universo.
21 Vertical Um vulcão ativo no sudeste da Colômbia nos Andes
22 Vertical Um lepton de massa muito grande
26 Vertical Um membro do povo indiano da América do Sul que vive no Brasil e no Paraguai
28 Vertical O principal nervo sensitivo da face e o nervo motor dos músculos da mastigação
29 Vertical Um redemoinho em miniatura ou redemoinho resultante quando a corrente de um fluido se dobra novamente
30 Artista britânico vertical e escritor de versos sem sentido (1812-1888)
31 Biscoito de chocolate vertical com recheio de creme branco
32 Vertical Um míssil balístico capaz de viajar de um continente para outro
33 Vertical Uma língua chadica de três tons
34 Vertical Uma unidade de capacidade usada para medir arenque fresco
36 Vertical Grande Híbrido suculento grande entre tangerina e toranja, com uma pele enrugada e grossa
39 Tecido vertical de lã ou lã e algodão, usado com freqüência para forros e roupas e cortinas
40 Vertical Uma unidade de peso farmacêutico igual a 480 grãos ou um décimo segundo de libra
45 Vertical Uma cidade no centro da Bélgica
47 Vertical Um xale longo e colorido
49 Vertical Um livro no Antigo Testamento descrevendo como Josué levou os israelitas a Canaã (a Terra Prometida) após a morte de Moisés.
51 Vertical Um medicamento anti-inflamatório não esteróide (nomes comerciais Advil e Motrin e Nuprin) usado para aliviar a dor da artrite e como analgésico e antipirético
52 Antílope vertical semelhante à cabra da Eurásia central, com nariz atarracado como probóscide
53 Tenista vertical dos Estados Unidos (nascida na Iugoslávia em 1973)
54 Vertical Um pouco de umidade
55 Plantas suculentas verticais com rosetas de folhas geralmente com fibras como cânhamo e espigas de flores vistosas
56 Atividade vertical envolvida em manter algo em bom estado de funcionamento
57 Vertical (sul-africano) uma viagem de carroça (especialmente uma migração organizada por um grupo de colonos)
58 Vertical Um lago de montanha (especialmente um formado por geleiras)
Palavras cruzadas 6 a 6 em russo:1 piloto de teste soviético horizontal, Herói da União Soviética, um dos participantes do vôo sem escalas Moscou - Polo Norte - Vancouver
2 Orelha Horizontal
3 adivinhador horizontal
4 cidade horizontal na Itália na ilha da Sicília
5 Fios texturizados enrolados horizontais obtidos por ondulação em câmaras aquecidas
6 Cineasta francês horizontal, roteirista ('' Bad Blood '', '' Boyfriend Meets Girl '')
7 Moeda de prata vertical do Grão-Ducado da Lituânia do século XVI
8 Bioquímico americano vertical, primeiro sintetizou o gene tRNA (Prêmio Nobel 1968)
9 Cidade vertical na Federação da Rússia, Ossétia do Norte, no rio Ardon, na estrada militar da Ossétia
10 Vertical nicho horizontal na parede da câmara funerária, onde o falecido foi colocado e murado ou pendurado com um dossel
11 Vertical A coxa da carcaça
12 Cidade vertical no sudeste da França
Palavras cruzadas 6 em 6 em inglês:1 Horizontal Um membro do povo indiano do norte da Califórnia e sul do Oregon
2 Horizontal Um membro de uma das quatro divisões dos gregos pré-históricos
3 Horizontal Pode tornar-se viciante
4 Deus da luz grego horizontal
5 Horizontal Pequenos itens pessoais ou de vestuário ou de costura
6 Árvore de madeira de valor horizontal da Nova Zelândia, produzindo madeira avermelhada dura, usada em móveis, pontes e cais
7 Vertical Uma linha reta que cruza uma curva em dois ou mais pontos
8 Vertical Qualquer um dos vários pássaros com crista do Velho Mundo com uma conta delgada e curvada para baixo
9 Romancista americano vertical conhecido por livros infantis (1832-1888)
10 pássaros azuis norte-americanos verticais
11 Vertical Uma pessoa cuja ocupação é fazer e alterar roupas
12 Gênero de tipo vertical das Annonaceae
Conclusão
A aplicação do solucionador SAT aumenta a complexidade das palavras cruzadas que podem ser geradas. Como no artigo anterior, quero pedir ao próximo pico incontestado - que faça palavras cruzadas com palavras em russo ou inglês na forma de um quadrado 7 por 7. Quem aceitará o desafio?