210. André Castro Ramos - Mestrado e Doutorado em Ciência da

UNIVERIDADE FEDERAL DO CEARÁ
CENTRO DE CIÊNCIAS
DEPARTAMENTO DE COMPUTAÇÃO
PROGRAMA DE MESTRADO E DOUTORADO
André Castro Ramos
COMPLEXIDADE E ALGORITMOS DE JOGOS DE BLOCOS
FORTALEZA – CE
Julho de 2014
André Castro Ramos
COMPLEXIDADE E ALGORITMOS DE JOGOS DE BLOCOS
Dissertação de Mestrado apresentada ao
Programa de Mestrado e Doutorado em
Ciência da Computação, do Departamento
de Computação da Universidade Federal do
Ceará, como requisito parcial para obtenção
do Tı́tulo de Mestre em Ciência da Computação. Área de concentração: Otimização
(Teoria da Computação).
Orientador: Prof. Dr. Rudini Menezes Sampaio
FORTALEZA – CE
Julho de 2014
Agradecimentos
Agradeço a todos os membros do ParGO, que forneceram um ambiente propı́cio ao desenvolvimento deste trabalho, que tem significou um momento crucial em minha existência.
Especialmente ao professor Rudini, que orientou e tornou possı́vel que os resultados fossem como são agora. Agradeço também a todos os parentes e amigos fora do grupo que
incentivaram que eu ingressasse e chegasse ao passos finais de um mestrado. Em especial
a meus pais, que estiveram comigo em todos os momentos.
“Como modelos computacionais, jogos e quebra-cabeças trazem uma nova visão sobre
uma teoria e mostram que ela pode ser mais concreta do que a matemática simbólica que
a define.”
Resumo
A noção de jogo eletrônico remete a entretenimento reservado às horas vagas, mas, além de uma
indústria bilionária, também é origem potencial de diversos temas de pesquisa, tanto voltados
a suas respectivas áreas quanto de interesse da própria indústria de jogos. Nesse contexto, nas
últimas décadas, foram produzidos trabalhos que lidam com esse tipo de produto como base
para problemas a serem tratados pela teoria dos algoritmos. Neste trabalho trazemos resultados
de complexidade e algoritmos relacionados a 3 jogos com caracterı́sticas em comum, Bloxorz,
On The Edge e Bobbin 3D.
Abstract
The notion of electronic game is often related to mere entertainment for free time, but, not only
a bilionaire industry, electronic gaming is also basis to many research themes focused on their
own respective fields or on the gaming industry itself. In that context, in the last few decades,
research has been made dealing with that kind of product as a basic framework for stating
problems in Computer Science terms. In this work we show complexity results and algorithms
about 3 games with important similarities, Bloxorz, On The Edge and Bobbin 3D.
11
Sumário
Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Bloxorz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Uma formulação matemática . . . . . . . . . . . . . . . . . . . . . .
3.3 Linguagem utilizada nas próximas demonstrações . . . . . . . . . .
3.4 N P -completude do BLOXORZ . . . . . . . . . . . . . . . . . . . .
3.5 Inaproximabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Bloxorz com restrições sobre chaves . . . . . . . . . . . . . . . . . .
3.7 O BLOXORZ −− . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 O BLOXORZ − . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19
19
21
22
22
26
28
33
36
4 On The Edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 N P -completude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Bobbin 3D . . . . . . . . . . . . . . .
5.1 O problema . . . . . . . . . . . .
5.2 Linguagem a ser utilizada a seguir
5.3 Algoritmo para o BOBBIN −− .
5.4 Algoritmo para o BOBBIN − . .
5.5 BOBBIN . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
43
43
44
45
6 Tabela de problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
13
1 Introdução
Na área de Algoritmos, utilizam-se objetos matemáticos como vetores, matrizes e grafos. Um exercı́cio interessante para testar os limites da área de Algoritmos é trabalhar
com conceitos diferentes para definir os problemas. Uma fonte possı́vel de conceitos matemáticos são os jogos eletrônicos, que apesar de todas as questões motoras e artı́sticas,
possuem regras matemáticas. Nesta dissertação, analisamos vários problemas de jogos
eletrônicos sob o enfoque da área de Algoritmos e Complexidade Computacional. Após
uma revisão introdutória, apresentamos nossos resultados a partir do Capı́tulo 3 sobre
uma famı́lia especı́fica de jogos, a saber, jogos de bloco. Os nomes protegidos por direito
autoral utilizados aqui o são com propósito acadêmico, portanto de forma legal.
O estudo teórico de objetos entedidos como recreativos tem já um longo histórico.
Um caso clássico é o do problema das oito damas, uma questão baseada nas regras do
xadrez originalmente proposta por Max Bezzel e estudada por vários matemáticos, incluindo Gauss. No que se refere a estabelecer problemas computacionais a partir de jogos
eletrônicos e similares e analisar a complexidade deles sob a ótica da teoria de Algoritmos,
abaixo são cidados trabalhos relevantes relacionados ao assunto.
Em [Demaine, Demaine et al., 2007], é demonstrada a NP-completude de problemas
que representam quebra-cabeças, onde busca-se completar uma imagem com peças dotadas de propriedades de encaixe.
Em [Demaine, Demaine et al., 2004] estuda-se um jogo concebido em 2001, chamado
Clobber, que faz parte de competições de IA. Nesse jogo, há um tabuleiro onde algumas
posições possuem uma peça preta ou uma peça branca. Uma jogada possı́vel é mover
uma peça branca para uma peça preta adjacente, removendo a preta do tabuleiro (ou
vice-versa, movendo a preta para a posição da branca). Prova-se que é NP-Completo
decidir se existe uma sequência de jogadas que deixa o tabuleiro com apenas uma única
peça.
Em [Demaine, Demaine et al., 2006] é demonstrada a inaproximabilidade por um
fator n(1−ε) , para qualquer ε > 0, de um problema extraı́do de um jogo de lápis e papel
conhecido como Join Five ou Morpian Solitaire, onde n é o número de pontos iniciais.
Nesse jogo há alguns pontos desenhados sobre um grid (na versão mais popular, os pontos
iniciais formam uma cruz). Uma jogada possivel é incluir um ponto novo no grid que torne
possı́vel traçar um segmento (na horizontal, vertical ou diagonal) passando por 5 pontos
vizinhos do grid, incluindo o ponto novo. Além do resultado de inaproximabilidade, são
obtidos no artigo limites superiores e inferiores relacionados.
Em [Flake e Baum, 2002], estuda-se o jogo Rush Hour, um jogo cujo objetivo é tirar um
carro especial de um “estacionamento” cheio de outros carros. Os carros podem mover-se
apenas horizontalmente ou verticalmente de cada vez. O objetivo é levar o carro especial
14
Capı́tulo 1. Introdução
até a saı́da do estacionamento. Provou-se que é PSPACE-Completo decidir se é possivel
tirar o carro especial do estacionamento.
Em [Fraenkel e Goldschmidt, 1987], é provada a PSPACE-completude de diferentes
problemas em jogos competitivos cujo “tabuleiro” é um grafo direcionado.
Em [Aloupis et al., 2012], os autores conseguiram traduzir jogos clássicos da Nintendo em problemas computacionais com regras claras e, com isso, obtiveram resultados
algorı́timicos e de complexidade. Especificamente, os jogos-base foram os das franquias
Mario, Donkey Kong, Legend of Zelda, Metroid e Pokémon. O objetivo é saber se é possivel terminar uma determinada fase do jogo, ou seja, se há uma sequência de movimentos
que levem até o fim da fase. Os principais resultados obtidos foram a N P -completude de
cada problema. Além disso, com relação aos jogos da franquia Zelda, também foi provada
a P SP ACE-completude do problema de decisão.
Já em [Demaine et al., 2004], artigo relacionado ao Tetris, famoso jogo eletrônico,
prova-se a N P -completude e a inaproximabilidade por um fator n(1−ε) , para qualquer
ε > 0, onde n é o número de peças envolvidas no jogo. Nesse artigo, é apresentada uma
formalização matemática mais precisa, visto que o jogo Tetris é mais fácil de formalizar
do que os jogos da Nintendo. Em linhas gerais, esse modelo coloca como entrada uma
matriz que representa a tela do jogo, que não precisa estar inicialmente em branco, e
uma sequência de peças de Tetris. A saı́da do problema é uma sequência de movimentos
válidos (noção também definida no modelo) com o objetivo de minimizar ou maximizar
uma função especifica do problema em questão, como maximizar o número de linhas
eliminadas. Esse artigo se concentra em 4 funções objetivo: número de linhas eliminadas,
número de peças utilizadas até um movimento que cause a derrota, número de movimentos
que eliminem 4 linhas simultaneamente e altura máxima de uma posição ocupada da
matriz ao longo da sequência de movimentos, sendo que apenas nesse último exemplo o
problema é tratado como de minimização.
O artigo [Dor e Zwick, 1999] é um dos mais antigos voltados a jogos eletrônicos, no
caso o jogo Sokoban, um jogo cujo objetivo é posicionar blocos corretamente. Nesse artigo,
existe o cuidado explı́cito de separar o problema, que imediatamente é classificado como
um problema de planejamento de movimentos, do jogo em si. É provada a N P -completude
da abstração considerada e a P SP ACE-completude de uma versão alternativa onde é
possı́vel mover 2 blocos de uma vez.
Um modo versátil de se estudar matematicamente jogos eletrônicos é encontrado e
aplicado sucessivamente no livro “Games, puzzles and Computation” [Hearn e Demaine,
2009] e também aplicado no artigo [Demaine e Hearn, 2005]. Esse estudo se baseia
em um tipo de “jogo” sobre um grafo não orientado. É dada uma configuração (que
é basicamente uma orientação do grafo original) e cada jogada possı́vel é a inversão de
um arco da configuração. Sem entrar em muitos detalhes, nem todos os arcos podem
ser invertidos em determinada configuração, pois é preciso satisfazer algumas condições
15
relacionadas a pesos nos arcos e nos vértices. Em termos gerais, o objetivo é alcançar,
através do encadeamento de jogadas válidas, uma configuração onde um determinado arco
especial esteja invertido. Em versões de mais de um jogador, os arcos são alternadamente
invertidos por jogadores diferentes e cada jogador tem seu arco objetivo. Em versões com
movimentos limitados, um arco só pode ser invertido uma única vez.
É possivel ainda uma versão desse jogo com 0 jogadores, onde a cada passo existe
apenas uma única possibilidade de arco para ser invertido. Em um jogo com pelo menos
2 jogadores, cada jogador precisa tentar vencer “pensando” nas possı́veis jogadas de seus
adversários (e possivelmente evitando a vitória dos adversários antes dele).
No livro “Games, puzzles and Computation” [Hearn e Demaine, 2009] prova-se as
complexidades das variantes desse jogo, descritas na tabela abaixo.
Movimentos
Ilimitados
Limitados
Zero jogadores
PSPACE
P
Um jogador Dois jogadores
PSPACE
EXPTIME
NP
PSPACE
time ou informação parcial
RE
NEXPTIME
Resumidamente, P é a classe dos problemas computacionais de decisão que podem
ser resolvidos em tempo polinomial. N P é a classe dos problemas que podem ter uma
solução verificada em tempo polinomial. P SP ACE é a classe dos que podem ser resolvidos
com uma quantidade polinomial de armazenamento (memória). EXP T IM E é a classe
dos que podem ser resolvidos em tempo exponencial com expoente polinomial. RE (ou
Recursivamente Enumerável) é a classe dos problemas de decisão para os quais existe
um algoritmo que, dada uma instância sim, consegue determinar que a instância dada é
realmente sim. N EXP T IM E é a classe daqueles que podem ter uma solução verificada
em tempo exponencial de expoente polinomial.
Finalmente, o livro “Games, puzzles and Computation” [Hearn e Demaine, 2009]
obtém reduções polinomiais entre variantes desse jogo e vários outros jogos, como Sokoban e Rush-Hour. Com isso, obtém provas alternativas de complexidade computacional
(de acordo com a tabela acima, dependendo da variante utilizada na redução) para tais
jogos.
Existe uma conferência bienal, FUN (Fun with Algorithms), onde se concentram trabalhos de algoritmos e complexidade computacional voltados a jogos. No Capı́tulo 2,
apresentamos as definições e terminologia que servirão de base para o desenvolvimento
deste trabalho. No Capı́tulo 3, apresentamos nossos resultados sobre problemas inspirados
no jogo Bloxorz. No Capı́tulo 4, apresentamos nossos resultados sobre um problema inspirado no jogo On The Edge. No Capı́tulo 5, apresentamos nossa formulaçao de problemas
inspirados no jogo Bobbin 3D.
17
2 Conceitos Básicos
2.1 Grafos
Um grafo G é um par ordenado (V (G), E(G)) composto de um conjunto, não vazio, V (G)
de vértices e um conjunto E(G), disjunto de V (G), de arestas. Cada aresta é um par não
ordenado de vértices de G. Se o par (u, v) está em E(G), escreve-se uv ∈ E(G) e diz-se
que u e v são extremidades da aresta uv.
A denominação grafo vem do fato do mesmo poder ser representado graficamente, os
vértices como pontos e as arestas como linhas ligando suas extremidades. Dizemos que dois
vértices são adjacentes quando eles são extremidade de uma mesma aresta. De maneira
análoga duas arestas são adjacentes se compartilham uma extremidade. Uma aresta que
possui extremidades iguais é chamada laço. Duas arestas distintas com extremidades
iguais são chamadas de arestas múltiplas.
Um grafo G é finito se V (G) e E(G) são finitos. Um grafo G é dito simples se G é
finito, não possui laços e não possui arestas múltiplas. A partir de agora, toda vez que
mencionarmos grafo, estaremos nos referindo a um grafo simples.
O grau de um vértice v em G é o número de vértices que são adjacentes a v em G
e é denotado por dG (v). Se não houver ambiguidade denota-se apenas por d(v). O grau
máximo de um grafo G é o maior grau de um vértice de G e é denotado por ∆(G).
Um caminho é uma sequência não vazia W = v0 e1 v1 e2 v2 . . . ek vk na qual os termos
são alternadamente vértices e arestas, tais que, para 1 ≤ i 6= j ≤ k, ei = vi−1 vi . neste
caso v0 e vk são as extremidades de W. Um caminho com n vértices é denotado por Pn
e o comprimento de um caminho é o número de arestas que este possui. A distância
entre dois vértices u e v em um grafo G é o comprimento do menor caminho que possui
extremidades u e v em G.
Um caminho hamiltoniano W = v0 e1 v1 e2 v2 . . . ek vk de um grafo G é um caminho tal
que ∀v ∈ V (G), existe um único i tal que vi = v.
H é um subgrafo de G se G e H são grafos onde V (H) ⊆ V (G)) e E(H) ⊆ E(G).
Um subgrafo H de G é induzido se, caso u ∈ V (H) e v ∈ V (H), uv ∈ E(H) ⇔ uv ∈
E(G).
O produto cartesiano GH entre os grafos G e H é o grafo (V , E ) tal que V =
V (G) × V (H) e (u, u0 )(v, v 0 ) ∈ E se ocorre um dos seguintes:
• u = v e u0 v 0 ∈ E(H).
• u0 = v 0 e uv ∈ E(G).
Um grid é o produto cartesiano entre grafos correspondentes a um Pm e um Pn .
18
Capı́tulo 2. Conceitos Básicos
Um subgrafo induzido Gs de um grid qualquer é um grid sólido se Gs pode ser mapeado
no plano cartesiano de maneira que as arestas liguem pontos com distância 1 entre si e
as faces internas formadas possuam área 1.
Um grafo ponderado é uma generalização do conceito de grafo onde, além do par
(V, E), existe uma função w : E → R. O valor de w para uma aresta é conhecido como
seu peso. Em grafos ponderados, o comprimento, nesse caso geral conhecido como custo,
n−1
P
de um caminho Pn é
w(ei ).
i=1
Um grafo direcionado é uma alteração do conceito de grafo onde E(G), chamado
neste caso de conjunto de arcos, é um conjunto de pares ordenados, ou seja, o arco
(u, v) 6= (v, u). Em um grafo direcionado G, o vértice v é adjancente ao vértice u se
(u, v) ∈ E(G) e também se diz nesse caso que e sai de u.
19
3 Bloxorz
3.1 O problema
Bloxorz é um jogo eletrônico desenvolvido originalmente para a plataforma Flash pela
DX Interactive onde o jogador controla um paralelepı́pedo de dimensões na escala 2:1:1 e
deve levá-lo entre 2 pontos de um cenário. Embora a visualização implementada seja uma
projeção que dá noção de profundidade, a mecânica envolvida é totalmente bidimensional.
A Figura 1 exemplifica o que se pode esperar ver no jogo.
Figura 1 – Uma visão geral do jogo
O objetivo é fazer o bloco, ou seja, o paralelepı́pedo, cair no buraco, o que é equivalente
no caso a ser deixado em pé sobre ele, no final, que é ilustrado na Figura 2a, de cada fase.
O bloco, mostrado na Figura 2b, pode ser rolado para frente, para trás, para esquerda ou
para a direita, mas não pode sair dos limites do piso da fase. Caso isso aconteça, a fase
reinicia. As fases podem ter chaves e pontes como na Figura 2c. As chaves são ativadas
quando pressionadas pelo bloco. Pontes então podem mudar de estado e se manter no
novo estado, fechadas, por exemplo, mesmo se o bloco for movido. Existem 2 tipos
básicos de chaves: pesadas ou leves. As leves, representadas da Figura 2d pela circular,
são ativadas quando qualquer parte do bloco as pressiona. As pesadas, que aparecem
em forma de ”x”como na Figura 2d, são ativadas apenas se o bloco estiver em pé sobre
elas. Quando ativadas, as chaves podem apresentar diferentes comportamentos. Algumas
alternarão o estado de pontes entre fechada e aberta a cada uso (que serão chamadas de
alternates) e outras mudarão o estado de pontes permanentemente (que serão chamadas
de não-alternates). Ao longo do texto, esses estados das pontes serão também chamados
de ligada e desligada. Ligada se referindo a fechada, ou seja, permitindo passar. Piso de
madeira, ilustrado na Figura 2e, é mais frágil que o resto do cenário e, se o bloco ficar em
20
Capı́tulo 3. Bloxorz
(a) Final da fase
(b) Bloco
(e) Madeira
(c) Chave e ponte
(f) Teletransporte
(g) Bloco
queno
(d) Dois tipos de
chave
pe-
Figura 2 – Elementos de uma fase
pé em cima dele, ele irá cair, tirando o bloco dos limites do piso da fase. Também existem
nas fases as chaves especiais de teletransporte como a que aparece na Figura 2f, elas são
ativadas como chaves pesadas e teletransportam o bloco para 2 lugares diferentes e assim
o dividem em 2 blocos cúbicos menores, um para cada ponto do cenário. Eles podem ser
controlados individualmente e se tornam um bloco normal caso colocados um ao lado do
outro. Blocos pequenos como os da Figura 2g podem ativar chaves leves, mas não chaves
pesadas. Além disso, blocos pequenos não podem passar pelo buraco final da fase.
O problema computacional que é estudado neste capı́tulo procura traduzir a seguinte
pergunta:
Dada uma fase hipotética de Bloxorz, ou seja, uma construção arbitrária que respeite
as regras expostas acima sobre o que pode haver em uma fase do jogo, mas sem que se
considere possı́veis restrições práticas, memória por exemplo, existe uma sequência de
jogadas que leve o jogador a passar de fase?
Exemplos de soluções, ou seja, sequências de jogadas, para fases concretas do jogo
estão ilustrados nas Figuras 3 e 4.
Na figura 3, o número i > 1 marca um bloco que vem em sequida do marcado com
i − 1 na sequência, 1 marca o primeiro movimento, se i está entre 2 elementos, marca um
bloco deitado sobre eles 2 e se está centralizado sobre um elemento marca um bloco em
pé sobre ele.
3.2. Uma formulação matemática
21
Figura 3 – Curioso caso com pontes
Figura 4 – Passos até o final da fase
3.2 Uma formulação matemática
Definição 3.1. Sejam a e b números naturais positivos, A = {1, ..., a}, B = {1, ..., b},
conjuntos que representam os limites da fase,
I = {(teletransporte, x1 , y1 , x2 , y2 ) : x1 , x2 ∈ A e y1 , y2 ∈ B} e
J = {(chave, ((x1 , y1 ), ..., (xk , yk )), alt, peso) : x1 , ..., xk ∈ A, y1 , ..., yk ∈ B, alt, peso ∈
{0, 1}, k ∈ N e chave ∈ {1, ..., |A| ∗ |B|}}, uma fase do Bloxorz generalizado é uma função
f : A × B → T onde T = {∅, piso, madeira, inicial, f inal} ∪ I ∪ J tal que existem xi , yi , xf
e yf tais que sejam os únicos valores para os quais f (xi , yi ) = inicial e f (xf , yf ) = f inal,
22
Capı́tulo 3. Bloxorz
não existem (xc1 , yc1 ) e (xc2 , yc2 ) diferentes tais que f (xc1 , yc1 ) = (z, K1 , alt1 , peso1 ) e
f (xc2 , yc2 ) = (z, K2 , alt2 , peso2 ). Além disso, se f (x, y) = (z, K, alt, peso), z ∈ 1, ..., |J ∩ Im(f )|
e, se (xp , yp ) ∈ K, f (xp , yp ) = piso ou f (xp , yp ) = ∅. Essas últimas restrições sobre chaves
estabelecem uma numeração única e ”sem buracos”para cada uma e que elas operam sobre
posições vazias ou de piso.
Considere o algoritmo abaixo que tem como entrada a matriz f que representa uma
fase do Bloxorz generalizado como definido acima, xi e yi como definidos acima, o valor d
que representa a quantidade de posições (i, j) tais que f [i][j] ∈ J e o vetor S de elementos
de {↑, ↓, ←, →} e, como saı́da, ((x1 , y1 , x2 , y2 ), p), onde x1 , x2 ∈ A e y1 , y2 ∈ B, um par
formado pela situação final do bloco e quantos movimentos foram executados com sucesso.
A linguagem em que esse algoritmo está expresso não é bem definida, mas seus passos
são precisos para aqueles familiarizados com a semântica de linguagens de programação
e pseudocódigo de forma a corresponder a uma determinada máquina de Turing. Uma
observação é que a matriz deve representar uma fase válida, ou seja, atendendo todos os
requisitos da definição. Por exemplo, uma fase não pode ter dois finais ou ser desprovida
de final.
Esse algoritmo é análogo àquilo descrito anteriormente como as regras que definem
o resultado de sequências de comandos no Bloxorz e parte da definição de fase dada em
seguida.
O problema principal explorado neste capı́tulo, o BLOXORZ, é aquele onde, dada
uma fase f do Bloxorz generalizado, deseja-se saber se existe uma sequência S de elementos
de {↑, ↓, ←, →, } tal que |S| ≤ |f | e, se colocada como parte de uma entrada consistente
a com f para o algoritmo descrito, ele retorna ((xf , yf , xf , yf ), |S|).
3.3 Linguagem utilizada nas próximas demonstrações
Na Figura 5, são mostrados os sı́mbolos que representarão a estrutura de uma fase ou
conjunto de fases da forma como foi definido na seção anterior, cada uma representando
uma possibilidade para f (x, y) com a observação de que na verdade pontes abertas significam f (x, y) = ∅ e pontes fechadas significam f (x, y) = piso, o que identifica uma posição
como ponte é pertencer a algum ch2 onde ch ∈ J ∩ Im(f ). Na representação, abaixo de
todo tele ∈ I ∩ Im(f ) estarão indicados tele2 , tele3 , tele4 e tele5 e, abaixo de toda ponte,
os rótulos das chaves que satisfazem a condição que a torna uma ponte.
3.4 N P -completude do BLOXORZ
Nesta seção, trataremos do problema geral descrito nas seções 3.1 e 3.2. Mais especificamente, trataremos do problema de decisão que chamamos BLOXORZ, que pode ser
descrito alternativamente da forma a seguir:
3.4. N P -completude do BLOXORZ
Algoritmo 1 Mecanismos do Bloxorz
Entrada: f [l][a], xi , yi , d, S[s]
x1 , x2 , y1 , y2 := xi , xi , yi , yi
cubo := 0 chaves := [0] ∗ d
for i := 1, ..., s do
x3 , x4 , y3 , y4 := x1 , x2 , y1 , y2
x1 , x2 , y1 , y2 := rolarbloco(S[i], (x1 , x2 , y1 , y2 ), cubo)
if S[i] = then
if cubo = 1 then
cubo := 2
if cubo = 2 then
cubo := 1
i := i + 1
vá para a linha 5
if f [x1 ][y1 ] = ∅ or f [x2 ][y2 ] = ∅ then
x1 , y1 , x2 , y2 := x3 , y3 , x4 , y4
return ((x1 , y1 , x2 , y2 ), i − 1)
if f [x1 ][y1 ] = madeira and x1 = x2 e y1 = y2 then
O mesmo que o caso anterior
if |x1 − x2 | < 2 e |y1 − y2 | < 2 e (x1 = x2 ou y1 = y2 ) then
cubo := 0
if tamanho(f [x1 ][y1 ]) = 5 e x1 = x2 e y1 = y2 then
cubo := 1
tele := f [x1 ][y1 ]
x1 , x2 , y1 , y2 := tele[2], tele[3], tele[4], tele[5]
if tamanho(f [x1 ][y1 ]) = 4 and (f [x1 ][y1 ][3] = 0 or chaves[f [x1 ][y1 ][1]] = 0)
and ((x1 = x2 e y1 = y2 ) or f [x1 ][y1 ][4] = 0) then
pontes := f [x1 ][y1 ][2]
for j := 1, ..., tamanho(pontes) do
if pontes[j] = ∅ then
f [pontes[j]] := piso
if pontes[j] = piso then
f [pontes[j]] := ∅
chaves[f [x1 ][y1 ][1]] := ((chaves[f [x1 ][y1 ][1]) + 1) mod 2
end
else
if tamanho(f [x2 ][y2 ]) = 4 and (f [x2 ][y2 ][3] = 0 or chaves[f [x2 ][y2 ][1]] = 0)
e f [x2 ][y2 ][4] = 0 then
O mesmo que o caso anterior trocando x1 , y1 por x2 , y2 .
end
end
return ((x1 , y1 , x2 , y2 ), s)
23
24
Capı́tulo 3. Bloxorz
Rotina rolarbloco(direcao, posicao, cubo)
x1 , x2 , y1 , y2 := posicao[1], posicao[2], posicao[3], posicao[4]
if direcao =→ then
if cubo = 0 then
if x1 = x2 then
x1 := x1 + 1
if y1 = y2 then
x2 := x2 + 2
else
x2 := x2 + 1
end
else
x2 := x2 + 1
x1 := x1 + 2
end
if cubo = 1 then
x1 := x1 + 1
if cubo = 2 then
x2 := x2 + 1
if direcao =← then
mesmo que S[i] =→ trocando ’+’ por ’-’
if direcao =↑ then
mesmo que S[i] =→ trocando ’x’ por ’y’
if direcao =↓ then
mesmo que S[i] =↑ trocando ’+’ por ’-’
return (x1 , x2 , y1 , y2 )
(a) Piso
(e) Teletransporte
(b) Ponte fechada
(f) Chave
(c) Ponte aberta
(g) Inı́cio
Figura 5 – Elementos de uma fase
(d) Madeira
(h) Final
3.4. N P -completude do BLOXORZ
(a) Inı́cio
25
(b) Variável
(c) Cláusula
(d) Fim
Figura 6 – Engrenagens da redução
• Problema de Decisão BLOXORZ:
• Entrada: Uma fase f do Bloxorz generalizado.
• Pergunta: Existe uma sequência com no máximo |f | movimentos de modo que o
bloco, começando na posição inicial da fase f , chegue na posição final da fase f ?
O teorema abaixo prova a NP-Completude do problema de decisão BLOXORZ, mesmo
restrito a fases que não possuem teletransportes.
Teorema 3.1. SAT ≤p BLOXORZ.
Demonstração. Dada uma fórmula lógica ϕ na FNC (forma normal conjuntiva), vamos
construir uma fase do Bloxorz utilizando as engrenagens (gadgets) descritas abaixo. Essas
fórmulas são no formato ϕ = C1 ∧ C2 ∧ . . . ∧ Cn . Cada Cj é chamado de cláusula e é do
formato l1,j ∨ l2,j ∨ . . . ∨ lmj ,j onde cada li,j é chamado literal e é uma variável xi ou o
complemento xi de uma variável.
A Figura 6 ilustra a redução. Nela temos que as partes que compõem a fase construı́da
são colocadas uma imediatamente à direita da outra, primeiramente a engrenagem de
inı́cio, depois uma de variável para cada variável e finalmente, na linha central, uma de
cláusula para cada cláusula e o elemento de fim da fase na mesma linha das engrenagens
de cláusula. As chaves são leves e não-alternantes. A ponte da engrenagem de uma
cláusula Cj é ligada pela chave C2 da engrenagem de uma variável xi , se xi ∈ Cj , e é
ligada pela chave C5 da engrenagem de uma variável xi , se xi ∈ Cj . Observe que as
pontes superior e inferior de cada engrenagem de variável começam ligadas e que elas são
desligadas respectivamente pelas chaves C1 e C4 da engrenagem da mesma variável. Note
ainda que a ponte de cada engrenagem de cláusula começa desligada. Finalmente, observe
que, para conseguir chegar a posição final da fase, será preciso ligar todas as pontes das
engrenagens de cláusula.
26
Capı́tulo 3. Bloxorz
Suponha que a fórmula ϕ é satisfatı́vel. Ou seja, existe uma atribuição de valores
verdadeiro ou falso às variáveis de modo que todas as cláusulas sejam satisfeitas. Para
a fase construı́da para ϕ, existe uma sequência de movimentos que permite atravessar as
engrenagens de variável ativando as chaves correspondentes aos literais satisfeitos pela
valoração. Além disso, note que é impossı́vel obter uma sequência de movimentos que
ative as chaves C2 e C5 de uma mesma engrenagem de variável. Com isso, como a
valoração satisfaz a fórmula ϕ, então todas as pontes das engrenagens de cláusulas serão
ligadas e com isso será possı́vel chegar ao fim da fase. Adicionalmente, como a sequência
só tem movimentos para a direita, para cima e para baixo e, se há um movimento para
cima, não há para um para baixo na mesma coluna e vice-versa, ela não envolve posições
repetidas e portanto a sequência tem cardinalidade menor do que a fase.
Por outro lado, seja f (ϕ) a fase gerada pela redução em questão para a fórmula
ϕ na CNF. Se existe uma sequência-solução para a fase f (ϕ), existe uma sequência de
movimentos que liga todas as pontes das engrenagens de cláusula. Tal sequência atravessa
as engrenagens de variável ativando a chave de pelo menos um literal de cada cláusula
de ϕ. Além disso, como já dito, não é possı́vel ativar a chave C2 e C5 de uma mesma
engrenagem de variável em nenhuma sequência de movimentos sucessivos, pois, se a chave
C2 foi ativada, a chave C1 também foi ativada, pois, devido à ponte ativada pela chave
C3, não é possı́vel alcançá-la vindo da direita, e, como existe a chave C1, não é possı́vel
ativar a chave C2 e depois retornar à esquerda para ativar a chave C5. Um raciocinio
simétrico pode ser aplicado partindo de um literal negado. Portanto, ϕ é satisfatı́vel.
Lema 3.1. BLOXORZ ∈ N P
Demonstração. BLOXORZ é um problema de decisão e seu algoritmo verificador é avaliar se, dada uma fase do Bloxorz como entrada e dada uma sequência de movimentos
como certificado, esta sequência de movimentos leva o bloxo da posição inicial a posição
final da fase e se o número de movimentos é menor ou igual ao tamanho da fase. Como o
tamanho da sequência está limitado pelo tamanho da fase, isso pode ser feito em tempo
polinomial em relação à entrada.
Colorário: BLOXORZ é N P -completo.
Pode-se observar que o comportamento segue a tabela da Seção ??, já que temos um
quebra-cabeça de um jogador e adicionamos uma restrição sobre o número de passos.
Embora não exista aqui uma prova formal, pode-se conjeturar fortemente que tirando
essa restrição, o problema se encaixa em P SP ACE.
3.5 Inaproximabilidade
Nesta seção é considerada uma versão de otimização do problema BLOXORZ. Para isso,
precisamos receber como entrada uma fase que tenha sempre uma solução (uma sequência
3.5. Inaproximabilidade
27
de movimentos que leve o bloco da posição inicial até a posição final). Na definição abaixo,
usaremos a noção de fase desviável, que é basicamente uma fase generalizada F do Bloxorz
que admite uma sequência com no máximo |F | movimentos levando o bloco da posição
inicial até a final sem passar por chaves. Para delimitar esse problema, primeiro será feita
a seguinte definição:
Definição 3.2. Uma fase desviável de Bloxorz é uma fase f do Bloxorz generalizado
tal que existe um conjunto L de posições (x, y) tal que pode-se definir a fase g com um
domı́nio que englobe os valores de L, g(x, y) = f (x, y) se (x, y) ∈ L e g(x, y) = ∅ caso
contrário, não existe g(x, y) ∈ J e g é uma instância sim do BLOXORZ.
É fácil ver que, dada uma fase do Bloxorz generalizado, é possı́vel decidir se ela é
desviável ou não em tempo polinomial. Uma observação é que uma fase desviável f
de Bloxorz é uma instância sim do BLOXORZ, pois qualquer sequência-solução de g é
sequência solução de f .
A pergunta que define o problema de otimização MINBLOXORZ é: Dada uma fase f
desviável de Bloxorz, qual é o menor valor h = |S| onde S é uma sequência de movimentos
que levam o bloco da posição inicial até a posição final?
Teorema 3.2. Se existe um algoritmo n1−ε -aproximativo para M IN BLOXORZ para
algum ε > 0, então P = N P .
Figura 7 – Construção que indica inaproximabilidade
Demonstração. Vamos aplicar a conhecida técnica do gap em provas de inaproximabilidade. Suponha que existe um algoritmo polinomial aproximativo com fator n1−ε para
algum ε > 0, onde n é o tamanho da fase desviável, para o problema MINBLOXORZ.
Vamos utilizar a redução SAT ≤p BLOXORZ do Teorema 3.1. Dada uma fórmula
ϕ na CNF, seja F a fase obtida na redução do Teorema 3.1. Provou-se que, se ϕ é
satisfatı́vel, então existe uma sequência com no máximo |F | movimentos que levam o
bloco da posição inicial até a posição final da fase F .
Vamos alterar a fase F para que seja uma fase desviável. Acrescente à fase F um
“caminho externo” (ilustrado na Figura 7) de tamanho X = N 2/ε − N capaz de levar o
bloco da posição inicial até a posição final. Com isso, obtemos uma fase F 0 desviável de
tamanho |F 0 | = N + X = N 2/ε .
28
Capı́tulo 3. Bloxorz
Se ϕ é satisfatı́vel, então a fase F 0 possui uma sequência de movimentos de tamanho
no máximo N . Com isso, o algoritmo aproximativo obtém uma solução de tamanho
no máximo N · f ator = N · (|F 0 |1−ε ) = N · (N 2/ε )1−ε = N −1+2/ε < N 2/ε − N = X.
Logo o algoritmo aproximativo obtém uma solução de tamanho menor do que X e que
consequentemente não utiliza o “caminho externo” (pois este tem tamanho X). Ou seja,
o algoritmo obtém um caminho na fase original F .
Se ϕ não é satisfatı́vel, então o algoritmo aproximativo obtém uma solução de tamanho
pelo menos X.
Resumindo, ϕ é satisfatı́vel se e só se o algoritmo aproximativo retornar uma solução
de tamanho menor que X. Como o algoritmo aproximativo é polinomial, ele estaria
decidindo o problema SAT e portanto P=NP.
3.6 Bloxorz com restrições sobre chaves
Nesta seção lidamos com versões alternativas dos problemas anteriores onde se exclui
a possibilidade de fases com uma quantidade arbitrária de chaves que abrem e fecham
pontes.
Definição 3.3. k-BLOXORZ é a restrição do BLOXORZ onde consideramos instâncias
f cujo conjunto Im(f ) possui até k elementos em J.
Teorema 3.3. Existe um algoritmo de tempo de execução polinomial que decide kBLOXORZ.
Demonstração. Supondo a existência de um algoritmo de tempo de execução O(ab α(n))
para BLOXORZ restrito às devidas instâncias, onde a é uma constante qualquer, b é o
número de chaves da fase, α(n) é um polinômio em n e n é o número de elementos da fase,
esse é um algoritmo de execução polinomial para k-BLOXORZ. Basta então provar que
existe tal algoritmo, que será apresentado a seguir.
Esse algorı́tmo consiste em gerar um grafo direcionado a partir da fase e encontrar
um caminho nesse grafo que represente uma sequência-solução. O conjunto de vértices do
grafo é o conjunto de estados possı́veis das variáveis x1 , y1 , x2 , y2 no algoritmo que define
o BLOXORZ combinadas com as possibilidades para o vetor chaves e mais um vértice
z. Os arcos de peso 1 ligam dois vértices que podem ocorrer em iterações seguidas no laço
principal do algoritmo e os de peso 0 ligam aqueles onde (x1 , y1 , x2 , y2 ) = (xf , yf , xf , yf )
ao vértice z.
Encontrar uma solução para a fase que seja menor do que a própria fase é encontrar
um caminho de tal tamanho no grafo, pois cada elemento da sequência é processado em
uma iteração e cada iteração processa um elemento.
3.6. Bloxorz com restrições sobre chaves
29
Tal construção é uma abordagem trivial para o problema, pois parte dos estados do
algoritmo que o define e busca conexão entre dois estados. O próprio algoritmo definidor
do problema define também o procedimento para a construção das arestas neste algorimo.
Sobre a complexidade de tempo, é preciso avaliar o custo de construir os vértices, as
arestas e o de encontrar o caminho. Cada vértice ou arco pode ser contruı́do em tempo
O(1), pois cada arco é definido com um simples if do algoritmo. A quantidade de vértices
é 2b n2 , o número de maneiras válidas de valorar x1 , y1 , x2 ey2 multiplicado pelo número
de maneiras de valorar o vetor chaves. O número de arcos é proporcional ao número
de vértices, pois o número que sai de cada vértice é limitado por 2|{↑, ↓, ←, →}| = 8,
logo a geração do grafo tem o mesmo custo de tempo assintoticamente que o número de
vértices e que o algoritmo como um todo, já que para detectar o caminho, basta usar
um algoritmo de busca. Temos que o algoritmo desta demonstração executa em uma
quantidade de passos O(ab α(n)) onde a = 2, b é o número de chaves da fase e α(n) = n2 ,
logo esse é um algoritmo O(n2 ) para k-BLOXORZ.
Uma observação é que o algoritmo apresentado no teorema pode ser visto quase como
uma força bruta para o BLOXORZ, no entanto, ele traz a informação prática de que,
se o objetivo é operar sobre um conjunto de fases de Bloxorz onde o número de chaves é
muito pequeno, isso pode ser feito em tempo hábil. Muito pequeno pela exponencialidade
no pior caso em relação a um crescimento no número de chaves. Fazendo uma estimativa
inocente, provavelmente a partir de no máximo 60 chaves o algoritmo já seria totalmente
impraticável na tecnologia atual.
Definição 3.4. CLOSED-BLOXORZ é a restrição do BLOXORZ onde as pontes
apenas fecham e não há chaves de teletransporte.
Teorema 3.4. CLOSED-BLOXORZ ∈ P
Demonstração. Existe um algoritmo que executa em tempo polinomial em relação ao
número de elementos para esse problema. A seguir ele será explicado e pode ser visto
como uma versão do algoritmo para o k-BLOXORZ onde não é necessário considerar
todas as combinações de ativação das chaves. Aqui é suposto sem perda de generalidade
que a fase não possui pontes inicialmente fechadas, pois elas, se existissem, nunca seriam
abertas, o que as tornaria equivalentes a piso normal.
Ele consiste nos seguinte passos:
1. Gere um grafo como no algorimo para o k − BLOXORZ a partir da fase obtida da
original com a troca das chaves por piso normal e das pontes por posições vazias.
2. Execute uma busca em profundidade no grafo a partir do vértice do bloco inicial
para determinar se existe caminho até o buraco final
30
Capı́tulo 3. Bloxorz
3. Em caso positivo, retorne sim.
4. Armazene a informação sobre as chaves para as quais a busca alcança um bloco que
as ativaria em um vetor A.
5. Se A = ∅, retorne não.
6. Execute recursivamente este algoritmo para a fase obtida da original com a troca das
pontes que as chaves em A fechariam e das próprias chaves de A por piso normal.
Para atestar a completude/corretude desse algoritmo, pode-se considerar a do apresentado para o k-BLOXORZ e mapear as chamadas recursivas para as mudanças de
conjunto de vértices no referido algoritmo anterior com a observação de que, um bloco
alcançável a partir de uma sequência de movimentos em uma fase, pode ser alcançado na
de sua chamada recursiva replicando-se a sequência, já que as mudanças na fase adicionam
piso normal e apenas substituem por piso normal chaves que não possuiriam efeito em sua
ativação. Além disso deve-se considerar a condição que o algoritmo para o CLOSEDBLOXORZ utiliza para identificar uma instância não. Os casos onde não há caminho
até o buraco final desprezando-se a ativação das chaves e ao mesmo tempo não há chaves
ativáveis de forma a fechar novas pontes são precisamente as instâncias não.
Para atestar a polinomialidade do algoritmo, basta um cálculo de sua complexidade
de tempo. O número de chamadas recursivas é limitado pelo número de chaves, que por
sua vez é limitado pelo número total de elementos da fase, que aqui é chamado de n e
é o tamanho da entrada. Dentro de cada chamada recursiva, os únicos passos que não
podem ser feitos de forma que executem em tempo O(1) são 1 e 2. Os passos 1 e 2
podem ser executados em tempo total O(n), pois na fase modificada não há chaves ou
teletransporte, ou seja, há apenas uma possibilidade para o vetor e nenhum caminho entre
o vértice inicial e aqueles onde (x1 6= x2 e y1 6= y2 ) ou 2 ≤ |x1 − x2 | ou 2 ≤ |y1 − y2 |, esse
fato será explicado um pouco melhor na apresentação dos últimos algoritmos do capı́tulo.
Isso leva a uma complexidade total O(n) para cada chamada recursiva e O(n2 ) para o
algoritmo completo.
Definição 3.5. M IN -CLOSED-BLOXORZ é o problema com a mesma pergunta do
M IN -BLOXORZ, mas aplicada às instâncias sim do CLOSED − BLOXORZ. Observe que uma instância sim do CLOSED-BLOXORZ não é necessariamente uma fase
desviável.
Teorema 3.5. M IN -CLOSED-BLOXORZ é N P -difı́cil.
Demonstração. Suponha que existe um algoritmo de execução polinomial para o M IN CLOSED-BLOXORZ. Aqui será demonstrado que tal algoritmo decide SAT . Dada
3.6. Bloxorz com restrições sobre chaves
31
Figura 8 – Engrenagem de variável para o M IN -CLOSED-BLOXORZ
uma formula ϕ da lógica proposicional escrita na CNF, pode-se construir uma fase F de
Bloxorz como na redução do Teorema 3.1 que prova a NP-completude do BLOXORZ,
mas com as engrenagens de variável como na Figura 8. A largura de cada engrenagem
de variável tem tamanho kv (ilustrado na Figura 8), onde k = 30 e v é a quantidade
de variáveis em ϕ Na engrenagem ilustrada, as chaves estão relacionadas às engrenagens
de cláusula de forma análoga ao que foi apresentado na construção que provou a NPcompletude do BLOXORZ.
Note que a fase F construı́da dessa maneira é uma instância sim do CLOSED-BLOXORZ,
visto que o bloco pode ativar todas as chaves de cada engrenagem de variável e com isso
ligar todas as pontes relativas às cláusulas mesmo que ϕ não seja satisfatı́vel.
Note que, como cada engrenagem de variável tem largura 30v e que, a cada 2 movimentos na parte superior ou inferior, o bloco percorre 3 posições, então temos 20v movimentos
(na parte superior ou na parte inferior da engrenagem). Com isso, seja m a quantidade
de cláusulas na formula, o número de movimentos é maior que 20v 2 + 2m + 1, pois cada
engrenagem de cláusula precisa de 2 movimentos do bloco para percorrer suas 3 posições
e há ainda o último movimento para a posição final.
Observe que, se ϕ é satisfatı́vel, então existe uma sequência-solução onde, para cada
engrenagem de variável, o bloco percorre só a parte de cima ou só a parte de baixo da
engrenagem. Além disso, o número de movimentos é menor que (20v + 7) · v + 2m + 1,
pois a sequência-solução poderia, no final de cada engrenagem de variável, percorrer o
trecho que leva da parte superior até a inferior (ou vice-versa) para iniciar o percurso da
próxima engrenagem de variável.
Se ϕ não é satisfatı́vel, então, para poder chegar até a posição final, o bloco terá que
ativar as duas chaves de uma mesma engrenagem de variável. Com isso, seu percurso
teria um acréscimo de pelo menos metade de 20v movimentos do bloco (ou seja, 10v
32
Capı́tulo 3. Bloxorz
movimentos). Logo o bloco deve percorrer pelo menos 20v 2 + 2m + 1 + 10v > (20v +
7) · v + 2m + 1.
Resumindo, ϕ é satisfatı́vel se e só existe uma solução de tamanho menor ou igual
a (20v + 7) · v + 2m + 1. Como existe um algoritmo polinomial para MIN-CLOSEDBLOXORZ, então P=NP.
Definição 3.6. CLOSED-BLOXORZ + é a restrição do BLOXORZ onde não há chaves que abram pontes.
Teorema 3.6. CLOSED-BLOXORZ + é N P -completo.
Figura 9 – Engrenagem de variável para o CLOSED-BLOXORZ +
Demonstração. Analogamente à redução que provou a N P -completude do BLOXORZ, a
partir de qualquer fórmula da lógica proposicional na CNF, pode-se construir uma fase
do Bloxorz generalizado onde a engrenagem de variável é como na Figura 9. A demonstração de completude/corretude da redução segue análoga à citada observando-se que a
sequência-solução construı́da a partir da valoração será muito semelhante. No inı́cio de
cada engrenagem de variável, existem dois teletransportes que podem ser alcançados pelo
bloco. Se o bloco utiliza o teletransporte da parte superior, ele irá então ter acesso apenas
a parte superior da engrenagem dessa variável. Se o bloco utiliza o teletransporte da parte
inferior, ele irá então ter acesso apenas a parte inferior da engrenagem dessa variável. Os
números indicados em cada teletransporte são as duas coordenadas para onde as duas
metades do bloco são levadas. Dentro de uma engrenagem de variável, um teletransporte
será ativado, o que leva x1 ao valor referido como 2 na imagem e y1 a 0 ou 6, esses valores são coordenadas relativas que fazem sentido dentro da engrenagem, mas que podem
assumir diversos valores efetivos dentro da fase dependendo da posição da engrenagem, o
3.7. O BLOXORZ −−
33
(0, 0) dela. Além disso, a variável cubo assumirá o valor 1, gerando o caso especial onde o
bloco está em um estado onde poderia mover-se segundo a mecânica de quando cubo = 0,
mas o algoritmo não levará a isso na próxima iteração. O movimento seguinte sendo para
a direita, o bloco mudará para um em pé em (3,0) ou (3, 6). Mais um movimento para
a direita e a chave C1 ou C3 será ativada, fechando a ponte das engrenagens de cláusula
devidas, mais um e a chave C2 ou C4 será ativada, fechando a ponte alterada por essa
chave, o que permite seguir até a próxima engrenagem. Finalmente, deve-se observar que
o mesmo mecanismo que impede movimentos de retorno à esquerda de forma a ativar C1
e C3 no mesmo literal, existem nesta redução pois o teletransporte impede o retorno de
forma análoga à ponte que correspondia a ele na redução original.
Considerando o problema onde, a partir do CLOSED-BLOXORZ + , restringimos as
instâncias aos casos onde há um número limitado de teletransportes, pode-se conjeturar
fortemente que tal problema pertence a P , pois é possı́vel resolvê-lo analizando todas as
escolhas possı́veis de teletransportes entre o conjunto dos existentes da fase e, para cada
um deles, recorrer à estratégia do algoritmo para o CLOSED-BLOXORZ.
3.7 O BLOXORZ −−
Definição 3.7. O BLOXORZ −− é o BLOXORZ restrito às instâncias sem chaves ou
teletransporte.
Esse na verdade foi o primeiro problema resolvido na produção deste trabalho e o
algoritmo que concebemos para resolvê-lo é uma restrição daquele mostrado para o k −
BLOXORZ.A consideração especial a ser feita é sobre o número de vértices do grafo.
Dada uma fase f do Bloxorz generalizado com as restrições descritas, o grafo Gf a ser
contruı́do no algoritmo será bem mais simples e visualizável do que no k − BLOXORZ
de forma geral, pois só há um estado de chaves e não há teletransporte, logo o conjunto
V (G) terá tamanho proporcional ao da fase. Vértices onde (x1 , y1 ) é distante de (x2 , y2 )
poderiam ser criados, mas não haveria caminho do vértice inicial até ele. Adicionalmente,
para cada elemento de madeira, um vértice pode ser eliminado, aquele onde (x1 , y1 ) =
(x2 , y2 ) = (xm , ym ) onde (xm , ym ) é a posição desse elemento, pois o algoritmo verificador
retorna imediatamente caso o bloco esteja em pé sobre tal posição e portanto os caminhos
que correspondem a uma solução não incluem tal vértice. Finalmente pode-se observar
que neste problema a direcionalidade dos arcos pode ser descartada, já que todos os
movimentos que não envolvem ativação de chaves ou teletransporte são reversı́veis com
outro no sentido oposto.
Teorema 3.7. Seja Gf o grafo gerado a partir da fase do Bloxorz generalizado f pelo
algoritmo em questão, |V (Gf )| ≤ 3n onde n = |f |.
34
Capı́tulo 3. Bloxorz
Figura 10 – Caminho-solução para BLOXORZ −−
Demonstração. GF possui um vértice para cada elemento de Bloxorz que não seja madeira
presente em F . Como F possui n elementos, seja Ve o conjunto de vértices desse tipo,
|Ve | ≤ n. O restante dos vértices de GF corresponde a pares de elementos vizinhos. Cada
elemento possui no máximo 4 vizinhos, 2 na horizontal e 2 na vertical. Se percorrermos os
elementos a partir do canto inferior esquerdo, encontraremos como o inicial, pois se trata
de um elemento o mais abaixo e o mais à esquerda possı́vel, um elemento com no máximo
2 vizinhos. Então temos no máximo 2 pares de vizinhos envolvendo o elemento inicial e
portanto no máximo 2 vértices correspondentes. Seguindo à direita na linha, adicionamos
no máximo mais 2 vértices para cada elemento, um por seu vizinho da direita e outro por
seu vizinho de cima, pois se trata da linha mais abaixo e o vizinho da esquerda forma
um par já considerado quando ele foi percorrido. Ao seguirmos para a linha superior,
os vértices que seriam adicionados pelo vizinho de baixo de cada elemento não o são
porque já o foram quando esses vizinhos foram percorridos. Assim, indutivamente, seja
Vp o conjunto de vértices desse tipo, |Vp | ≤ 2n. Como V (GF ) = Ve ∪ Vp , |V (GF )| ≤
|Ve | + |Vp | ≤ n + 2n = 3n.
Teorema 3.8. Sejam f uma instância do BLOXORZ −− e Gf o grafo gerado pelo algoritmo em questão para f , existe um caminho em Gf entre os vértices vi e vf , correspondentes respectivamente ao bloco inicial de I e ao final da fase, se e somente se a resposta
de I é sim.
Demonstração. (←)
Se f é uma instância com resposta sim, possui uma sequência-solução. Dada uma
sequência-solução de Bloxorz para f , há uma sequência de blocos B correspondente que,
3.7. O BLOXORZ −−
35
por ser extraı́da de uma sequência-solução, se inicia com o bloco inicial de f , é tal que 2
blocos seguidos nela são tais que um é resultado de um movimento válido sobre o outro,
termina com um bloco em pé no final da fase de f e não possui nenhum bloco em pé
ocupando piso de madeira. Pelas propriedades de B e pela construção de Gf , todo par
de blocos seguidos de B tem os vértices correspondentes adjacentes. Indutivamente, todo
vértice com correspondente em B é alcançado por arestas a partir de vi e portanto vf é
alcançado. Percorrendo B eliminando o que há entre as ocorrências de um mesmo bloco
e deixando apenas uma, constrói-se um caminho entre vi e vf .
(→)
Se existe um caminho entre vi e vf em Gf , pela definição de caminho existe uma
sequência que alterna vértices e arestas sem repetição, começa com vi , termina com vf e
a aresta (u, v) é a única que pode aparecer imediatamente entre 2 vértices u e v quaisquer
nela. Cada vértice corresponde a um bloco e, pela definição de Gf , se uv ∈ E(Gf ), u
e v correspondem a blocos tais que um resulta de um movimento válido sobre o outro.
Logo, indutivamente, o buraco final de I é alcançado por uma sequência de movimentos
válidos a partir do bloco correspondente a vi sem que exista nessa sequência um bloco em
pé sobre madeira, pois não existe nenhum vértice correspondente a esses blocos, logo f é
uma instância com resposta sim.
Combinando os dois teoremas, conclui-se que, para decidir o BLOXORZ −− em tempo
polinomial em relação ao tamanho da instância, basta decidir se existe um caminho entre
2 vértices de um grafo qualquer em tempo polinomial em relação a seu número de vértices.
Para esse fim, um algoritmo de busca em largura ou profundiade é o suficiente. Logo a
argumentação está completa.
Sendo mais preciso em relação à complexidade de tempo, é possı́vel construir o grafo em
tempo O(n) no pior caso, onde n é o número de elementos da fase do Bloxorz generalizado,
pois são no máximo 3n vértices e 6n arestas por um raciocı́nio análogo ao do primeiro
teorema e é possı́vel contruir cada aresta em tempo constante bastando uma checagem das
posições que o bloco gerado pelo movimento ocuparia. Um algoritmo de busca executa em
tempo O(|V | + |E|), o que no caso significa O(n). Já o algoritmo para encontrar o menor
caminho como em [?] executa em tempo O(|E| + |V |log(|V |)), ou seja, O(n + nlog(n)) =
O(nlog(n)), se usadas as devidas estruturas de dados e portanto nosso algoritmo para o
BLOXORZ −− executa em tempo O(nlog(n)) com a troca da busca pelo algoritmo de
menor caminho.
Uma observaçao importante é que esse algoritmo, além de resolver o problema, encontra, com a substituição mencionada, se houver, a menor sequência-solução para a fase
do Bloxorz generalizado dada como entrada, o que resolve uma versão de otimização do
problema.
36
Capı́tulo 3. Bloxorz
3.8 O BLOXORZ −
Nesta seção, o foco é o caso onde não há pontes, mas pode existir teletransporte além de
todos os elementos do BLOXORZ −− , chamaremos esse novo problema de BLOXORX − .
Para resolvê-lo, basta recorrer ao algoritmo apresentado para o k-BLOXORZ considerando apenas x1 , y1 , x2 , y2 , pois não há chaves.
O vértice final a ser considerado é aquele onde (x1 , y1 ) = (x2 , y2 ) = (xf , yf ), então não
existirão os arcos de peso 0.
.
37
4 On The Edge
4.1 O problema
O tópico deste capı́tulo é um novo problema extraı́do de um jogo semelhante ao Bloxorz,
na verdade inspirado nele, mas com diferenças importantes. On The Edge é um jogo
eletrônico desenvolvido para a plataforma Flash pela Yzi Games onde o jogador controla
um cubo. A Figura 11 exemplifica o que pode-se esperar ver no jogo:
Figura 11 – Uma visão geral do jogo
O objetivo é fazer o bloco, ou seja, o cubo, alcançar a posição vermelha no final de
cada fase após eliminados todos os elementos restantes. O bloco pode ser rolado para
frente, para trás, para esquerda ou para a direita, mas não pode sair dos limites do piso
da fase. Caso isso aconteça, a fase reinicia.
Caso o bloco esteja sobre piso normal, ao ser rolado para outra posição, o piso que ele
ocupava é eliminado. Em uma fase de On The Edge pode haver posições pretas, que não
sofrem esse efeito, mas tornam-se piso normal, e 0 ou 2 posições azuis, que levam o bloco
à outra posição azul e são eliminadas após esse efeito, a que foi ativada o é imediatamente
e a posição alvo após ser abandonada.
O problema computacional que é estudado neste capı́tulo, que chamaremos de ON T HE-EDGE, corresponde à seguinte pergunta:
Dada uma fase hipotética de On The Edge, ou seja, uma construção arbitrária que
respeite as regras expostas acima sobre o que pode haver em uma fase do jogo, mas sem
que se considere possı́veis restrições práticas, existe uma sequência de jogadas que leve o
jogador a passar de fase?
Um exemblo de 2 soluções possı́veis para uma mesma instância de ON -T HE-EDGE,
ou seja, ambas significariam uma resposta sim, está ilustrado na Figura 12. Trata-se de
uma fase concreta do jogo implementado.
38
Capı́tulo 4. On The Edge
(a) Possibilidade 1
(b) Possibilidade 2
Figura 12 – Mesma fase, dois caminhos
4.2 N P -completude
Nosso resultado sobre o ON -T HE-EDGE se refere a sua relação com um problema em
grafos. Especificamente com o problema de decidir se um subgrafo induzido de um grid
possui um caminho hamiltoniano entre os vértices u e v. Chamaremos esse problema
aqui de HP SU BGRID . Sobre o HP SU BGRID , em 1982, A. Itai, C. H. Papadimitriou e J.
L. Szwarcfiter demonstraram sua N P -completude. [Itai et al., 1982]
Teorema 4.1. HP SU BGRID ≤p ON -T HE-EDGE.
Demonstração. Dado um subgrafo H induzido de um grid, pode-se construir uma fase de
nosso On The Edge generalizado como na Figura 13.
Na Figura 13, em azul escuro e verde está representado o grafo H. Os vértices em
verde são aqueles entre os quais se deseja verificar a presença de um caminho hamiltoniano.
Em cinza está representado o piso normal da fase, em azul claro as posições azuis e em
vermelho o final da fase. A posição inicial corresponde ao retângulo cinza onde está um
dos vértices em verde. Na fase gerada, sempre existe a região correspondente aos vértices
do grafo e a região separada, ou seja, inalcançável a partir da primeira sem o efeito de
uma posição azul, com uma posição azul e imediatamente à direita o final.
4.2. N P -completude
39
Figura 13 – Redução do problema do caminho hamiltoniano em subgrafos induzidos de
grids
Se existe um caminho hamiltoniano entre u e v em H, existe uma sequência de movimentos que passa por cada posição relacionada a piso normal na fase construı́da uma
única vez e alcança a posição azul da região onde elas se encontram, pois cada movimento
válido nessa região corresponde a uma aresta de H, u corresponde à posição inicial e v à
posição azul. Além disso, ao alcançar a posição azul, pode-se continuar os movimentos
a partir da outra, agora com a primeira eliminada. Basta um movimento a mais para a
direita e o final é alcançado com todos os outros elementos da fase eliminados.
Por outro lado, se existe uma sequência de movimentos válidos que alcança o final
da fase com todos os outros elementos eliminados, existe uma que alcança a posição azul
logo à esquerda dele já eliminados todos os elementos diferentes desses 2, pois não existem
outros elementos vizinhos ao final, logo há uma terceira sequência que alcança a outra
posiçao azul e elimina todo o piso normal já que elas se encontram em regiões separadas
entre si. Essa sequência por suas propriadades passa por cada posição correspondente
a piso normal uma única vez. Como essas posições correspondem também a vértices do
grafo original e os movimentos válidos a arestas, a sequência pode ser mapeada para um
caminho hamiltoniano em H.
41
5 Bobbin 3D
5.1 O problema
Bobbin 3D é um jogo semelhante ao Bloxorz desenvolvido pela Maplabs para o sistema
Android. Nele o bloco a ser levado entre 2 pontos do cenário é um cilindro de altura 1 e raio
1
. Apesar de trazer uma impressão ainda maior que os anteriores de tridimensionalidade,
2
a mecânica continua sendo bidimensional. A Figura 14 exemplifica o que pode-se esperar
ver no jogo:
Figura 14 – Uma visão geral do jogo
O objetivo é rolar o cilindro a partir da posição inicial até que ele fique em pé sobre
o buraco final. O bloco pode ser rolado para frente, para trás, para esquerda ou para
a direita. Com a justificativa geométrica de o bloco ser um cilindro, rolar não significa
sempre um movimento restrito a uma vizinhança limitada pelas dimensões do objeto. Se
o bloco está deitado e é rolado de forma a se manter deitado, o bloco resultante ocupa
somente posição anterior ao primeiro obstáculo presente na linha ou coluna.
Em uma fase de Bobbin 3D, pode haver piso normal e piso elevado, que serve de
obstáculo quando o bloco rola. Também pode haver uma quantidade par de chaves ’+’
elevadas ou abaixadas, que, quando elevadas, funcionam como o piso elevado e quando
abaixadas alternam o estado de outra chave ’+’ pré-definida entre elevada e abaixada.
Se uma chave ’+’ alterna o estado de outra, essa outra alterna o estado dela. Além
disso, podem existir posições ’*’ que transformam o bloco cilı́ndrico em cúbico por uma
quantidade determinada de movimentos. Um bloco cúbico ocupa uma única posição e
42
Capı́tulo 5. Bobbin 3D
pode ser rolado nas mesmas 4 direções, mas sempre no máximo até uma posição vizinha.
Figura 15 – Passos em fase do Bobbin 3D
O problema computacional que é estudado neste capı́tulo, que chamaremos de BOBBIN ,
corresponde à seguinte pergunta:
Dada uma fase hipotética de Bobbin 3D, ou seja, uma construção arbitrária que respeite as regras expostas acima sobre o que pode haver em uma fase do jogo, mas sem que
se considere possı́veis restrições práticas, existe uma sequência de jogadas menor do que
a fase que leve o jogador a passar de fase?
A Figura 15 ilustra um exemplo de solução para uma fase concreta do jogo.
Uma observação é que pode-se ser construı́do para esse jogo um algorimo semelhante
ao do capı́tulo anterior com o objetivo de formalizar as regras dos movimentos e consequentemente delimitar melhor o problema.
Definição 5.1. BOBBIN −− é a restrição do BOBBIN de forma que não haja chaves
’+’ ou posições ’*’
Definição 5.2. BOBBIN − é a restrição do BOBBIN de forma que não haja chaves
’+’.
5.2. Linguagem a ser utilizada a seguir
(a) Piso
(b) Piso elevado
(e) Inı́cio
43
(c) Chave +
(d) Chave + elevada
(f) Final
Figura 16 – Elementos de uma fase
5.2 Linguagem a ser utilizada a seguir
Esta seção se refere ao formato visual que descreverá as construções apresentadas. Na
Figura 16 temos uma representação para cada tipo de elemento de forma similar ao que
foi feito para o Bloxorz.
Cada chave ’+’ em estado normal tem indicada a posição de seu par, as elevadas não
precisam, pois pode-se supor sem perda de generalidade que são pareadas cada uma com
uma em estado normal que a indica. Se uma fase possui um par de chaves ’+’ inicialmente
elevadas, pode-se trocar por um par de elementos de piso elevado.
5.3 Algoritmo para o BOBBIN −−
Para as instâncias deste problema, pode-se aplicar a mesma estratégia de nosso algoritmo
para o BLOXORZ −− , mas considerando um grafo direcionado como ilustrado na Figura
17.
Diferentemente do caso do BLOXORZ −− , cada posição possui 3 vértices diferentes
correspondentes. Pode-se excluir aquelas de piso elevado nesse sentido. No algoritmo
definidor, isso significaria uma variável a mais marcando o estado do bloco entre deitado
horizontalmente, deitado verticalmente ou em pé.
Cada arco representa um movimento válido possı́vel na fase hipotética de Bobbin 3D,
incluindo aqueles onde o bloco ”rola”, já que haverá um arco ligando o bloco deitado a
outro também deitado, mas na posição anterior no devido eixo ao elemento elevado mais
próximo. Além disso, neste algoritmo, a posição final é representada por um vértice e o
caminho mı́nimo a ser buscado é do bloco inicial, aqui o conjunto de vértices do grafo é
44
Capı́tulo 5. Bobbin 3D
um conjunto de blocos, a esse vértice, que é o bloco em pé sobre a posição final.
Com essas observações, o argumento de corretude/completude é o mesmo do algoritmo
que decide o BLOXORZ −− .
Figura 17 – Resolvendo um caso simples
5.4 Algoritmo para o BOBBIN −
Para as instâncias deste problema, pode-se aplicar uma estratégia similar a nosso algoritmo para o BLOXORZ − . Saindo dos vértices correspondentes às posições ’*’, vale
observar que há 3 deles para casa posição ’*’, há arcos que os ligam a vértices correspondentes a uma situação marcada por uma nova variável, situação onde os movimentos
respeitam o padrão dos cubos isolados do Bloxorz considerando que um movimento do
cubo é uma rotação do cilindro resultante no fim do processo. Na condição de existir
um caminho onde se esgota a quantidade de movimentos que a posição ’*’ em particular
permite, os arcos ligarão o vértice onde isso acontece de volta à região do grafo onde se
mostram as regras de movimento do bloco cilı́ndrico. Vale ressaltar a unidirecionalidade
dos arcos que entram e saem da dita ”região do cubo”. Os caminhos encontrados podem
eventualmente não refletir uma sequência válida no caso de saı́rem da ”região do cubo”,
que pode ser imaginada como uma camada extra do grafo sobre a fase, no número errado
de passos, mas esse caminho indica ainda assim a existência da sequência válida. Para
a construção da ”região do cubo”no grafo, é necessário registrar todas as formas de se
mover a partir da devida posição no estado de cubo pela dada quantidade de passos, o que
teria custo potencialmente exponencial se feito utilizando força bruta, uma alternativa é
5.5. BOBBIN
(a) Parte
inicial
45
(b) Para cada variável
(c) Para
cada
cláusula
Figura 18 – Engrenagens da redução
recorrer a uma estratégia de programação dinânica onde regitra-se as subsequências de
tamanho k e adiciona-se um movimento para obter as de tamanho k + 1. Essa construção será o passo mais custoso do algoritmo e demandará, seja n o tamanho da fase,
até n − 2 tabelas com n valores demarcando o número de passos como cubo necessários
para alcançar um dado elemento a partir da posição ’*’ em questão. Ou seja o custo total
de tempo é O(n2 ).
5.5 BOBBIN
Teorema 5.1. SAT ≤p BOBBIN
Demonstração. Dada uma fórmula da lógica proposicional na CNF, pode-se construir uma
fase hipotética do Bobbin 3D como na Figura 18. Nela, são mostradas as engrenagens
da construção analogamente ao feito com o BLOXORZ, mas esta exige mais cuidado na
análise.
O pareamento das chaves ’+’ , que não fica totalmente explı́cito, é o seguinte: se uma
chave ’+’ é da região correspondente a um literal e não possui par na própria, seu par
é uma chave ’+’ elevada presente na engrenagem de cláusula de uma daquelas onde o
literal aparece. ’ ?’ se refere a uma coluna especı́fica cujo valor depende de quantas vezes
o literal mais frequente envolvendo a variável aparece na fórmula. Pela necessidade de
simetria na construção e pela necessidade de manter a paridade da sequência de chaves,
deve-se preencher as potenciais posições faltantes com piso normal. Além disso, deve-se
considerar o encaixe das engrenagens. As unidades mais à esquerda de piso normal da
primeira engrenagem de variável ficam na mesma altura das mais à direita da engrenagem
de inı́cio. As engrenagens de variável são encaixadas em altura igual uma à direita da
46
Capı́tulo 5. Bobbin 3D
outra. A primeira engrenagem de cláusula é encaixada à direita da última de variável
na linha mais abaixo que possui piso normal. À direita das engrenagens de cláusula, na
mesma linha de uma chave ’+’, será encaixado o buraco final.
Se a fórmula é satisfatı́vel, a sequência de movimentos correspondente a passar pelas
engrenagens de variável ativando chaves ’+’ da correspondentes ao literais satisfeitos por
uma valoração que satisfaz a fórmula descreve uma sequência-solução para a fase, pois ao
ativar essas chaves, seus pares nas engrenagens de cláusula serão abaixados permitindo
a passagem do cilindro. Como toda cláusula tem um literal satisfeito pela valoração,
todas as engrenagens de cláusula possuem uma chave ’+’ que será abaixada tornando isso
verdade, permitindo que o cilindro alcance o buraco final. Resta observar que é possı́vel
passar pelas engrenagens de variável da forma descrita, pois, com a construção possuindo
o número adequado de elementos de piso normal, o cilindro pode ser rolado até ficar
deitado sobre o piso na mesma coluna que a posição elevada esquerda da construção para
o literal e então com um movimento ”bater”na posição elevada para em seguida ativar
as chaves. Além disso, o cilindro pode passar pela chave elevada da construção para o
literal, pois seu par está imediatamente à esquerda. Ou seja, a fase é uma instância sim
do BOBBIN .
Por outro lado, se a fase contruı́da é uma instância sim do BOBBIN , existe uma
sequência-solução para ela, ou seja, o buraco final pode ser alcançado, o que implica
que pelo menos uma chave ’+’ de cada engrenagem de cláusula pode ser abaixada, ou
seja, é possı́vel passar pelas engrenagens de variável ativando as chaves correspondentes
a pelo menos um literal de cada cláusula sem ativar chaves correspondentes a literais
contraditórios entre si, pois, a partir de um bloco alcançável a partir de movimentos
válidos que esteja na região de um literal, não é possı́vel ir até a região da negação desse
literal nem pela esquerda, pois uma sequência de movimentos para esquerda enquanto
válidos leva a um bloco deitado na horizontal, e nem pela direita, pois, após abaixar
a chave ’+’ na extrema direita da engrenagem de variável e abandoná-la, a chave ’+’
que abaixaria a chave elevada da região da negação do literal não pode ser alcançada.
Conclui-se que a fórmula é satisfatı́vel.
47
6 Tabela de problemas
Abaixo mostramos uma tabela
cidos neste trabalho.
Problema
BLOXORZ −−
BLOXORZ −
BLOXORZ
k-BLOXORZ
CLOSED-BLOXORZ
CLOSED-BLOXORZ +
ON -T HE-EDGE
BOBBIN −−
BOBBIN −
BOBBIN
com um resumo dos resultados de complexidade estabeleDecisão
O(n)
O(n2 )
N P -completo
O(n2 )
O(n2 )
N P -completo
N P -completo
O(n)
O(n2 )
N P -completo
Min
O(nlog(n))
O(n2 log(n))
inaprox n1−
O(n2 log(n))
N P -difı́cil
N P -difı́cil
N P -difı́cil
O(nlog(n))
O(n2 log(n))
N P -difı́cil
49
Referências
G. Aloupis, E. D. Demaine e A. Guo, Classic Nintendo Games are (NP)-Hard,
hhttp : //arxiv.org/abs/1203.1895i (2012).
E. D. Demaine, S. Hohenberger e D. Liben-Nowell,Tetris is Hard, Even to Approximate,
International Journal of Computational Geometry and Applications 14:1-2 (2004) 41–68.
E. D. Demaine, M. L. Demaine e R. Fleisher, Solitaire Clobber, Theoretical Computer
Science 313:3 (2004) 325–338
E.D. Demaine, M. L. Demaine, A. Langerman e Stefan Langerman, Morpion Solitaire,
Theory of Computing Systems 39:3 (2006) 439–453
E. D. Demaine e M. L. Demaine, Jigsaw Puzzles, Edge Matching and Polyomino
Packing: Connections and Complexity, Graphs and Combinatorics 23 (Supplement)
(2007) 195–208
E.W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische
Mathematlk 1(1959) 269–271.
D. Dor e U. Zwick, SOKOBAN and other motion planning problems,Computational
Geometry: Theory and Applications - COMGEO, vol. 13, no. 4 (1999) 215–228.
G. W. Flake e E. B. Baum, Rush Hour is PSPACE-complete or ’Why You Should
Generously Tip Parking Lot Attendants’, Theoretical Computer Science 270:1-2 (2002),
895–911
A. S. Fraenkel e E. Goldschmidt, PSPACE-Hardness of Some Combinatorial Games,
Journal of Combinatorial Theory, Series A 46 (1987), 21 – 38
R. A. Hearn e E. D. Demaine, PSPACE-Completeness of Sliding-Block Puzzles
and Other Problems through the Nondeterministic Constraint Logic Model of
Computation, Theoretical Computer Science, ”Game Theory Meets Theoretical
Computer Science”Special Issue, 343:1-2 (2005) 72–96
R. A. Hearn e E. D. Demaine, Games, Puzzles & Computation (2009), Editora AKPeters.
A. Itai, C. H. Papadimitriou e J. L. Szwarcfiter, Hamilton Paths in Grid Graphs, Society
for Industrial and Applied Mathematics Journal on Computing - SICOMP, vol. 11, no.
4 (1982)