O tabuleiro diário tem sete peças de largura e sete de altura. Parece pequeno. Então você conta de quantas maneiras ele pode ser girado, e o número deixa de parecer pequeno por completo.
Escrito e editado em inglês. Esta versão em português foi produzida por tradução automática; quando a precisão importa, o original em inglês é a referência. Ler o original em inglês →
Cada peça em Conduit tem quatro orientações possíveis, girada zero, um, dois ou três quartos de volta a partir de onde está. 1 Dê a cada uma das quarenta e nove células da grade diária uma escolha independente entre essas quatro, e o número de estados distintos do tabuleiro é 449. Escrito por extenso, isso dá 316.912.650.057.057.350.374.175.801.344, mais de trezentos octilhões de configurações, entre as quais o jogo pede que você encontre uma que esteja totalmente acesa e sem vazamentos.
O embaralhamento que lhe entrega um quebra-cabeça escolhe, para cada peça, um número aleatório de quartos de volta, de zero a três. 1 Assim, o tabuleiro que você encontra é sorteado uniformemente desse espaço enorme, com uma única exclusão cuidadosa que o jogo faz para não lhe entregar uma grade já resolvida. 1 A força bruta está fora de cogitação: os próprios testes do jogo observam que experimentar as quatro rotações de cada peça é exponencial, e eles só executam a busca exaustiva em tabuleiros de brinquedo com nove células ou menos. 2
Esse número de manchete conta a mais, porque algumas peças não se importam com a forma como você as gira. Uma cruz, com conectores nos quatro lados, tem a mesma aparência nas quatro orientações; girá-la não muda nada. Uma linha reta tem apenas duas aparências distintas, horizontal e vertical, porque meia-volta a leva sobre si mesma. Só as formas assimétricas, o cotovelo, o tê e a ponta de conector único, têm de fato as quatro orientações distintas. 3
| Forma | Conectores | Voltas distintas | Simetria |
|---|---|---|---|
| Ponta (nó/lâmpada) | 1 | 4 | nenhuma |
| Linha | 2 | 2 | meia-volta |
| Cotovelo | 2 | 4 | nenhuma |
| Tê | 3 | 4 | nenhuma |
| Cruz | 4 | 1 | completa |
As formas são nomeadas nas notas de design do jogo; as contagens de orientações distintas decorrem de a máscara de conectores de quatro bits permanecer inalterada sob as rotações listadas. 3 O espaço de busca efetivo é menor que 449 exatamente pelo produto dessas simetrias por peça, mas, em qualquer tabuleiro com uma boa mistura de cotovelos e tês, continua astronomicamente grande.
Inverta a pergunta. Esqueça as orientações que você poderia tentar; pergunte quantos tabuleiros resolvidos são possíveis, para começar. Uma grade de Conduit concluída é um conjunto de tubos que está conectado, em que a energia chega a todas as peças e que não tem nenhum laço desperdiçado, porque uma árvore geradora é o que o gerador constrói: conectada, acíclica, um único caminho da fonte até cada nó. 3 Cada uma dessas fiações é, precisamente, uma árvore geradora do grafo da grade, em que os vértices são as células e as arestas são as fronteiras compartilhadas que um tubo pode transpor.
E árvores geradoras podem ser contadas com exatidão. O teorema matriz-árvore de Kirchhoff, um resultado de 1847, diz que o número de árvores geradoras de qualquer grafo é igual a qualquer cofator de sua matriz laplaciana, um determinante que se pode calcular em tempo polinomial. 4 Para grades, a contagem explode com o tamanho: um modesto reticulado 4×4 já tem 100.352 árvores geradoras, e o número sobe ferozmente a partir daí. Cada uma delas é uma solução legítima e totalmente acesa de Conduit. O quebra-cabeça é difícil não porque as respostas sejam escassas, mas porque estão escondidas numa multidão muito maior de quase-respostas.
Os estados resolvidos são contáveis e numerosos; os estados embaralhados são contáveis e imensamente mais numerosos. Resolver é a busca por uma agulha que você sabe que existe, porque o jogo a escondeu ali de propósito.
Você poderia esperar que o quebra-cabeça se decompusesse: fixar o canto superior esquerdo, depois a peça ao lado, e marchar ordenadamente até o canto oposto. Às vezes um trecho do tabuleiro cede a isso. Uma peça num canto tem apenas duas arestas que tocam vizinhos, então seus conectores ficam fortemente restringidos; uma ponta na borda só pode apontar para dentro. Esses movimentos forçados oferecem pontos de apoio.
Mas as duas condições de vitória não se encadeiam de modo tão obsequioso. Sem vazamentos é uma propriedade local, que você pode verificar aresta por aresta. Energizado não é: se uma peça está acesa depende de uma cadeia ininterrupta de junções que corre todo o caminho de volta até a fonte, possivelmente atravessando o tabuleiro inteiro. 3 Uma mudança que você faz num canto pode mergulhar uma região distante na escuridão ao romper o único caminho que a alimentava. Esse acoplamento, o destino de cada peça potencialmente atado a uma rota pela grade inteira, é o que impede um quebra-cabeça de rotação de desabar em mera contabilidade, e é por isso que os solucionadores da família mais ampla Net/Pipes (os quebra-cabeças de tubos) se apoiam em propagação de restrições e busca, em vez de uma simples varredura da esquerda para a direita. 5
Apesar de toda a vastidão do espaço de estados, a quantidade pela qual Conduit avalia você é minúscula e humana: quantas vezes você tocou. A pontuação é 1000 − 4 × jogadas − 2 × segundos, com piso em zero. 3 Existe um número mínimo teórico de rotações para qualquer tabuleiro dado, a soma, sobre todas as peças, do menor número de quartos de volta necessários para alcançar uma orientação resolvida, e cada giro desperdiçado além dele custa quatro pontos, cada segundo ocioso, dois.
Então o jogo de verdade fica entre dois fatos enormes e um pequeno. O palheiro tem 449 orientações de largura; as agulhas são as muitas árvores geradoras da grade; e a sua tarefa é viajar de um ponto ao outro com o menor número possível do único movimento permitido. A combinatória garante que há uma resposta lá dentro. A pontuação, discretamente, desafia você a encontrá-la sem vagar. 4