Início / algoritmo do solucionador de Sokoban
Guia do algoritmo de Sokoban

Algoritmo de Sokoban: como a busca encontra uma solução

Um algoritmo de Sokoban transforma o quebra-cabeça em uma busca por estados do tabuleiro. Ele registra caixas, piso alcançável, empurrões válidos e posições conhecidas.

Este guia explica como um solucionador funciona. Use a página do solucionador online para inserir um tabuleiro ASCII e obter uma rota.

Atualizado em 16 de novembro de 2026Para jogadores, criadores de níveis e programadores curiosos

Tabuleiro de Sokoban com caixas, objetivos, paredes e casas de acesso

O solucionador avalia o tabuleiro como um grafo de estados, não apenas como imagem.

Resposta rápida: Em resumo: o solucionador guarda estados compactos, calcula por preenchimento o piso alcançável, gera apenas empurrões legais e elimina estados repetidos ou claramente bloqueados. Mantém ligações aos estados anteriores para reconstruir a solução como uma sequência de movimentos.

A unidade útil costuma ser um empurrão, não um passo com as setas. Caminhar entre empurrões altera a posição do jogador, mas não as caixas. Por isso o tabuleiro pode ser tratado como um grafo: um nó é uma posição conhecida e uma aresta é um empurrão legal com a caminhada necessária para chegar atrás da próxima caixa.

O grafo é grande porque nem todo empurrão pode ser desfeito. Para mover uma caixa é preciso ficar do lado oposto; não se pode puxá-la de um canto ruim. Cada nó deve conservar quais casas contêm caixas e quais casas o jogador alcança sem movê-las.

Quando todos os alvos estão ocupados, o solucionador segue as ligações aos estados anteriores até ao início e reconstrói a rota. A sequência de direções pode conter muitos passos, mas as decisões essenciais são os empurrões que alteraram o estado.

Como representar o estado do tabuleiro

O tabuleiro tem dados fixos e variáveis. Paredes e alvos são lidos uma só vez. Variam as coordenadas das caixas e a região alcançável do jogador. Duas posições do jogador costumam ser equivalentes quando se pode caminhar entre elas sem atravessar caixas. Normalizá-las evita encher a fila com posições de caminhada duplicadas.

Parte do estadoInformação registradaImportância
Paredes e alvosGeometria fixaDefine o piso transitável e a condição de vitória.
Configuração das caixasUma coordenada por caixaDetermina empurrões e atribuições a alvos possíveis.
Região do jogadorPiso alcançável sem empurrarMostra de que lados se pode apoiar um empurrão.
Antecessor e açãoEstado anterior e direção do empurrãoPermite reproduzir a rota em vez de responder apenas sim ou não.

Uma tabela de transposições, ou conjunto de visitados, guarda uma chave por estado normalizado. Examinar novamente as mesmas caixas e região alcançável não revela novas continuações. É uma troca de memória por velocidade.

Tabuleiro de Sokoban para planejar a ordem das caixas com alvo restrito e área livre de espera

Diagrama explicativo: a ordem das caixas altera os estados alcançáveis depois de cada empurrão. A imagem ilustra a ideia, não é uma captura do código.

Como cresce a fronteira de busca

Depois de ler um estado, um preenchimento calcula a área transitável. Para cada caixa, verificam-se quatro direções. Um empurrão é legal se o destino for piso vazio e o jogador alcançar a casa oposta. Cria-se então um novo estado com a caixa deslocada e a região acessível recalculada.

A ordem da busca muda as garantias. A busca em largura examina sequências curtas primeiro e minimiza empurrões se todas as arestas tiverem o mesmo custo. A busca em profundidade segue um ramo e usa menos memória de fronteira, mas pode demorar num ramo inútil. A busca de custo uniforme ou A* combina custos e heurísticas; as propriedades e a qualidade da estimativa determinam o significado do resultado.

  1. Ler.Identificar paredes, alvos, caixas e jogador; rejeitar contagens erradas ou símbolos não aceitos.
  2. Alcançar.Marcar o piso acessível sem mover caixas.
  3. Expandir.Gerar empurrões com casas de apoio e destino válidas.
  4. Podar e registrar.Ignorar duplicados e bloqueios evidentes, guardando antecessor e empurrão.
  5. Terminar.Parar com todos os alvos cobertos ou informar que não foi encontrada uma rota dentro do limite.

Não é preciso conservar cada caminhada separadamente. Depois de empurrar, uma região alcançável normalizada basta para gerar os próximos empurrões. Isso torna viável um solucionador compacto no navegador.

Por que podar os bloqueios

Sem poda, a busca perde tempo em posições sem saída. A regra mais simples é um canto sem alvo: uma caixa contra duas paredes perpendiculares não consegue sair, e o ramo pode ser descartado. Também se verificam paredes sem alvo compatível, grupos 2×2 imóveis e caixas que fecham corredores de uma casa.

Algumas falhas dizem respeito ao acesso, não a uma caixa imóvel. Um alvo corretamente preenchido pode ocupar o único apoio necessário para outra caixa. Duas caixas podem deslizar, mas o jogador já não alcança o lado para separá-las. Esses casos difíceis exigem regras simples, detecção de duplicados e um orçamento finito de busca.

Exemplo de bloqueio de canto em Sokoban para explicar a poda da busca

Um bloqueio de canto pode ser reconhecido antes de aprofundar a busca. Perdas de acesso mais sutis exigem verificações de estado mais abrangentes.

A poda precisa preservar a correção: uma regra agressiva demais pode eliminar uma solução incomum. Ferramentas pequenas devem explicar os limites das regras, sem chamar todo resultado sem solução de prova.

Custo de empurrar, caminhar e usar heurísticas

É necessário definir o que significa «solução mais curta». Uma rota ótima em empurrões minimiza movimentos das caixas; uma ótima em movimentos inclui os passos. Esses objetivos podem conflitar: contornar uma sala pode poupar um empurrão e preservar a atribuição das caixas. O solucionador deve priorizar os custos e identificar o critério no resultado.

Uma heurística estima a distância até ao fim. Uma forma simples associa caixas a alvos por distâncias na grade e penaliza caixas presas nas paredes. Paredes, apoios e ordem das caixas tornam a rota real mais complexa. A estimativa prioriza estados promissores, sem provar que a distância seja exata.

Em tabuleiros pequenos, convém mostrar a sequência, os empurrões, os passos e os estados examinados. O leitor pode comparar com o próprio plano sem presumir uma otimalidade não demonstrada.

Acompanhando um tabuleiro pequeno

Neste exemplo com uma caixa, # representa parede, . alvo, $ caixa e @ jogador.

#####
# . #
# $ #
# @ #
#####

A região inicial inclui a casa do jogador e o piso abaixo da caixa. Existe um empurrão legal: ficar abaixo dela e empurrar para o alvo acima. O solucionador registra a nova coordenada, recalcula o acesso e identifica todos os alvos ocupados. A ligação ao antecessor permite reconstruir a caminhada necessária seguida de um empurrão.

Num tabuleiro difícil, a fronteira contém vários empurrões candidatos. Um ramo que termina num canto desaparece na poda, enquanto outro continua na fila. Essa é a diferença entre tentar ao acaso e guardar o que a busca já estabeleceu.

Quando o solucionador para ou indica um problema

Há várias razões para parar. Quantidades diferentes de caixas e alvos, símbolos não aceitos ou jogador ausente invalidam a entrada. Um tabuleiro válido pode superar limites seguros de linhas, colunas, caixas ou estados visitados. Uma busca limitada também pode esgotar a fronteira sem encontrar solução.

Apenas o último caso numa busca completa e ilimitada justifica uma prova matemática de impossibilidade. Ferramentas pequenas limitam o trabalho para manter a página responsiva. Um aviso convida a reduzir o tabuleiro, inspecionar bloqueios ou planejar de trás para a frente. O solucionador de Sokoban associado documenta os limites para tabuleiros pequenos e devolve uma mensagem clara, em vez de executar indefinidamente.

Criadores de níveis podem verificar uma rota com o solucionador e depois testar com pessoas para confirmar se a ideia fica clara. O guia de criação de níveis de Sokoban explica esse processo; este artigo explica a busca por trás dele.

FAQ do algoritmo de Sokoban

O que é um algoritmo solucionador de Sokoban?

É uma busca que representa caixas e jogador, gera empurrões legais, descarta bloqueios conhecidos e reconstrói uma rota quando todos os alvos estão ocupados.

O solucionador examina cada toque nas setas?

Normalmente agrupa os passos numa região alcançável e expande empurrões como as arestas principais. Assim elimina muitos caminhos de caminhada equivalentes.

Por que a poda de bloqueios acelera a busca?

Ela remove ramos com cantos sem alvo, grupos imóveis e passagens fechadas antes de gastar tempo nos estados seguintes.

A primeira rota encontrada é a mais curta?

Só quando a ordem de busca e o modelo de custos garantem isso. Um solucionador limitado pode devolver uma rota útil sem provar que minimiza empurrões ou movimentos.

O que significa atingir o limite de busca?

A ferramenta esgotou o orçamento de segurança antes de provar uma rota ou a sua impossibilidade. Tente um tabuleiro menor ou verifique o estado manualmente; a mensagem não prova que não exista solução.

Fontes e leituras complementares

Os estados e as regiões alcançáveis foram conferidos com a referência de solucionadores da wiki de Sokoban. Os exemplos de ordem seguem Algoritmos básicos de busca em Sokoban. O crescimento do espaço de estados e as estimativas de distância são discutidos na documentação do solucionador de Pavel Klavik. As fontes tratam de Sokoban padrão; os limites desta ferramenta vêm do solucionador Zeek vinculado.

Resolva um tabuleiro pequeno e examine o resultado

Cole um tabuleiro ASCII no solucionador do navegador e volte para relacionar a sequência com estados, empurrões e poda.

Abrir o solucionador de Sokoban