No fim do ano passado o meu Nintendo DS quebrou, após anos de bons serviços prestados. Eu pensei em consertar, mas dado que o Nintendo 3DS ia sair em março, achei que valia a pena simplesmente esperar. Porém, o que fazer nesse meio tempo?
A minha solução foi ir à banca e comprar um punhado de cruzadinhas da Coquetel. No começo foi divertido, mas depois de algum tempo perdeu a graça: para quem está acostumado com a Denksel, os puzzles da Coquetel são fáceis demais.
Para aumentar a dificuldade dos puzzles, eu resolvi mudar as regras de alguns deles. A minha modificação predileta eu batizei de Torto Reverso. Antes de mostrar como funciona a minha variação, vamos relembrar as regras do Torto tradicional, tais como estão na revista. É dado um grid 3x6 de letras e a seguinte descrição:
"Deve-se formar as palavras seguindo em todas as direções, sempre ligando as letras em seqüência direta, sem cruzar, sem pular e sem repetir a mesma letra (para que uma palavra tenha a mesma letra repetida, é necessário que esta letra também esteja duplicada no diagrama). Damos como exemplo uma palavra encontrada. Só valem palavras de cinco letras ou mais. Na solução, constam 30 palavras formadas com este diagrama."
Depois de fazer alguns desses na mão, eu fiquei com vontade de implementar um solver. Eu poderia ter feito um solver em C++ ou Python, mas pensei aqui comigo: "eis uma boa oportunidade para aprender Prolog!"
Se você também não conhece Prolog, então acompanhe um pequeno tutorial antes de ver minha implementação do solver:
Para aumentar a dificuldade dos puzzles, eu resolvi mudar as regras de alguns deles. A minha modificação predileta eu batizei de Torto Reverso. Antes de mostrar como funciona a minha variação, vamos relembrar as regras do Torto tradicional, tais como estão na revista. É dado um grid 3x6 de letras e a seguinte descrição:
Se você tiver um bom vocabulário, esse puzzle não tem segredo. Muito mais difícil é o Torto Reverso: e se, ao invés de procurar palavras no grid, eu te der as palavras e pedir para achar um grid válido que contenha todas elas?
Depois de fazer alguns desses na mão, eu fiquei com vontade de implementar um solver. Eu poderia ter feito um solver em C++ ou Python, mas pensei aqui comigo: "eis uma boa oportunidade para aprender Prolog!"
Se você também não conhece Prolog, então acompanhe um pequeno tutorial antes de ver minha implementação do solver:
Introdução ao Prolog
Em linguagens de programação tradicionais, a metáfora que você usa para explicar é a da receita de bolo: programar é fazer uma seqüência de tarefas, como adicionar 200g de farinha e mexer até que a massa esteja consistente. Prolog usa um paradigma diferente, então a melhor metáfora é pensar que ele é um provador de teoremas: você entra com os axiomas e ele deriva os teoremas a partir deles.
Por exemplo, podemos usar o Prolog para definir os axiomas de Peano. Começamos com a definição de números naturais: zero é um número natural, e o sucessor de um natural também é um natural.
Com essas definições já podemos perguntar ao Prolog: será que 2, ou seja, o sucessor do sucessor do zero, é um número natural?
Resolvendo o Torto Reverso
Agora que sabemos o básico do Prolog, já temos o material necessário para resolver o puzzle! Note que eu usei como interpretador o SWI-Prolog, porque ele tem a melhor biblioteca de built-ins dos Prologs que eu pesquisei. Tudo que estiver em verde são palavras reservadas do SWI-Prolog.
Em linguagens tradicionais você precisa descrever, passo a passo, um método para encontrar a solução do seu problema. Em Prolog é o contrário, você só precisa falar quais são as propriedades da sua solução, e o interpretador se vira para achar um método de solucionar.
Por exemplo, nós podemos criar um predicado que é verdadeiro se o nosso grid é uma lista com 18 elementos. Mas como Prolog é reversível, se você deixar a variável do grid livre, ele vai criar um grid para você!
O Prolog não tinha informação suficiente para deduzir quem eram os elementos do grid, então colocou placeholders no lugar (_G282, _G285, etc).
Note também que o Prolog não tem arrays bidimensionais, só listas. Por isso, vamos precisar de um predicado para checar se os índices do grid são válidos, e um para indexar o grid a partir dos índices:
Nesse trecho o importante é entender o comando is. Para o Prolog, 1+1*3 é diferente de 4, porque ele não faz a avaliação aritmética por default. Usando o comando is, você o força a avaliar a expressão.
Agora vamos definir a conectividade do grid. Dada uma posição válida qualquer, nós podemos nos mover para qualquer das oito direções, desde que você não saia do grid. Para isso, podemos definir as oito possibilidades para um predicado move:
Assim, já podemos perguntar ao Prolog: saindo da posição 0,0, quais são as posições atingíveis?
Pronto, já temos as ferramentas básicas. Vamos descrever a nossa solução então. Nós queremos colocar uma palavra no grid, então quais as propriedades dessa palavra? Se a palavra tiver uma letra só, ela pode ser encaixada em qualquer posição do grid:
Agora, se ela tem várias letras, então você encaixa a primeira letra e faz a recursão para o resto da palavra, notando que o resto começa em um ponto que é um movimento válido a partir da primeira letra:
Aqui temos mais dois operadores do Prolog: o operador pipe separa uma lista em head e tail, e o operador underscore significa "don't care", nós não ligamos para o que o Prolog vai encaixar ali.
Isso já é o suficiente para encaixar uma palavra no grid, por exemplo, a partir da posição 0,0:
Eu pedi para imprimir só a primeira solução, mas nós poderíamos ter pedido para o Prolog imprimir todas as soluções. (Eu pulei a definição do writegrid, porque não é tão interessante.)
Antes de encaixar o resto das palavras, precisamos adicionar o restante das regras. Uma regra que não lidamos até agora é que uma palavra não pode repetir uma posição do grid durante o trajeto.
Para implementar essa restrição, podemos criar uma lista de posições já visitadas, e só permitir a inserção de uma letra se a posição dela ainda não estiver na lista. Vamos modificar nosso predicado word então:
A novidade aqui é o operador \+, que é simplesmente um "not". Ou seja, insira a nova letra somente se a posição dela não estiver na lista Visited.
Mas ainda tem outra regra: a palavra não pode cruzar o próprio caminho. Na horizontal e na vertical isso não tem como acontecer, porque para isso ele teria que repetir uma posição. Mas pode acontecer na diagonal, como na figura abaixo:
Para evitar esse caso, podemos fazer uma nova lista. Sempre que passarmos na diagonal por um bloco delimitado por letras, adicionamos esse bloco na lista.
Agora, para checar se andamos na diagonal, poderíamos verificar a direção que o Prolog deduziu no predicado move. Ao invés disso, vamos fazer de um jeito diferente:
Se um movimento repetir o X, ou se repetir o Y, então não é uma diagonal, e não precisamos adicionar nada na lista. Para isso, usamos o operador exclamação, que implementa um corte.
A idéia é simples: um predicado do tipo validBlock(0, 0, 0, 0, A, B) iria fazer match nas três instâncias declaradas, e por isso o Prolog iria deduzir três soluções para esse predicado. Mas, com o corte, ele desiste de procurar mais soluções após encontrar a primeira.
Note também que, para definir unicamente um bloco, independente da direção da diagonal, basta pegar o mínimo das posições X e Y.
Podemos agora incorporar esse predicado para chegar na versão final do word:
Isso já encaixa qualquer palavra seguindo todas as regras! Agora é só falar para inserir uma lista de palavras, ao invés de uma palavra só, e terminamos nosso solver:
O solver em Prolog ficou curto, né? Note que nós descrevemos só a solução, e não o método de solução. Em outras linguagens você precisaria se preocupar com Backtracking, A*, Exact Cover e o escambau, enquanto que no Prolog isso é feito por baixo dos panos para você.
Se você quiser rodar o solver em casa, aqui está o fonte completo:
Solução do Torto Reverso em Prolog
A desvantagem de escrever em Prolog é que fica um pouco mais lento que as linguagens tradicionais. Com essa implementação mostrada, temos 30 palavras, onde cada uma tem uma posição inicial definida num grid de 18 posições, e no mínimo 5 letras, onde cada letra pode estar em 8 posições possíveis a partir da anterior.
Ou seja, o espaço de busca é de (18*84)30, o que dá um total de 106898987586074109109365096428568366376512477689679588996632532409238880450162648732507836110780231551768603122161241934850249808547434035647873024 grids possiveis. Daí, usar esse solver em Prolog para um grid com 30 palavras pode demorar um bocadinho.
Ricbit Jam #3
Você acha que consegue fazer melhor que o Prolog usando sua linguagem predileta? Então participe do Ricbit Jam! Quem conseguir fazer o solver mais rápido do Torto Reverso vai ganhar de brinde um Boliche de Dedo oficial do Google:
Para participar, é só ler as regras abaixo:
Regras do Ricbit Jam #3
Divirta-se, e boa sorte!
Em linguagens de programação tradicionais, a metáfora que você usa para explicar é a da receita de bolo: programar é fazer uma seqüência de tarefas, como adicionar 200g de farinha e mexer até que a massa esteja consistente. Prolog usa um paradigma diferente, então a melhor metáfora é pensar que ele é um provador de teoremas: você entra com os axiomas e ele deriva os teoremas a partir deles.
Por exemplo, podemos usar o Prolog para definir os axiomas de Peano. Começamos com a definição de números naturais: zero é um número natural, e o sucessor de um natural também é um natural.
natural(0).
natural(s(X)) :- natural(X).Com essas definições já podemos perguntar ao Prolog: será que 2, ou seja, o sucessor do sucessor do zero, é um número natural?
?- natural(s(s(0))).
true.Bacana! E o sucessor de Togakure, é um número natural?
?- natural(s(togakure)).
false.Está certo, afinal, se Togakure não é um número natural então o sucessor também não pode ser. Vamos agora definir a adição: zero é o elemento neutro, e se você somar qualquer coisa com o sucessor de outra coisa, o resultado é o sucessor da soma das duas coisas.
add(A, 0, A).
add(A, s(B), s(C)) :- add(A, B, C).Podemos perguntar agora: será que 1+1=2? Será que 1+1=3?
?- add(s(0), s(0), s(s(0))).
true .
?- add(s(0), s(0), s(s(s(0)))).
false.Até agora só usamos o Prolog para testar a veracidade de sentenças, mas a diversão começa quando usamos o Prolog para completar sentenças. Sempre que você deixar uma variável livre numa sentença, o Prolog tenta completar a sentença para torná-la verdadeira. Por exemplo, quanto é 2+2?
?- add(s(s(0)), s(s(0)), X).
X = s(s(s(s(0)))) .Talvez a parte mais bacana do Prolog seja o fato da linguagem ser reversível. O mesmo programa que avalia a soma também é capaz de resolver uma equação. Por exemplo, qual é o número que somado com 2 dá 5?
?- add(X, s(s(0)), s(s(s(s(s(0)))))).
X = s(s(s(0))) .E qual é o número que somado com 1 dá 0?
?- add(X, s(0), 0).
false.O Prolog respondeu false, ou seja, no conjunto dos naturais não tem nenhum número que somado com 1 dá 0. Outra coisa bacana é que você pode deixar mais de uma variável livre. Por exemplo, quais são os pares de números cuja soma é 2?
?- add(A, B, s(s(0))).
A = s(s(0)),
B = 0 ;
A = s(0),
B = s(0) ;
A = 0,
B = s(s(0)) ;Ou seja, as soluções possíveis são 2+0, 1+1 e 0+2.
Resolvendo o Torto Reverso
Agora que sabemos o básico do Prolog, já temos o material necessário para resolver o puzzle! Note que eu usei como interpretador o SWI-Prolog, porque ele tem a melhor biblioteca de built-ins dos Prologs que eu pesquisei. Tudo que estiver em verde são palavras reservadas do SWI-Prolog.
Por exemplo, nós podemos criar um predicado que é verdadeiro se o nosso grid é uma lista com 18 elementos. Mas como Prolog é reversível, se você deixar a variável do grid livre, ele vai criar um grid para você!
validgrid(Grid) :-
length(Grid, 18).
?- validgrid(X).
X = [_G282, _G285, _G288, _G291, _G294,|...].O Prolog não tinha informação suficiente para deduzir quem eram os elementos do grid, então colocou placeholders no lugar (_G282, _G285, etc).
Note também que o Prolog não tem arrays bidimensionais, só listas. Por isso, vamos precisar de um predicado para checar se os índices do grid são válidos, e um para indexar o grid a partir dos índices:
valid(I,J) :- between(0, 2, I), between(0, 5, J). validletter(Grid, Letter, X, Y) :- valid(X, Y), Pos is X + Y * 3, nth0(Pos, Grid, Letter).
Nesse trecho o importante é entender o comando is. Para o Prolog, 1+1*3 é diferente de 4, porque ele não faz a avaliação aritmética por default. Usando o comando is, você o força a avaliar a expressão.
Agora vamos definir a conectividade do grid. Dada uma posição válida qualquer, nós podemos nos mover para qualquer das oito direções, desde que você não saia do grid. Para isso, podemos definir as oito possibilidades para um predicado move:
move(I, J, left, X, J) :- X is I - 1, valid(X, J). (...) move(I, J, down_right, X, Y) :- X is I + 1, Y is J + 1, valid(X, Y).
Assim, já podemos perguntar ao Prolog: saindo da posição 0,0, quais são as posições atingíveis?
?- move(0, 0, Direction, X, Y). Direction = right, X = 1, Y = 0 ; Direction = down, X = 0, Y = 1 ; Direction = down_right, X = 1, Y = 1.
Pronto, já temos as ferramentas básicas. Vamos descrever a nossa solução então. Nós queremos colocar uma palavra no grid, então quais as propriedades dessa palavra? Se a palavra tiver uma letra só, ela pode ser encaixada em qualquer posição do grid:
word(Grid, [Letter], X, Y) :- validletter(Grid, Letter, X, Y).
Agora, se ela tem várias letras, então você encaixa a primeira letra e faz a recursão para o resto da palavra, notando que o resto começa em um ponto que é um movimento válido a partir da primeira letra:
word(Grid, [Letter | Tail], X, Y) :- validletter(Grid, Letter, X, Y), move(X, Y, _, I, J), word(Grid, Tail, I, J).
Aqui temos mais dois operadores do Prolog: o operador pipe separa uma lista em head e tail, e o operador underscore significa "don't care", nós não ligamos para o que o Prolog vai encaixar ali.
Isso já é o suficiente para encaixar uma palavra no grid, por exemplo, a partir da posição 0,0:
solve(Word) :-
word(Grid, Word, 0, 0),
writegrid(Grid).
?- solve("torto").
tor
.ot
...
...
...
...Eu pedi para imprimir só a primeira solução, mas nós poderíamos ter pedido para o Prolog imprimir todas as soluções. (Eu pulei a definição do writegrid, porque não é tão interessante.)
Antes de encaixar o resto das palavras, precisamos adicionar o restante das regras. Uma regra que não lidamos até agora é que uma palavra não pode repetir uma posição do grid durante o trajeto.
Para implementar essa restrição, podemos criar uma lista de posições já visitadas, e só permitir a inserção de uma letra se a posição dela ainda não estiver na lista. Vamos modificar nosso predicado word então:
word(Grid, [Letter], Visited, X, Y) :- validletter(Grid, Letter, X, Y), \+ member(pos(X, Y), Visited). word(Grid, [Letter | Tail], Visited, X, Y) :- validletter(Grid, Letter, X, Y), move(X, Y, _, I, J), \+ member(pos(X, Y), Visited), word(Grid, Tail, [pos(X, Y) | Visited], I, J).
A novidade aqui é o operador \+, que é simplesmente um "not". Ou seja, insira a nova letra somente se a posição dela não estiver na lista Visited.
Mas ainda tem outra regra: a palavra não pode cruzar o próprio caminho. Na horizontal e na vertical isso não tem como acontecer, porque para isso ele teria que repetir uma posição. Mas pode acontecer na diagonal, como na figura abaixo:
Etna não é um vulcão válido.
Para evitar esse caso, podemos fazer uma nova lista. Sempre que passarmos na diagonal por um bloco delimitado por letras, adicionamos esse bloco na lista.
Agora, para checar se andamos na diagonal, poderíamos verificar a direção que o Prolog deduziu no predicado move. Ao invés disso, vamos fazer de um jeito diferente:
validBlock(X, _, X, _, Block, Block) :- !. validBlock(_, Y, _, Y, Block, Block) :- !. validBlock(X, Y, I, J, OldBlock, NewBlock) :- Bx is min(X, I), By is min(Y, J), \+ member(pos(Bx, By), OldBlock), NewBlock = [pos(Bx, By) | OldBlock].
Se um movimento repetir o X, ou se repetir o Y, então não é uma diagonal, e não precisamos adicionar nada na lista. Para isso, usamos o operador exclamação, que implementa um corte.
A idéia é simples: um predicado do tipo validBlock(0, 0, 0, 0, A, B) iria fazer match nas três instâncias declaradas, e por isso o Prolog iria deduzir três soluções para esse predicado. Mas, com o corte, ele desiste de procurar mais soluções após encontrar a primeira.
Note também que, para definir unicamente um bloco, independente da direção da diagonal, basta pegar o mínimo das posições X e Y.
Podemos agora incorporar esse predicado para chegar na versão final do word:
word(Grid, [Letter], Visited, _, X, Y) :- validletter(Grid, Letter, X, Y), \+ member(pos(X, Y), Visited). word(Grid, [Letter | Tail], Visited, Block, X, Y) :- validletter(Grid, Letter, X, Y), move(X, Y, _, I, J), \+ member(pos(X, Y), Visited), validBlock(X, Y, I, J, Block, NewBlock), word(Grid,Tail,[pos(X, Y) | Visited],NewBlock,I,J).
Isso já encaixa qualquer palavra seguindo todas as regras! Agora é só falar para inserir uma lista de palavras, ao invés de uma palavra só, e terminamos nosso solver:
wordlist(_, []). wordlist(Grid, [Word | WordList]) :- word(Grid, Word, [], [], _, _), wordlist(Grid, WordList). solve(WordList) :- validgrid(Grid), wordlist(Grid, WordList), writegrid(Grid). ?- solve(["otica","dedal","tedio","cardeal","aldeia"]). oti dac eda tel idr oac
O solver em Prolog ficou curto, né? Note que nós descrevemos só a solução, e não o método de solução. Em outras linguagens você precisaria se preocupar com Backtracking, A*, Exact Cover e o escambau, enquanto que no Prolog isso é feito por baixo dos panos para você.
Se você quiser rodar o solver em casa, aqui está o fonte completo:
Solução do Torto Reverso em Prolog
A desvantagem de escrever em Prolog é que fica um pouco mais lento que as linguagens tradicionais. Com essa implementação mostrada, temos 30 palavras, onde cada uma tem uma posição inicial definida num grid de 18 posições, e no mínimo 5 letras, onde cada letra pode estar em 8 posições possíveis a partir da anterior.
Ou seja, o espaço de busca é de (18*84)30, o que dá um total de 106898987586074109109365096428568366376512477689679588996632532409238880450162648732507836110780231551768603122161241934850249808547434035647873024 grids possiveis. Daí, usar esse solver em Prolog para um grid com 30 palavras pode demorar um bocadinho.
Ricbit Jam #3
Você acha que consegue fazer melhor que o Prolog usando sua linguagem predileta? Então participe do Ricbit Jam! Quem conseguir fazer o solver mais rápido do Torto Reverso vai ganhar de brinde um Boliche de Dedo oficial do Google:
Boliche de dedo do Google
Para participar, é só ler as regras abaixo:
Regras do Ricbit Jam #3
Divirta-se, e boa sorte!
