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++, Programação em C, Matemática para Ensino Fundamental, Matemática para Ensino Médio
Oferece aulas online (sala profes)
Oferece aulas presenciais
R$ 200 / aula
Conversar
Cadastre-se ou faça o login para comentar nessa publicação.

Listas de exercícios, Documentos, Revisões de textos, Trabalhos?

Se seu problema for dificuldade em uma lista de exercícios, revisão de teses e dissertações, correção de textos ou outros trabalhos, peça uma ajuda pelo Tarefas Profes.

Enviar Tarefa

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