De tempos em tempos a mídia impressa inventa uma modinha para vender mais papel. A modinha da vez são os livros de colorir. Eles são uma sensação! Os livros não param nas lojas, existem grupos e grupos falando disso na internet, rola até competição para ver quem pinta melhor!
Mas, se você tem memória boa, deve lembrar que mesma coisa aconteceu dez anos atrás. Ao invés de livros de colorir, a modinha era Sudoku. Era uma sensação! Haviam livros e livros nas lojas, todo mundo falava disso na internet, rolava até competição para ver quem resolvia mais rápido!
À primeira vista, os dois passatempos são bem distintos: o livro de colorir precisa de sensibilidade artística, o sudoku de raciocínio lógico. Mas hoje eu vou provar que, na verdade, os dois são equivalentes! E tudo começa com a regra não escrita dos livros de colorir.
Livros de colorir tem uma regra implícita. Todo mundo concorda que isso aqui é uma pintura válida, certo?
Mas isso aqui é trapacear:
A regra implícita dos livros de colorir é que pintar duas regiões adjacentes com a mesma cor não vale. Afinal, tem uma linha preta ali, e ela está ali por uma razão, que é separar regiões de cores diferentes. Se você ignorar a linha preta, não está aproveitando todos os detalhes da figura.
Se você for a uma papelaria atualmente, verá que todas as caixas de lápis de cor com 48 cores estão esgotadas. O motivo é que os livros de colorir tem muitas regiões adjacentes, então quanto mais cores, mais fácil de pintar.
E qual é o mínimo de cores que você precisa? Um estojo de 12 cores é suficiente? Incrivelmente, doze cores dá e sobra. Na verdade, com apenas 4 cores você consegue pintar qualquer desenho, sem deixar regiões adjacentes com a mesma cor! Essa proposição é o lendário Teorema das Quatro Cores, que ficou famoso por ter sido o primeiro grande teorema da matemática provado por computador.
Além disso, o problema de pintar um desenho com a menor quantidade de cores possíveis não é apenas teórico. Ele tem várias utilidades práticas! Por exemplo, compiladores usam pintura para fazer alocação de registros, e companhias aéreas usam pintura para fazer alocação de aviões em rotas aéreas.
O problema da pintura mínima também serve para resolver Sudokus. Mas antes de mostrar como isso pode ser feito, vamos resolver um problema mais simples, o Bidoku.
O Bidoku é a versão fácil do Sudoku. Você tem um grid 2x2, e precisa preenchê-lo com 0 e 1, de modo não tenha dois números iguais na mesma linha e na mesma coluna:
Esse puzzle é bem fácil, dá para resolver de cabeça né? Mas vamos ver como é o raciocínio usando pintura. Para isso, vamos dar um nome para cada uma das células do puzzle:
Cada uma das letras pode ser 0 ou 1. Vamos enumerar as possiblidades: A pode ser 0 ou 1, B pode ser 0 ou 1, e assim por diante:
Agora vamos ligar com uma linha todos os nós que não podem acontecer ao mesmo tempo. Começando do B, nós sabemos que ou o B é zero, ou o B é um. Então coloco uma linha entre B0 e B1. Além disso, se B for 0, então nem A e nem C podem ser 0. Da mesma maneira, se B for 1, então nem A e nem C podem ser 1. Desenhando:
Agora é só repetir o que fizemos com o B para todas as outras letras:
Este é o grafo equivalente do Bidoku. Com o grafo em mãos, podemos achar a figura de colorir equivalente, basta achar um desenho onde as regiões adjacentes são exatamente aquelas indicadas pelas linhas do grafo. Qualquer desenho que satisfaça essa condição serve, pode ser esse aqui, por exemplo:
Com o desenho em mãos, podemos resolver o Bidoku através da coloração!. Começa assim: você pega todos os números que foram dados, e pinta de verde. No Bidoku exemplo acima, era dado que o A valia 1, então nós pintamos de verde o A1:
Agora é só pintar o restante com o menor número de cores possível, respeitando a regra de que regiões adjacentes precisam ter cores distintas. Se você fizer a pintura, vai notar que é possível pintar com apenas duas cores, de uma única maneira:
Agora você pega todas as regiões verdes e retorna para o Bidoku original:
Funciona mesmo! O Bidoku foi resolvido pela coloração mínima!
Uma dúvida pertinente é o que acontece com a coloração se você tentar pintar um Bidoku insolúvel. Por exemplo, o Bidoku abaixo não tem solução (o B não pode ser 0 e nem 1):
Se você tentar a coloração mínima, vai notar que são necessárias no mínimo três cores para respeitar as regras:
Essa regra vale sempre, se a sua coloração mínima tem mais de duas cores, então o Bidoku original era insolúvel.
Agora que já dominamos o Bidoku, podemos passar para a solução do Sudoku.
O Sudoku usa o mesmo raciocínio do Bidoku, mas o problema é muito maior. No Bidoku a célula A tinha duas possibilidades, então nós criávamos dois nós: A0 e A1. No Sudoku, ela tem nove possibilidades, então a célula A gera os nós A1, A2, A3, .., até A9. E você precisa adicionar linhas ligando os números, as linhas, as colunas, e as caixas (eu chamo de caixas aqueles blocos 3x3). O grafo final do Sudoku, levando em conta tudo isso, fica assim:
São 729 nós e 11664 linhas, só um pouquinho maior que o Bidoku, que tinha 8 nós e 12 linhas. Além disso, no Bidoku nós conseguimos fazer um desenho equivalente ao grafo. No Sudoku isso não é possível, porque esse grafo não é planar (ou melhor, você pode fazer um desenho, mas vai ser um desenho multidimensional em uma geometria possivelmente não-euclideana). Isso não afeta nossa proposição, já você pode colorir diretamente os nós do grafo, ao invés de colorir as regiões de um desenho equivalente.
E como fazemos isso? Da mesma maneira que o Bidoku, você parte de um Sudoku que você quer resolver, por exemplo esse aqui, que eu peguei no The Guardian:
Nós vamos pintar de verde todas as células correspondentes no grafo do Sudoku (eu não vou mostrar as linhas dessa vez, assim fica mais visível):
Pois bem, a minha proposição é que se você fizer a pintura mínima nesse grafo, o resultado do Sudoku vai aparecer nas células que forem pintadas de verde. Nós vimos um exemplo de que isso funciona no Bidoku, mas um exemplo não é uma demonstração, pode ter sido coincidência. Eu vou provar abaixo que isso sempre é verdade. Se você tem medo de demonstrações, pule a caixa azul para ver o Sudoku pintado.
Se você tiver paciência de fazer a pintura mínima naquele grafo gigante, o resultado será esse aqui:
Transcrevendo as células verdes para o diagrama original, temos a solução do Sudoku, como prometido!
Na prática, esse é provavelmente um dos piores métodos para resolver o Sudoku. Mesmo um algoritmo no estado da arte em graph coloring vai levar um bom tempo para achar uma solução através de pintura mínima. Mas pelo menos você pode dizer que Sudoku é equivalente a um livro de pintura, desde que você não ligue de fazer pinturas mínimas em livros multidimensionais de geometria possivelmente não-euclideana :)
Mas, se você tem memória boa, deve lembrar que mesma coisa aconteceu dez anos atrás. Ao invés de livros de colorir, a modinha era Sudoku. Era uma sensação! Haviam livros e livros nas lojas, todo mundo falava disso na internet, rolava até competição para ver quem resolvia mais rápido!
À primeira vista, os dois passatempos são bem distintos: o livro de colorir precisa de sensibilidade artística, o sudoku de raciocínio lógico. Mas hoje eu vou provar que, na verdade, os dois são equivalentes! E tudo começa com a regra não escrita dos livros de colorir.
A Regra dos Livros de Colorir
Livros de colorir tem uma regra implícita. Todo mundo concorda que isso aqui é uma pintura válida, certo?
Mas isso aqui é trapacear:
A regra implícita dos livros de colorir é que pintar duas regiões adjacentes com a mesma cor não vale. Afinal, tem uma linha preta ali, e ela está ali por uma razão, que é separar regiões de cores diferentes. Se você ignorar a linha preta, não está aproveitando todos os detalhes da figura.
Se você for a uma papelaria atualmente, verá que todas as caixas de lápis de cor com 48 cores estão esgotadas. O motivo é que os livros de colorir tem muitas regiões adjacentes, então quanto mais cores, mais fácil de pintar.
E qual é o mínimo de cores que você precisa? Um estojo de 12 cores é suficiente? Incrivelmente, doze cores dá e sobra. Na verdade, com apenas 4 cores você consegue pintar qualquer desenho, sem deixar regiões adjacentes com a mesma cor! Essa proposição é o lendário Teorema das Quatro Cores, que ficou famoso por ter sido o primeiro grande teorema da matemática provado por computador.
Além disso, o problema de pintar um desenho com a menor quantidade de cores possíveis não é apenas teórico. Ele tem várias utilidades práticas! Por exemplo, compiladores usam pintura para fazer alocação de registros, e companhias aéreas usam pintura para fazer alocação de aviões em rotas aéreas.
O problema da pintura mínima também serve para resolver Sudokus. Mas antes de mostrar como isso pode ser feito, vamos resolver um problema mais simples, o Bidoku.
Bidoku
O Bidoku é a versão fácil do Sudoku. Você tem um grid 2x2, e precisa preenchê-lo com 0 e 1, de modo não tenha dois números iguais na mesma linha e na mesma coluna:
Esse puzzle é bem fácil, dá para resolver de cabeça né? Mas vamos ver como é o raciocínio usando pintura. Para isso, vamos dar um nome para cada uma das células do puzzle:
Cada uma das letras pode ser 0 ou 1. Vamos enumerar as possiblidades: A pode ser 0 ou 1, B pode ser 0 ou 1, e assim por diante:
Agora vamos ligar com uma linha todos os nós que não podem acontecer ao mesmo tempo. Começando do B, nós sabemos que ou o B é zero, ou o B é um. Então coloco uma linha entre B0 e B1. Além disso, se B for 0, então nem A e nem C podem ser 0. Da mesma maneira, se B for 1, então nem A e nem C podem ser 1. Desenhando:
Agora é só repetir o que fizemos com o B para todas as outras letras:
Este é o grafo equivalente do Bidoku. Com o grafo em mãos, podemos achar a figura de colorir equivalente, basta achar um desenho onde as regiões adjacentes são exatamente aquelas indicadas pelas linhas do grafo. Qualquer desenho que satisfaça essa condição serve, pode ser esse aqui, por exemplo:
Com o desenho em mãos, podemos resolver o Bidoku através da coloração!. Começa assim: você pega todos os números que foram dados, e pinta de verde. No Bidoku exemplo acima, era dado que o A valia 1, então nós pintamos de verde o A1:
Agora é só pintar o restante com o menor número de cores possível, respeitando a regra de que regiões adjacentes precisam ter cores distintas. Se você fizer a pintura, vai notar que é possível pintar com apenas duas cores, de uma única maneira:
Agora você pega todas as regiões verdes e retorna para o Bidoku original:
Funciona mesmo! O Bidoku foi resolvido pela coloração mínima!
Uma dúvida pertinente é o que acontece com a coloração se você tentar pintar um Bidoku insolúvel. Por exemplo, o Bidoku abaixo não tem solução (o B não pode ser 0 e nem 1):
Se você tentar a coloração mínima, vai notar que são necessárias no mínimo três cores para respeitar as regras:
Essa regra vale sempre, se a sua coloração mínima tem mais de duas cores, então o Bidoku original era insolúvel.
Agora que já dominamos o Bidoku, podemos passar para a solução do Sudoku.
A Coloração do Sudoku
O Sudoku usa o mesmo raciocínio do Bidoku, mas o problema é muito maior. No Bidoku a célula A tinha duas possibilidades, então nós criávamos dois nós: A0 e A1. No Sudoku, ela tem nove possibilidades, então a célula A gera os nós A1, A2, A3, .., até A9. E você precisa adicionar linhas ligando os números, as linhas, as colunas, e as caixas (eu chamo de caixas aqueles blocos 3x3). O grafo final do Sudoku, levando em conta tudo isso, fica assim:
Clique na imagem para ver o SVG original
São 729 nós e 11664 linhas, só um pouquinho maior que o Bidoku, que tinha 8 nós e 12 linhas. Além disso, no Bidoku nós conseguimos fazer um desenho equivalente ao grafo. No Sudoku isso não é possível, porque esse grafo não é planar (ou melhor, você pode fazer um desenho, mas vai ser um desenho multidimensional em uma geometria possivelmente não-euclideana). Isso não afeta nossa proposição, já você pode colorir diretamente os nós do grafo, ao invés de colorir as regiões de um desenho equivalente.
E como fazemos isso? Da mesma maneira que o Bidoku, você parte de um Sudoku que você quer resolver, por exemplo esse aqui, que eu peguei no The Guardian:
Nós vamos pintar de verde todas as células correspondentes no grafo do Sudoku (eu não vou mostrar as linhas dessa vez, assim fica mais visível):
Clique na imagem para ver o SVG original
Pois bem, a minha proposição é que se você fizer a pintura mínima nesse grafo, o resultado do Sudoku vai aparecer nas células que forem pintadas de verde. Nós vimos um exemplo de que isso funciona no Bidoku, mas um exemplo não é uma demonstração, pode ter sido coincidência. Eu vou provar abaixo que isso sempre é verdade. Se você tem medo de demonstrações, pule a caixa azul para ver o Sudoku pintado.
Antes de mais nada, quantas cores precisamos para pintar esse grafo? O instinto é falar que precisamos de 4 cores, por causa do Teorema das Quatro Cores. Mas esse teorema só funciona se o grafo for planar! E o grafo do Sudoku claramente não é planar, já que ele admite o K5 como subgrafo, e, portanto, viola o teorema de Kuratowski para grafos planares.
Vamos tentar achar qual o número de cores então. Pegue uma célula qualquer, por exemplo uma célula A. Nós temos 9 nós correspondentes, de A1 até A9, e nenhum desses nós pode ter a mesma cor que o outro. Então o grafo da célula A é um clique de tamanho 9. Como o número cromático de um grafo é sempre maior ou igual ao grau do maior clique, então sabemos que o grafo tem pelo menos 9 cores.
Mas, se esse grafo foi construído a partir de um Sudoku que tem solução, então nós podemos construir uma coloração com 9 cores para ele. Você começa pintando todos os nós da solução com a cor 0. Depois, para cada tripla (i, j, digito) que foi pintada com a cor 0, você pinta a tripla (i, j, digito + 1) com a cor 1 (o incremento no dígito é mod 9). Essa pintura não viola o grafo, porque ele é simétrico nos dígitos. Repetindo o processo para as cores 2..9, você tem um grafo totalmente pintado e sem nenhuma violação.
Se o número mínimo de cores é 9, e nós sempre conseguimos construir uma pintura com 9 cores, então o número cromático é 9. Done.
Ainda falta um detalhe: ninguém garante que existe uma única pintura possível com 9 cores (e na prática vai ter mais de uma mesmo). Mas todas as pinturas possíveis resolvem o Sudoku! Como o número cromático é 9, então cada célula (i,j) vai ter um elemento pintado com cada uma das cores possíveis (já que a célula é um clique de tamanho 9). Como cada célula tem todas as cores, então cada célula vai ter um elemento com a cor 0; e se todas as células tem a cor 0, então toda pintura possível embute uma solução do Sudoku. QED.
Vamos tentar achar qual o número de cores então. Pegue uma célula qualquer, por exemplo uma célula A. Nós temos 9 nós correspondentes, de A1 até A9, e nenhum desses nós pode ter a mesma cor que o outro. Então o grafo da célula A é um clique de tamanho 9. Como o número cromático de um grafo é sempre maior ou igual ao grau do maior clique, então sabemos que o grafo tem pelo menos 9 cores.
Mas, se esse grafo foi construído a partir de um Sudoku que tem solução, então nós podemos construir uma coloração com 9 cores para ele. Você começa pintando todos os nós da solução com a cor 0. Depois, para cada tripla (i, j, digito) que foi pintada com a cor 0, você pinta a tripla (i, j, digito + 1) com a cor 1 (o incremento no dígito é mod 9). Essa pintura não viola o grafo, porque ele é simétrico nos dígitos. Repetindo o processo para as cores 2..9, você tem um grafo totalmente pintado e sem nenhuma violação.
Se o número mínimo de cores é 9, e nós sempre conseguimos construir uma pintura com 9 cores, então o número cromático é 9. Done.
Ainda falta um detalhe: ninguém garante que existe uma única pintura possível com 9 cores (e na prática vai ter mais de uma mesmo). Mas todas as pinturas possíveis resolvem o Sudoku! Como o número cromático é 9, então cada célula (i,j) vai ter um elemento pintado com cada uma das cores possíveis (já que a célula é um clique de tamanho 9). Como cada célula tem todas as cores, então cada célula vai ter um elemento com a cor 0; e se todas as células tem a cor 0, então toda pintura possível embute uma solução do Sudoku. QED.
Se você tiver paciência de fazer a pintura mínima naquele grafo gigante, o resultado será esse aqui:
Clique na imagem para ver o SVG original
Transcrevendo as células verdes para o diagrama original, temos a solução do Sudoku, como prometido!
Na prática, esse é provavelmente um dos piores métodos para resolver o Sudoku. Mesmo um algoritmo no estado da arte em graph coloring vai levar um bom tempo para achar uma solução através de pintura mínima. Mas pelo menos você pode dizer que Sudoku é equivalente a um livro de pintura, desde que você não ligue de fazer pinturas mínimas em livros multidimensionais de geometria possivelmente não-euclideana :)
Nenhum comentário:
Postar um comentário