Tenho certeza de que muitos dos leitores às vezes se envolvem em bobagens inúteis na sala de aula, em vez de ouvir o professor. Fiz exatamente isso, e uma maneira de acabar com o tempo era jogar no papel. O jogo de pré-visualização (cujo nome ainda é desconhecido para mim) me pareceu especialmente interessante, mas há duas razões: ele não requer uma segunda pessoa e pode ser concluído! É verdade que era extremamente raro fazer isso. Durante muito tempo, fiquei pensando como a solução pode ser simples e, agora, depois de muitos anos, não será difícil encontrá-la programaticamente.
As regras
Primeiro, vale a pena descrever as regras. O jogo começa com o seguinte campo:
123456789
111213141
516171819
Aqui, todos os números de 1 a 19 são registrados caractere por caractere, com exceção de 10. Os números estão localizados da esquerda para a direita, linha por linha. As regras são bastante simples - a cada passo, você precisa cruzar 2 números que correspondem aos seguintes critérios:
- os números devem ser iguais ou no total dar 10 (1 e 1, 3 e 7, 8 e 2, etc.);
- eles devem ficar um em cima do outro ou estar dispostos em série. Nesse caso, os números já riscados são ignorados.
Uma das opções para os primeiros movimentos é mostrada abaixo:
1 23456789
1 11213141
5161718 19
#2345678 9
# 1 1213141
5161718##
#2345678#
##1213141
5161718##
No momento em que não há mais movimentos, todos os números não marcados são adicionados ao final. O jogo termina quando todo o campo é cruzado.
#2345678#
##1213141
51 6 171 8 ##
23 4 567 8 12
131415161
718
#2345678#
##1213 1 41
5 1 # 1 71###
23#567#12
131415 1 61
718
#2345678#
##1213#41
5###71###
2 3 #567#12
1 3 1415#61
718
...
O número de movimentos disponíveis está aumentando rapidamente, o jogo começa a se ramificar fortemente. Muitas vezes, a tabela fica tão longa que passa para a próxima página em um caderno. É mais fácil iniciar um novo lote. Às vezes eu continuava sem persistência, mas no final desisti.
Isso levanta a questão razoável - com que rapidez você pode terminar este jogo? Na infância, era possível encontrar uma solução em uma coluna em uma folha de caderno - isso tem cerca de 40 linhas ou 360 caracteres.
Não sei a maneira garantida de concluir o jogo. Não está completamente claro como escolher uma estratégia. Você pode tentar jogar sozinho, se não tiver.
Solução
Como as soluções para esses problemas são buscadas? Não sei ao certo, mas escolhi o busto de sempre.
Precisamos de uma fila, primeiro consistindo apenas em uma única configuração inicial. Em cada etapa, pegamos a seguinte configuração da fila, analisamos todas as jogadas disponíveis nela e as adicionamos ao final da fila ou nos declaramos vencedores se não houver essas jogadas.
123456789 #23456789 12345678# 123456789 123456789 123456789 123456789 ...
111213141 #11213141 #11213141 ##1213141 1##213141 11#213141 11121314# ...
516171819 516171819 516171819 516171819 516171819 516#71819 51617181# ...
Se você não insistir na primeira solução disponível, esse algoritmo produzirá todas as soluções possíveis (na presença de uma quantidade infinita de RAM).
Na prática, essa abordagem ingênua não ajudará em nada, pelo menos por causa das duplicatas que aparecem constantemente na fila. Portanto, serão necessárias algumas otimizações, que serão explicadas agora:
- Naturalmente, as configurações precisam ser armazenadas em cache para não serem colocadas em fila novamente. Isso aumentará bastante o uso de memória, mas ainda não ajudará a obter uma solução em um período de tempo razoável. Além disso, a questão da comparação de configurações surge acentuadamente. Como duas configurações vencedoras do mesmo tamanho sempre consistem apenas em números tachados, é necessária uma maneira adicional para distingui-las; caso contrário, nem todas as soluções serão encontradas;
- para tornar a pesquisa significativa e rápida, é melhor usar uma fila de prioridade. Quanto menos números no campo (inclusive riscados), mais cedo essa configuração deve ser considerada;
- se você precisar de mais de uma solução, mas muitas, é melhor limitar o número máximo de números em campo, a pesquisa emitirá soluções muito mais cedo.
A resposta
Se tudo estiver correto, acontece que a solução mínima consiste em apenas 68 caracteres ou 8 linhas!
Vou trazê-lo na forma de gif-animação. Alguns movimentos foram colados em um para reduzir o número de quadros:
Sinceramente, fiquei impressionado com a falta de decisão. Mas talvez essa sorte e outras decisões não sejam cumpridas em breve e demorem muito?
Não, decisões não são raras. Respostas rápidas são encontradas em comprimentos de 72, 74 e 76. E quatro soluções mais fundamentalmente diferentes, com um comprimento de 80. Em geral, eu consegui encontrar 30 soluções com até 90 de comprimento (inclusive), e se eu aumentar a borda para 100, haverá 170 soluções. mas procurá-los se torna mais caro.
Sob o spoiler, a solução ideal é descrita em detalhes:
Texto oculto 123456789 111213141 516171819 123456789 111213141 5161718## 123456789 1##213141 5161718## 12345678# 1##21314# 5161718## #2345678# ###21314# 5161718## #234567## ####1314# 5161718## #234567## ####1314# 5161718## 234567131 45161718 #234567## ####1314# 51#1718## 23#567131 45161718 #234567## ####1314# 51#171### #3#567131 45161718 #234567## ####1314# 51#171### #3#567#31 451617#8 #234567## ####1314# 51#171### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 571356145 16178 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 57#356145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 5###56145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 #####6145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 34567131# ######145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3456713## #######45 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 451617### 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 45161#### ##56713## #######45 1##78 #234567## ####1314# 5###7#### #3#56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# 5######## ###56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##56##### #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##5###### ########5 1##78 #234567## ####1314# ######### ####6###1 45161#### ######### ######### 1##78 #234567## ####131## ######### ########1 45161#### ######### ######### 1##78 #234567## ####13### ######### ######### 45161#### ######### ######### 1##78 #234567## #####3### ######### ######### 4516##### ######### ######### 1##78 #23456### ######### ######### ######### 4516##### ######### ######### 1##78 #2345#### ######### ######### ######### #516##### ######### ######### 1##78 #234##### ######### ######### ######### ##16##### ######### ######### 1##78 #23###### ######### ######### ######### ##1###### ######### ######### 1##78 #23###### ######### ######### ######### ######### ######### ######### ###78 #2####### ######### ######### ######### ######### ######### ######### ####8 ######### ######### ######### ######### ######### ######### ######### #####
Meu código de solução Java pode ser visualizado neste link , mas eu aviso que é terrível, porque originalmente escrito não para publicação. Em sua forma atual, ele encontra todas as soluções com até 70 caracteres (ou seja, apenas uma solução). Isso é fácil de corrigir, brincando com as condições no código.
Obrigado pela atenção!