Eu realmente amo quebra-cabeças deslizantes, mas recentemente não tive tempo para eles. Por isso, preciso de um programa para me dar a minha solução de quebra-cabeças deslizantes, especificamente quebra-cabeças de Klotski.
Sua entrada estará no seguinte formato:
#######
#001gg#
##.222#
.######
onde #
representa paredes, .
representa uma área aberta, g
representa a meta e números adjacentes representam blocos diferentes. Você pode assumir que:
- Não haverá mais de 10 blocos
- Não haverá dois blocos com o mesmo número
- Todos os blocos serão fechados por paredes
- A grade é retangular
- O
0
bloco é grande o suficiente para cobrir todos os quadrados de gol. - Existe uma solução válida
Você precisa retornar uma sequência de movimentos que colocarão o 0
bloco para que cubra todos os quadrados de gol. Os blocos não podem atravessar paredes ou outros blocos. Para o quebra-cabeça acima, uma sequência apropriada seria
2L,1R,1R,1D,0R,0R,0R
enquanto representa mover o 2
bloco 1 quadrado para a esquerda, o 1
bloco 2 quadrados para a direita (no topo da meta), depois 1 quadrado para baixo e, em seguida, o 0
bloco 3 quadrados para a direita.
Na verdade, existem várias seqüências que funcionarão para o problema acima, e a produção de qualquer uma delas é aceitável. Sua solução deve ser ótima, o que significa que deve produzir uma sequência que resolva o quebra-cabeça o menor número possível de etapas.
A sequência deve ser impressa como acima, mas pode ser separada por vírgula, nova linha ou espaço. Não me importo se houver vírgulas ou espaços em branco. Você deve produzir a saída em tempo razoável (máximo de 120 segundos nos quebra-cabeças abaixo).
Quebra-cabeça 1:
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..
Enigma 2:
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######
Enigma 3:
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######
Quebra-cabeça 4:
.####.
##00##
#.00g#
#.0.1#
#..g2#
######
Isso é código-golfe, então a solução mais curta (em bytes) vence!
fonte
Respostas:
Python, 1761
Meio que me queimei com essa questão, por isso não consegui jogar. De qualquer forma, agora é a única solução que resolve tudo dentro do prazo (o mais longo, nº 3, leva 27 segundos).
fonte
JavaScript (ES6), 446
388Largura da primeira pesquisa; portanto, a primeira solução encontrada é a mais curta.
Enquanto eu ainda acho que é uma boa solução, não é boa o suficiente. Mesmo depois de verificar milhões de posições (tempo de execução de vários minutos), não consegui encontrar uma solução, por exemplo, 2 e 3.
Edite a versão modificada do ES6 para superar o limite de tempo de execução do javascript. Quebra-cabeça 3 resolvido em 7min, 145 etapas. Quebra-cabeça 2 resolvido em 10min, 116 passos
Editar 2 Grande aceleração, usando a idéia de @ orlp de considerar igual a dois blocos da mesma forma (excluindo o bloco '0' que é especial). Isso reduz o espaço das posições visitadas durante o BSF. Por exemplo, para o quebra-cabeça 2, qualquer posição com o bloco 1,2,3 ou 5 trocado é realmente a mesma.
Tempo: o mais longo é o quebra-cabeça 3, ~ 20 segundos, no meu laptop.
Use o Firefox para jogar com o novo JsFiddle para testar.
Desatualizado
EcmaScript 6 (FireFox) JSFiddleEcmaScript 5 (Chrome) JSFiddleExemplo
Quebra-cabeça 1
Puzzle 2
Puzzle 3
Quebra-cabeça 4
fonte