Há um mistério interessante no final de Harry Potter e a Pedra Filosofal. Harry e Hermione entram na sala, após o que as entradas são bloqueadas pelo fogo mágico, e elas só podem sair dela resolvendo o seguinte enigma:
Há perigo diante de você e salvação atrás de você,
Dois o ajudarão, a quem você encontrará entre nós;
Com um dos sete atacantes, você continuará a se mover
O outro o levará de volta imediatamente.
Em nós dois você encontrará apenas vinho de urtiga,
E três carregam destruição, permanecem em fila secretamente.
Então escolha de qual tentar,
Para isso, damos quatro pistas.
Em vão o veneno tentou esconder seu calor mortal
Você sempre o encontrará à esquerda do vinho,
E saiba que aqueles que estão no limite, diferentes, guardam o presente,
Mas se você quiser mais, nem um único ajudará.
Estamos separados em tamanho, de ponta a ponta,
Sua morte não fica menos, mas também não é maior;
O segundo do lado direito e do lado esquerdo do segundo
Eles gostam de gêmeos, apesar de parecerem diferentes.
[
da "tradução folclórica" do livro "Harry Potter e a Pedra Filosofal" ]
Simplificando, eles precisam entender quais garrafas contêm quais poções.
Neste artigo, resolveremos todas as 42 variantes possíveis desse quebra-cabeça usando programação e desenharemos um diagrama dos resultados (como na figura acima, apenas muito maior).
Espere um segundo, e de onde vieram 42 opções?
Isso ocorre porque os locais das poções “menores” e “maiores” não são indicados. O maior pode estar em um dos sete lugares, o que dá as 6 opções restantes para o menor, totalizando 7 * 6 = 42. Descobrir que tipo de arranjo Joan Rowling tinha em mente ao inventar esse enigma falhará, a menos que ela fale sobre isso em no seu twitter. Enquanto isso, esse dia inevitável ainda não chegou, podemos escolher uma versão aleatória e trabalhar com ela. No entanto, não haverá garantias de sua resolubilidade, e é por isso que trabalhamos para o bem comum, resolvendo todas as 42 variantes do quebra-cabeça (ou provando sua insolubilidade).
SIM DECIDIR JÁ
Primeiro, aqui estão todas as limitações do quebra-cabeça, reformuladas de uma maneira simples:
- Existem duas poções inofensivas, 3 envenenadas, uma que permite avançar e outra que permite voltar.
- No lado esquerdo de cada uma das duas poções inofensivas é venenoso.
- As poções dos dois lados são diferentes e nenhuma delas permite que você avance.
- Os frascos maiores e menores não contêm veneno.
- O segundo frasco à esquerda e o segundo frasco à direita contêm a mesma poção.
Como lidar com isso? Considere a seguinte opção. Observe que, conforme declarado no enigma, na linha há 1 garrafa menor que todas as outras em tamanho e 1 garrafa é maior que todas as outras.
Vamos tentar classificar estupidamente todas as opções - pegue uma garrafa e selecione todas as opções possíveis para o conteúdo.
Por exemplo, a primeira garrafa não pode conter uma poção que nos empurre para a frente devido à restrição nº 3. Além disso, ele não contém uma poção segura devido à restrição nº 2 - o veneno não pode ser localizado à esquerda dele. Isso nos deixa com opções com uma poção envenenada e uma poção que retorna de volta. Vamos tentar as duas opções.
Nas imagens a seguir, as poções verdes indicam veneno, laranja - bebidas seguras, azul - uma poção se movendo para trás, roxa - se movendo para frente.
Repetimos esse processo para as duas opções de trabalho - pegue a segunda garrafa e tente alternadamente todas as opções de conteúdo válidas. Isso nos dará o seguinte:
Continuando a agir dessa maneira e descartando todas as opções de trabalho nas quais uma garrafa não pode ser enchida com uma poção sem violar as restrições listadas acima, chegamos à única opção aceitável:
Naturalmente, não tínhamos garantias para encontrar uma solução. Não pode haver solução, ou pode haver várias (e se você tiver várias soluções, isso é equivalente ao fato de que o enigma não pode ser resolvido, pois não se sabe qual das poções está correta).
A aplicação do algoritmo a todas as opções nos fornece as seguintes soluções. 8 opções de quebra-cabeça são solucionáveis, 8 não têm soluções e 26 têm várias soluções.
Saiba mais sobre soluções.
Existe algo em comum com todas as variantes de quebra-cabeças resolvidas? Sim Por favor, note que nelas as garrafas menores ou maiores estão em 2º ou 6º lugares. Isso permite concluir que as 2ª e 6ª garrafas contêm poções seguras devido às restrições nº 4 e nº 5. Sem essa etapa, não podemos eliminar a possibilidade de envenenamento nessas garrafas e, como resultado, chegamos a várias soluções possíveis. As opções solucionáveis também exigem que a segunda garrafa “especial” (a menor ou a maior) fique em 3º ou 4º lugar. Caso contrário, a localização exata da poção que nos move para frente não pode ser encontrada.
Sumário
Terminarei a citação do livro.
Hermione exalou ruidosamente, e Harry ficou surpreso ao ver que ela estava sorrindo - essa era a última lição que ele conseguia pensar. "Brilhante", disse Hermione. - Isso não é mágico - isso é lógica, um enigma. Muitos grandes mágicos não terão um grama de lógica e ficariam presos aqui para sempre. "
Mas ei, talvez possamos descobrir a versão canônica do enigma com base no diálogo do livro:
"Entendi", disse ela. "A menor garrafa nos levará através do fogo negro e até a Pedra."
...
"E qual deles te devolverá através do fogo púrpura?"
Hermione apontou para a garrafa arredondada no lado direito da linha.
Droga. Esta opção ainda nos oferece várias soluções. Escreva tweets, DR.
Código
Se você estiver interessado em código para resolver esse quebra-cabeça e desenhar diagramas, faça o
download aqui .