Não é segredo que nerd que é nerd adora resolver problemas sem nenhuma utilidade aparente. Na maioria dos casos, quanto mais inútil e desligado de qualquer compromisso, mais tentador é o problema. Como dizia Carl Sagan, nem que se pagassem todo o dinheiro do mundo conseguiriam que Maxwell desenvolvesse suas equações em pesquisa controlada.
De fato, todo o processo de resolução de problemas, desde a formulação, passando pela modelagem e desenvolvimento do método, até finalmente obter os resultados e encontrar conclusões a respeito deles. Daí um dia eu me vi formulando um problema tão incrivelmente banal que provavelmente seria infinitamente fascinante de resolver: o Problema dos Dominós!
... hein?
O problema é o seguinte: você tem um conjunto de dominós com até n pontos(e.g., um jogo de dominó convencional é um 6-dominó). O problema consiste simplesmente de duas perguntas:
- É possível enfileirar todas as peças de uma vez só, segundo as regra do jogo, i.e., uma peça com uma extremidade X se conecta com outra que tenha uma extremidade igual livre?
- Se sim, de qual forma, i.e., enfileirando-as em que ordem?
Simples assim. A utilidade disso? Não sei. Só sei que resolvi resolver essa coisa.
E...?
E fiz um programa bem simples em Python. Escolhi Python porque pra mexer com vetores, tuplas e etcéteras, ou Python ou PHP, e Pyhton estava mais à mão. Pois bem, fiz o programa, com um argumento(qual o "n" do conjunto) e mandei ele rodar. Os resultados foram interessantes...
Obviamente, para 1-dominós e 2-dominós o resultado era óbvio, logo só serviram para provar que o programa estava certo, e também que eu cometi um erro na especificação do problema. Não deveria ser "de qual forma", mas "de quais formas". O problema para 3-dominós, por exemplo, tem 12 soluções, que são 6 se você descontar as reversões. Mas a parte mais interessante vem agora...
Não provei formalmente ainda, mas achar uma primeira solução é trivial para o programa. Não leva 1 segundo e ele já imprime umas dezenas delas, quando há. Daí deu pra perceber um padrão interessante: existe solução para o "Problema dos Dominós" com N igual a 1, 2, 3, 5, 7, 9, 11, 13... Mas não existe para N igual a 4, 6, 8, 10, 12, 14... Ou seja: para conjuntos pares, exceto 2(que tem solução imensamente trivial) não existe uma solução sequer. Juro, rodei com N=4 e o programa não deu resposta. Para n=6, o "problema clássico", ele rodou por quase meia hora sem resposta, mais que suficiente...
Então...
Então não sei. Deve existir alguma aplicação prática pra isso, mas no momento eu não faço idéia. Por ora é apenas mais uma curiosidade desenvolvida por conta própria por um jovem nerd.
E, essas férias, vou ver se consigo fazer a versão "Cíclica" do problema. Se der alguma coisa interessante, eu aviso. ;)
Bruno Pedrassani
20/06/2008 23:44
Cara, veja devola o seu programa, você deve estar esquecendo alguma combinação. Não vou dizer que sempre tem solução(apesar de que acho que sempre tem), mas pelo menos pra n = 4 tem. Não se esqueça que você pode "caminhar" pros dois lados, e tem a pedra sem pontos(acho que se ela não existir dá na mesma).
Link para este comentário | ResponderFaça na mão n = 4. Você terá 15 peças de dominó. Acho que a solução mais fácil sempre é ir colocando as pedras duplicadas uma após a outra. Ex. |0|0| -> |0|1| -> |1|1| -> |1|2| -> |2|2| -> ...
Quando não puder mais, você sempre terá, |0|0| -> ... -> |n|n|
A partir daí dá pra distribuir as outras peças. Não garanto que é a única solução, devem existir várias, e quanto mais peças, maior o número de soluções(eu acho). Pra n = 4 funcionou essa abordagem, e ela já garante que há pelo menos uma solução.
"Toupeira Profissional"
21/06/2008 10:10
Okay, um detalhe que eu acabei omitindo, o problema começa com dominó 1|1, logo a sua proposição de n=4 é na realidade um n=5. E tem solução, sim. Tente com n=3 no seu esquema, acho que não vai dar.
Link para este comentário | ResponderMas meu programa tenta exaustivamente as soluções, ele tenta todos os dominós iniciais, de um lado e de outro. Caminhar pros dois lados equivale a começar com outra pedra e chegar na mesma sequência, ou seja, não faz diferença para o programa. E quanto à pedra sem pontos, nunca vi nenhuma regra a respeito.
Bruno Pedrassani
21/06/2008 10:52
Saquei, e tem razão, números pares não têm solução.
Link para este comentário | ResponderSe modelar por grafos é um dos problemas existentes, basta achar um circuito/caminho euleriano nesse grafo.
Pro circuito ser euleriano(ou seja, alcançar todos os nós do grafo, no caso, todos os dominós), o grau dos vértices tem que ser par(porque tem que "entrar" e "sair" em cada vértice).
No seu caso dos dominós, cada lado do dominó pode ser considerado como um grau do respectivo vértice. Exemplo:
Pra n = 4, temos: 1|1, 1|2, 1|3, 1|4 pras peças com 1 ponto. Isso dá grau 5(1|1 conta 2 graus). Então não há como alcançar todos os nós do grafo, uma vez que há grau ímpar pra 1(e pros outros também). Quando o n = # ímpar, temos sempre grau par para os pontos, por isso há solução.
"Toupeira Profissional"
22/06/2008 00:45
Ê, beleza. E agora vou te agradecer por ter provado formalmente o que eu só consegui por experiência. Parabéns! =D
Link para este comentário | ResponderBruno Pedrassani
22/06/2008 07:05
Hehehe, e veja, a idéia foi boa. Apesar da aplicação dos dominós não ser muito prática, o problema em si tem várias aplicações.
Link para este comentário | ResponderThiago-Nacio
23/06/2008 14:24
muito bem modelado! hehe =]
Link para este comentário | Responder