Sudoku

 Nota: Não confundir com sodoku.

Um típico problema de sudoku ...

... e sua solução, marcada em vermelho.

Sudoku,^[1] por vezes escrito Su Doku (数独, sūdoku) é um jogo baseado na colocação lógica de números. O objetivo do jogo é a colocação de números de 1 a 9 em cada uma das células vazias numa grade de 9×9, constituída por 3×3 subgrades chamadas regiões. O quebra-cabeça contém algumas pistas iniciais, que são números inseridos em algumas células, de maneira a permitir uma indução ou dedução dos números em células que estejam vazias. Cada coluna, linha e região só pode ter um número de cada um dos 1 a 9. Resolver o problema requer apenas raciocínio lógico e algum tempo. Os problemas são normalmente classificados em relação à sua realização. O aspecto do sudoku lembra outros quebra-cabeças de jornal.

No Brasil, o sudoku é publicado pelas Revistas Coquetel (Ediouro) desde o setembro de 2005.^[2] No ano seguinte, a Editora JBC lançou um manual de como jogar soduku em mangá (nome dado aos quadrinhos japoneses) intitulado Sudoku & Mangá, roteirizado por Jay Morrison e ilustrado por Atsuhisa Okura.^[3] Em Portugal, ele começou a ser publicado em maio de 2005 pelo jornal Público. Actualmente, já existem muitas publicações portuguesas de formato bolso, como é o caso do Extreme Sudokus da Editora Momentos de Relax ou Super Sudokus da Editora JEA. Estão disponíveis no mercado brasileiro duas opções. A revista Sudoku (tamanho grande) e Sudoku de bolso, em formato mais portátil.

A palavra "sudoku" é de origem japonesa. Ela é uma junção de duas palavras japonesas: "su" significa "número" e "doku" significa "único". Portanto, "sudoku" pode ser traduzido aproximadamente como "números únicos".

A palavra "sudoku" em si foi cunhada pelo empresário japonês Maki Kaji, que fez uma contração da frase japonesa "cada número deve ser individual".^[4]

Um jogo de sudoku nonominó, como visto no The Sunday Telegraph ...

... e sua solução marcado com números vermelhos.

Apesar de a grade 9×9 com regiões 3×3 ser de longe a mais conhecida, diversas variações abundam: amostras do enigma podem ser grades de 4×4 com regiões 2×2; grades 5×5 regiões pentaminó têm sido publicadas sob o nome Logi-5; o World Puzzle Championship apresentou anteriormente grades 6×6 com regiões 2×3 e grades 7×7 com 6 regiões heptominó e com regiões desconexas. Daily SuDoku apresenta novas grades 4×4, 6×6 e mais simples 9×9 todos os dias com Daily SuDoku for Kids (Sudoku diário para crianças).^[5] Mesmo as grades 9×9 não são sempre padrões, com a Ebb publicando regularmente alguns com regiões nonominó (também conhecido como variação quebra-cabeça); o Campeonato Estadunidense de Enigmas de 2005 tinha um sudoku com regiões em paralelogramo que circundavam a parte e×terior do enigma, como se a grade fosse uma arruela quadrada. Grades maiores também são possíveis, como o Daily SuDoku's 12×12 Monster SuDoku. O Times igualmente oferece um com grade 12×12: o Dodeka sudoku, com 12 regiões, cada uma sendo 4×3. O sítio Conceptis Puzzles oferece, gratuitamente, um puzzle 12×12 (Mega Sudoku) por semana. A Dell regularmente publica o 16×16 Number Place Challenger (a variação 16×16 geralmente utiliza 1 até G ao invés do 0 até o F utilizado em notações hexadecimais), e a Nikoli oferece o enorme 25×25 Sudoku the Giant.

Uma quebra-cabeça do jogo Hyper Sudoku ...

... e sua solução marcado nos números faltantes.

Hyper Sudoku usa a grade clássica 9×9 com regiões 3×3, mas define quatro regiões interiores adicionais 3×3 nas quais os números 1–9 devem aparecer exatamente uma vez. Foi inventado por Peter Ritmeester e publicado pela primeira vez por ele no jornal holandês NRC Handelsblad em outubro de 2005, e desde abril de 2007 diariamente no International New York Times (International Herald Tribune). A primeira vez que foi chamado de Hyper Sudoku foi nas variações favoritas de sudoku de Will Shortz (fevereiro de 2006). Também é conhecido como Windoku porque com as quatro regiões internas da grade sombreadas, lembra uma janela com barras envidraçadas.^[6]

No Twin Sudoku duas grades regulares compartilham uma caixa 3×3. Este é um dos muitos tipos possíveis de grades sobrepostas. As regras para cada grade individual são as mesmas do Sudoku normal, mas os dígitos na seção sobreposta são compartilhados por cada metade. Em algumas composições, nenhuma grade individual pode ser resolvida sozinha – a solução completa só é possível depois que cada grade individual tiver sido pelo menos parcialmente resolvida.

X-Sudoku (também sudoku diagonal ou mágico) é uma variante em que (além das condições do sudoku normal) cada número só pode aparecer uma vez em cada uma das duas diagonais principais, que juntas formam um “X”. Sudoku e outras revistas de quebra-cabeças publicam regularmente X-Sudoku em vários tamanhos. Além do tamanho padrão 9×9, também ocorrem outros tamanhos, como 8×8 (com blocos 2×4). Neste último caso, as duas diagonais não possuem um campo de corte comum. Para o X-Sudoku no tamanho padrão 9×9, a determinação do número mínimo de campos pré-atribuídos não é resolvida. Existem X-Sudokus claramente solucionáveis ​​com 12 padrões, mas não se sabe se existe algum com 11 inadimplências.^[7]

Variações alfabéticas também surgiram; não há nenhuma diferença funcional no passatempo, a não ser se as letras significam alguma algo. Recentes variantes têm esta característica, geralmente em forma de palavra lida ao longo da diagonal principal depois de encontrada a solução; determinar a palavra antecipadamente pode ser visto como um auxílio para a solução.

Uma quebra-cabeça do jogo Wordoku ...

... e a solução marcado com letras vermelhos.

Como o sudoku padrão não envolve aritmética, os dígitos de 1 a 9 podem ser substituídos por nove símbolos arbitrários, como formas geométricas, algarismos romanos (por exemplo, Quadratum latinum, publicado na revista de quebra-cabeças latinas Hebdomada aenigmatum) ou letras, e não há função diferença. O Code Doku^[8] inventado por Steve Schaefer tem uma sentença completa embutida no passatempo; o Super Wordoku, ou apenas Wordoku da Top Notch^[9] contém duas palavras de nove letras, uma em cada diagonal. É discutível se estas formas são verdadeiros sudokus, contudo elas contêm uma solução "linguisticamente" válida e não podem necessariamente serem resolvidas inteiramente através da lógica, fazendo-se necessário que o solucionador determine a palavra embutida. Top Notch diz que esta característica foi projetada para derrotar os programas de computadores de solução.

Algumas variantes, como na TV Guide Magazine, incluem a leitura de uma palavra ao longo de uma diagonal principal, linha ou coluna, uma vez resolvida; determinar a palavra antecipadamente pode ser visto como uma ajuda na resolução. Um Wordoku pode conter outras palavras além da palavra principal.

Quebra-cabeças construídos a partir de mais de duas grades também são comuns. Outras variações comuns é ter restrições adicionais, forçando a colocação de números além dos requisitos normais para as linhas, colunas e regiões. Geralmente, a restrição toma forma de uma "dimensão" extra; o mais comum é que os números nas diagonais principais da grade também devam ser únicos (não podendo ser repetidos). O supracitado Number Place Challenger faz parte desta variante, assim como o Sudoku X no Daily Mail, o qual utiliza grades 6×6. O Daily Mail também apresenta o Super Sudoku X em sua edição de final de semana: uma grade 8×8 na qual as linhas, colunas e diagonais principais, blocos 2×4 e blocos 4×2 contêm cada número apenas uma vez, bem como as suas diagonais principais; Conceptis Puzzles apresenta o Diagonal Sudoku em uma grade 9×9 e blocos 3×3 com as mesmas regras supracitadas.

Uma dimensão também utilizada é com os dígitos com as mesmas posições relativas em suas respectivas regiões; porém as regiões não formam um paralelogramo e possuem formatos variados e desconexos, neste formato Conceptis Puzzles apresenta o Irregular Sudoku,^[10] enquanto que algumas editoras também se utilizam de cores diferentes em cada grupo desconexo para uma melhor identificação de cada grupo de números.

Também pode ser encontrado o Circular Sudoku, também conhecido como Target Sudoku, inventado pelo matemático Peter Higgins.^[11][12] Nessa variante, todos os números devem aparecer em círculos concêntricos bem como em todos os pares de fatias adjacentes.

Um quebra-cabeça de Killer Sudoku ...

... e a solução dele marcado em números vermelhos.

Outros tipos de restrições extras podem ser de natureza aritmética, tais como, exigindo que os números em um delineado segmento da grade tenham uma soma ou um produto específico. Um exemplo pode ser o Killer Sudoku, simplesmente conhecido como addoku do The Times, que combina elementos de sudoku e kakuro'. Apesar do nome em inglês, os addokus mais simples pode ser mais fácil de resolver do que o sudokus normais, dependendo da habilidade do solucionador em aritmética mental; os mais difíceis, porém, podem levar horas para serem resolvidos. Outros como o Magic Sudoku adicionam algumas restrições (diagonais de 1 a 9, e cores) ao sudoku-padrão para resolvê-lo com menos números.^[13]

Muitas outras variantes foram desenvolvidas.^[14][15][16] Alguns têm formatos diferentes no arranjo de grades 9×9 sobrepostas, como borboleta, moinho de vento ou flor.^[17] Outros variam a lógica para resolver a grade. Um deles é “Maior que Sudoku”. Nisso, uma grade 3×3 do sudoku é fornecida com 12 símbolos de Maior que (>) ou Menor que (<) na linha comum dos dois números adjacentes.^[18]

Outra variante da lógica da solução é "Clueless Sudoku", em que nove grades de sudoku 9×9 são colocadas cada uma em uma matriz 3×3. A célula central em cada grade 3×3 de todos os nove quebra-cabeças é deixada em branco e forma um décimo quebra-cabeça sudoku sem nenhuma célula concluída; portanto, "sem noção".^[19] Uma nova variante mistura o sudoku com o quebra-cabeça de peças deslizantes no sudoku Slide Extreme. Nesta variante, todas as posições são preenchidas. As peças são movidas para a posição adequada para resolver o quebra-cabeça. Esta variante contém power-ups e um modo de campanha.

Passatempos construídos a partir de múltiplas grades sudoku são comuns: cinco grades 9x9 sobrepostas umas às outras nas regiões dos cantos são conhecidas no Japão como Gattai 5 (cinco unidos) Sudoku. No The Times e no The Sydney Morning Herald, esta forma de passatempo é conhecida como Samurai SuDoku.^[20] No Conceptis Puzzles, são publicados semanalmente os Multi Sudoku, que são compostos de duas a cinco grades sobrepostas. Passatempos com vinte ou mais grades sobrepostas não são incomuns em algumas publicações japonesas. Geralmente, nenhuma dica é encontrada nas regiões sobrepostas.

Outros exemplos únicos de variação incluem um passatempo sudoku tridimensional inventado por Dion Church e publicado no Daily Telegraph em maio de 2005, e um sudoku de 100×100 criado por Michael Metcaff e publicado para o grupo do Yahoo! Sudokuworld.

O problema geral de solucionar enigmas sudoku em tabuleiros ${\displaystyle n^{2}\times n^{2}}$ de blocos ${\displaystyle n\times n}$ é conhecido como NP-completo.^[21] Isto dá algumas indicações de porque o sudoku é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos, o problema é finito e pode ser solucionado através de um autômato finito probabilístico que conheça toda a árvore do jogo. Solucionar enigmas sudoku (assim como qualquer outro problema NP-difícil) pode ser expresso como sendo um problema de coloração de grafos. O objetivo do enigma em sua forma-padrão é se construir um grafo apropriado de nove colorações, informando, parcialmente, as nove colorações. O grafo em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados ${\displaystyle (x,\,y)}$, onde ${\displaystyle x}$ e ${\displaystyle y}$ são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por ${\displaystyle (x,\,y)}$ e ${\displaystyle (x',\,y')}$ são conectados por uma borda se e apenas se ${\displaystyle x=x'\ \lor y=y'\,\lor (\lceil x/3\rceil =\lceil x'/3\rceil \land \lceil y/3\rceil =\lceil y'/3\rceil )}$.

O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o sudoku é também um quadrado latino. Há significativamente menos soluções de grades de sudoku válidas do que os quadrados latinos, porque o sudoku impõe restrições de região adicionais. Apesar disso, o número de soluções de sudoku para uma grade-padrão de 9x9 foi calculado em 2005 por Bertram Felgenhauer como sendo 6,670,903,752,021,072,936,960 (6.671×10²¹).^[22] Este número é igual a ${\displaystyle 9!\times 72^{2}\times 2^{7}\times 27.704.267.971}$, o último fator o qual é um número primo. O resultado é derivado através da lógica e computação força bruta. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5 472 730 538 soluções.^[23] O número de soluções válidas para a variação do sudoku de uma grade 16x16 é desconhecido.

• Algoritmo de sudoku

Referências

• Plataforma Sudoku em português para competições globais, estatísticas pessoais e tutoriais
• KillerSudoku.com
• Sudoku Brasil
• Sudoku Hard