Sudoku Adventures, Part I

Computação Programação
Sudoku Adventures, Part I
Lucas Virgili
em 28 de Abril de 2014

All work and no play makes Jack a dull boy

Começar a aprender a programar é chato. É como aprender uma nova língua: no começo, não sabemos nem o vocabulário simples, quem dirá falar uma frase completa.

Com programação é a a mesma coisa, infelizmente. No começo, temos dificuldade em dizer para o computador realizar tarefas simples como só imprimir algo na tela ou fazer uma conta! Tanto é que os alunos usualmente ficam com uma cara mais ou menos assim:

Mas com uma quantidade impressionantemente pequena de palavras e "estruturas gramaticais" é possível fazer, bom, tudo! Afinal, o computador é muito burro, lembra?

Assim, depois de umas 4 ou 5 aulas já podemos fazer coisas legais como um programa que resolve um sudoku!

Itinerário

Como tudo que é interessante de se resolver, não podemos resolver o sudoku sem pensar um pouco. Por isso, vou dividir nossa "viagem" nos seguintes passos:

1. Entender o que é "resolver um sudoku";
2. Pensar em uma solução para o problema;
3. Dividir a solução de um sudoku em problemas menores;
4. Converter esses problemas em funções e testarmos uma por uma; e
5. Juntar nossas funções e resolver o problema!

Basicamente, resolver um problema usando programação sempre envolve esses passos: primeiro, temos que entender o problema que vamos resolver, depois o quebramos em problemas menores, os quais resolvemos um por um, para termos certeza que fizemos tudo certo. No fim, juntamos tudo e puff!, temos nossa solução para o problema original!

Sudoku

O problema

Um jogo de sudoku é bem simples: temos uma tabela com 9 linhas e 9 colunas, que é dividida em 9 subtabelas de 3 linhas e 3 colunas. Nessa tabela, temos alguns números colocados para nós, e nosso trabalho é o seguinte: temos que preencher o resto da tabela de forma que cada linha, cada coluna e cada subtabela tenha os números de 1 a 9 exatamente uma vez. Ou seja, em uma dada linha, coluna ou subtabela não pode haver repetição de números.

A solução

Algo que não falta no mundo são jeitos de resolver sudokus com o computador. Por isso mesmo, vamos fazer do jeito mais simples, que aproveita o que o computador faz melhor: repetir instruções simples.

Veja só como iremos fazer: nós vamos começar no primeiro quadrado vazio da tabela e colocar o número 1. Brilhante, não? Depois, nós vamos checar se já havia um 1 na mesma linha, coluna ou submatriz daquele quadrado. Se não, maravilha, nós vamos para o próximo quadrado vazio e colocamos, advinhe, outro 1!

O que acontece é que se encontrarmos o mesmo número na linha, coluna ou subtabela, nós simplesmente tentamos com o próximo e depois o próximo e depois o próximo, até que consigamos encaixar um número no maldito quadrado que não está repetido. Nós fazemos isso até o final da tabela e, bumba meu boi, resolvemos um sudoku!

O único problema é que podemos, em algum quadrado, não conseguir colocar nenhum número (ou seja, tentamos até 9 e todos os números já apareciam na mesma linha, coluna ou subtabela). :( Mas não se despespere! Basta deixarmos esse quadrado em branco e voltarmos para o último quadrado que preenchemos com algum número e colocar o próximo número nele. Se não conseguirmos colocar nada nesse quadrado também, voltamos para o anterior e colocamos o próximo número nele e assim até conseguirmos colocar algum número sem problemas!

Eu admito, não é o jeito mais elegante de se resolver um sudoku. OK, é o mais porco. Mas acredite em mim quando eu digo que funciona!

No próximo post dessa série nós vamos converter essa coisa de colocar 1, depois 2 e ir para o próximo e deixar em branco e voltar em problemas menores, para depois juntarmos tudo e resolver um sudoku.

Então aguarde o próximo episódio, nesse mesmo canal, nesse mesmo horário para vermos como vamos, como dizia nosso amigo Jack, ir por partes.

São Paulo / SP

14 avaliações
Mestrado: MSc Advanced Computing - Machine Learning, Data Mining and H (University of Bristol - UK)
Professor de matemática e computação na Escola Britânica de São Paulo, St. Paul's. Experiência no preparo para IB (Studies, SL e HL), IGCSE, SAT e ACT.
IGCSE Computer Sciece, IB Computer Science, Python, C, C++, Matemática para Ensino Fundamental, Matemática para Ensino Médio
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 224 / aula
Conversar
Cadastre-se ou faça o login para comentar nessa publicação.

Confira artigos similares

Confira mais artigos sobre educação

Ver todos os artigos

Encontre um professor particular

Busque, encontre e converse gratuitamente com professores particulares de todo o Brasil