Sudoku e os métodos de solução deste tipo de problemas, juntamente com um breve resumo histórico e algumas

considerações adicionais.

O que é um Sudoku e como resolvê-lo

Índice• Generalidades

• Resumo histórico

• Como se resolve?

• Grau de dificuldade

• Qualidade

• Bibliografia

• Os Sudoku têm vindo a ganhar uma enorme popularidade nos últimos tempos, ao ponto

de rivalizarem hoje em dia com o mais popular de todos os passatempos: As Palavras

Cruzadas. É vulgar nos dias que correm aparecer na secção de passatempos de um

jornal ou revista, um ou mais problemas de Sudoku, lado a lado com problemas de

Palavras Cruzadas.

• Mais recentemente, a Internet veio dar um novo impulso aos Sudoku, existindo vários

sítios dedicados ao tema. Uma grande vantagem dos Sudoku sobre as Palavras

Cruzadas é que aqueles não têm que ultrapassar barreiras linguísticas: Um problema

publicado nos Estados Unidos ou no Japão é igualmente válido em Portugal.

• A versão mais comum do problema tem este aspecto:

Generalidades

Generalidades

• Como se pode ver na figura, um problema de Sudoku toma a forma de uma

grelha de 9x9 quadrados, dividida em nove blocos de 3x3 quadrados. O

objectivo é preencher os quadrados com os números 1 a 9, de tal forma que

em cada domínio não haja números repetidos. Um domínio é constituído por

uma linha, uma coluna ou um bloco de 3x3. À partida o problema é

apresentado com um número variável (normalmente à volta de 30) de

quadrículas já preenchidas, as quais condicionam o preenchimento das

restantes.

• A solução para o problema apresentado acima é:

Generalidades

Generalidades

• Sudoku é uma espécie de acrónimo da expressão japonesa Suuji wa dokushin ni kagiru, a qual pode ser traduzida por "Os números devem ser únicos " ou " Os números devem ocorrer apenas uma vez". Este nome foi proposto por Kaji Maki, o presidente da empresa editora Nikoli, responsável pela introdução deste passatempo no Japão, a qual publicou um Sudoku pela primeira vez no seu jornal Monthly Nikolist em Abril 1984. O termo Sudoku continua a ser uma marca registada da Nikoli.

• Contudo, a invenção to passatempo é anterior (1979) e deve-se a Howard Garns, um construtor de passatempos freelancer. O primeiro passatempo deste tipo foi publicado emNew York nos finais dos anos 70 pela editora Dell Magazines na sua revista Dell Pencil Puzzles and Word Games, sob o título Number Place

• Em Inglaterra, o Times publicou o seu primeiro Sudoku em 12 de Novembro de 2004 sob o título Su Doku. Três dias mais tarde, o Daily Mail iniciou a publicação do passatempo, a que chamou Codenumber. O Daily Telegraph publicou o seu primeiro Sudoku em 19 de Janeiro de 2005. A partir daqui muitos outros jornais e revistas passaram a publicar também este tipo de passatempo.

• A partir de Julho de 2005 o canal de TV Channel 4 publica diariamente um Sudoku no seu serviço de teletexto. O primeiro programa de TV ao vivo dedicado ao Sudoku, chamadoSudoku Live foi transmitido em 1 de Julho de 2005 no canal Sky One.

Resumo histórico

• Esta secção descreve a metodologia de solução de problemas Sudoku. Os métodos aqui

descritos pressupõem a utilização do programa NovCruz, embora sejam válidos também

para a forma tradicional de solução no papel. No entanto, o programa NovCruz é

preferível, uma vez que este automatiza algumas das operações necessárias para

solução de um Sudoku, sem retirar nada ao prazer de descobrir a lógica subjacente ao

preenchimento de uma dada posição da quadrícula.

• Para resolver um Sudoku é necessário, antes de mais, definir um método de identificar

quais os números válidos para cada quadrícula. Todas as restantes operações se

baseiam neste tipo de informação. Uma forma expedita de atingir este objectivo é o

sistema de pontos, o qual consiste em colocar um ponto numa dada posição da

quadrícula para cada algarismo que não pode ser colocado nessa quadrícula, seguindo o

esquema:

Como se resolve?

1 2 3

4 5 6

7 8 9

Seguindo este método, a janela de um Sudoku em fase de resolução aparece no programa NovCruz com este aspecto:

Como se resolve?

• Olhando para a figura supra e tomando como exemplo a 3ª posição da 1ª linha, torna-se

imediatamente aparente que nesta posição apenas podem aparecer os algarismos 3, 5 e 9. A

grande vantagem de usar o programa é que este automaticamente actualiza os pontos

referentes a cada quadrícula quando se coloca um número. Na resolução em papel é

necessário proceder a essa operação manualmente, o que se torna um tanto ou quanto

fastidioso e sujeito a enganos.

• Uma vez encontrada uma forma expedita de identificar os números que podem ser colocados

numa dada posição podemos avançar para os métodos de solução propriamente ditos, os

quais irão determinar qual o número a colocar numa dada posição, respeitando os

condicionalismos derivados das regras básicas do problema. Para resolver um Sudoku

existem fundamentalmente três operações, de dificuldade progressivamente crescente:

Varrimento, Análise e Emparelhamento.

Como se resolve?

• Varrimento

• Esta é a operação mais simples de todas. Como o próprio nome indica, consiste em varrer a grelha

à procura de quadrículas que apenas possam conter um número. No exemplo acima, a segunda

posição da primeira linha só pode conter um 5. Isto é o suficiente para avançar um passo na

solução do problema.

• Análise

• Esta operação também não é complicada, embora seja mais trabalhosa que a anterior. Consiste

em analisar cada domínio (linha, coluna ou bloco de 3x3) à procura das posições onde cada

algarismo de 1 a 9 pode aparecer. Se um dado número apenas pode aparecer numa posição do

domínio, isso é o suficiente para colocar mais um número na grelha. Por exemplo se reparar na 6ª

linha da figura supra, verificará que o algarismo 7 apenas pode aparecer na 2ª posição.

Como se resolve?

• Emparelhamento

• Esta é a operação mais complexa de todas e, embora seja fácil entender a lógica subjacente, a sua aplicação prática requer uma certa prática ou mesmo “olho clínico” para identificar as situação que podem levar à simplificação do problema.

• Como acima referido, a regra fundamental de um Sudoku estabelece que num dado domínio não possa haver números repetidos. Um corolário desta regra é que num domínio tenha obrigatoriamente que conter 9 algarismos diferentes, uma vez que cada domínio tem precisamente 9 posições.

• Da regra fundamental e do seu corolário pode também deduzir-se que num dado domínio qualquer subconjunto de n posições apenas pode conter n algarismos. É neste facto que a operação de emparelhamento se baseia. Consiste em encontrar grupos de n posições que apenas possam conter um grupo de n algarismos. Também se pode fazer emparelhamento usando a perspectiva inversa, isto é, descobrir subconjuntos de n algarismos que apenas podem aparecer em n posições.

• Veja-se por exemplo a seguinte situação:

Como se resolve?

Como se resolve?

• Usando apenas operações de análise não é possível avançar a solução do problema; por

conseguinte somos obrigados a tentar operações de emparelhamento.

• Se reparar na terceira linha do problema, verificará que nas 5ª e 6ª posições apenas

podem aparecer os algarismos 1 e 2. Temos portanto dois algarismos emparelhados com

duas posições de quadrícula.

• Isto implica que a 8ª posição da linha não poderá conter o algarismo 1, tal como indicado

pelos pontos pertencentes àquela posição. Isto por sua vez implica que na 8ª posição da

linha apenas possa aparecer o algarismo 3. Este raciocínio é o suficiente para

desbloquear a situação e resolver o resto do problema usando apenas operações de

análise triviais.

•

Como se resolve?

• Sendo a operação de emparelhamento a mais difícil de todas, é natural associar o grau de dificuldade de um Sudoku ao número destas operações a que é necessário recorrer para o resolver.

• Nos problemas resolvidos com o programa NovCruz, o grau de dificuldade aparece no título da janela associada, podendo tomar os valores de 1 a 5, correspondendo ao número de asteriscos que aparecem entre parêntesis rectos. Veja-se por exemplo o seguinte problema:

Grau de dificuldade

• A solução deste problema é:

Grau de dificuldade

• O problema supra tem grau de dificuldade 1, o nível mais baixo. Isto quer dizer que pode ser resolvido sem recurso a operações de emparelhamento. Veja-se agora um exemplo de um problema difícil:

Grau de dificuldade

• A solução deste problema é

• Este problema tem grau de dificuldade 5, o que quer dizer que é necessário recorrer a operações de emparelhamento pelo menos 4 vezes para o resolver.

Grau de dificuldade

• Um problema Sudoku bem construído deve ter apenas uma solução, determinada univocamente a partir do enunciado. Infelizmente, aparecem problemas publicados em jornais e revistas que não respeitam esta regra fundamental. O resultado é que apesar de você conseguir resolver o problema, a sua solução poderá ser diferente da solução publicada e dessa maneira ficará a pensar que a sua solução está errada quando poderá não ser esse o caso.

• Um outra consideração relativamente à qualidade de um Sudoku é que deve ser possível resolvê-lo recorrendo exclusivamente às operações acima referidas: Varrimento, Análise e Emparelhamento. Aparecem no entanto problemas publicados em que é necessário recorrer a métodos de tentativa e erro, uma vez que durante a solução se chega a uma situação em que não é possível avançar usando apenas os métodos usuais. Tal situação é evidentemente indesejável uma vez que o método de tentativa e erro não requer qualquer habilidade especial, baseando-se apenas em força bruta, tornando por outro lado a solução do problema desnecessariamente trabalhosa.

Qualidade

BIBLIOGRAFIA• http://novcruz.planetaclix.pt/whissdku.htm#GERAL

FIMTrabalho elaborado por: Miguel Monteiro