Todos ja ouviram falar do jogo Sudoku, um ‘puzzle’ numérico que se popularizou no mundo todo e acabou sendo um hobby pra muita gente.
No sudoku clássico, o objetivo é preencher a grade 9 × 9 com dígitos de modo que cada coluna/linha e cada um dos nove subgrupos 3 × 3 que compõem a grade (também chamados de “caixas”, “blocos” ou “regiões”) contenham todos os dígitos de 1 a 9.
Por exemplo, o mesmo número inteiro não pode aparecer duas vezes na mesma linha, coluna ou em qualquer uma das nove sub-regiões 3 × 3 em um quadro 9 × 9.
Os jornais franceses publicaram diferentes variedades de quebra-cabeças de Sudoku no século 19, e o quebra-cabeça apareceu em livros de quebra-cabeças com o nome de Number Place desde 1979.
No entanto, o Sudoku moderno começou a ganhar popularidade apenas em 1986, quando foi publicado pela empresa japonesa Nikoli com o nome de Sudoku, que significa “número único”.
História do Sudoku
Os quebra-cabeças numéricos apareceram nos jornais no final do século 19, quando os fabricantes franceses começaram a fazer experiências com a remoção de números de quadrados mágicos.
Le Siècle, um jornal diário parisiense, publicou um quadrado mágico 9 × 9, parcialmente preenchido com subquarks 3 × 3, em 19 de novembro de 1892.
Não era Sudoku porque continha números de dois dígitos e exigia aritmética em vez de lógica para ser resolvido, mas tinha características principais comuns: cada linha, coluna e caixa-guia somavam o mesmo número.
Em 6 de julho de 1895, o rival de Le Siècle, La France, refinou este quebra-cabeça para torná-lo quase moderno como um Sudoku, e chamou-o francês: carré magique diabolique (“o quadrado mágico do mal”).
Ele simplificou o quebra-cabeça do quadrado mágico 9 × 9 para que cada linha, coluna e diagonais quebradas contivessem apenas números de 1 a 9, mas não selecionou os sub-blocos.
Embora não marcado, cada subtrama 3 × 3 na verdade contém os números de 1 a 9, e a restrição adicional nas diagonais inclinadas leva apenas a uma solução.
Esses quebra-cabeças semanais têm sido apresentados em jornais franceses como L’Écho de Paris por cerca de uma década, mas desapareceram durante a Primeira Guerra Mundial
O Sudoku moderno
Possivelmente projetado anonimamente por Howard Garns, um arquiteto aposentado de 74 anos e fabricante independente de quebra-cabeças de Connersville, Indiana, e publicado pela primeira vez em 1979 pela Dell Magazines como Number Place (os primeiros exemplos conhecidos de Sudoku moderno).
O nome de Garns sempre esteve presente na lista de colaboradores em edições da Dell Pencil Puzzles e Word Games que incluíam Number Place, e sempre esteve ausente nas edições que não incluíam.
Ele morreu em 1989 antes de ter a chance de ver seu trabalho como um fenômeno global.
Não está claro se Garns conhecia algum dos jornais franceses mencionados acima.
O enigma foi apresentado no Japão por Nikoli no jornal Monthly Nikolist em abril de 1984.
como Sūji wa dokushin ni kagiru (数字 は 独身 に 限 る), que também pode ser traduzido como “os números devem ser únicos” ou “os números são limitados a uma ocorrência” (em japonês, dokushin significa “uma pessoa”).
Mais tarde, o nome foi encurtado para Sudoku (数 独) por Maki Kaji (鍜 治 真 起, Kaji Maki), pegando apenas o primeiro kanji de palavras compostas, tornando uma versão mais curta.
“Sudoku” é uma marca registrada no Japão [11] e o quebra-cabeça é geralmente referido como Lugar Numérico (ナ ン バ ー プ レ ー ス, Nanbāpurēsu) ou, mais informalmente, a mala de duas palavras Num (ber) Pla (ce) (ナン プ レ, Nanpure).
Em 1986, Nikoli introduziu duas inovações: o número de dados foi reduzido para não mais que 32 e os quebra-cabeças tornaram-se “simétricos” (o que significa que os dados foram distribuídos em células rotacionalmente simétricas). Agora é publicado nas principais revistas japonesas, como Asahi Shimbun.
Variações do Sudoku
Embora a grade 9 × 9 com regiões 3 × 3 seja de longe a mais comum, existem muitas outras variações. Os exemplos de quebra-cabeças podem ser grades 4 × 4 com regiões 2 × 2; As grades 5 × 5 com regiões pentominós foram publicadas sob o nome Logi-5; O World Puzzle Championship incluiu uma grade 6 × 6 com regiões 2 × 3 e uma grade 7 × 7 com seis regiões heptômicas e uma região disjunta.
Grades maiores ou várias formas irregulares (com nomes diferentes como Suguru, Tectonic, Jigsaw Sudoku, etc.) também são possíveis.
O Times oferece uma grade “Dodeka Sudoku” 12 × 12 com 12 regiões de quadrados 4 × 3. As revistas Dell publicam regularmente um quebra-cabeça “Number Place Challenger” de 16 × 16 (usando os números de 1 a 16 ou as letras AP). Nikoli oferece aos gigantes 25 × 25 “Sudoku the Giant”. Um quebra-cabeça com uma grade de 100 × 100 chamado Sudoku-zilla foi publicado em 2010.
Mini sudoku
Sob o nome de “Mini Sudoku”, a variante 6 × 6 com regiões 3 × 2 aparece no jornal americano USA Today e mais. O objeto é o mesmo do Sudoku padrão, mas o quebra-cabeça usa apenas os números de 1 a 6.
Uma forma semelhante para solucionadores de quebra-cabeças mais jovens, chamada “Junior Sudoku”, apareceu em alguns jornais, como em algumas edições do Daily Mail.
Restrições adicionais
Outra variação popular é adicionar restrições de posicionamento de número além dos requisitos usuais de linha, coluna e campo.
A fronteira freqüentemente assume a forma de uma “dimensão” adicional; na maioria das vezes, os números nas diagonais principais da malha também devem ser exclusivos. Todos os quebra-cabeças mencionados “Number Place Challenger” pertencem a esta variante, assim como os quebra-cabeças Sudoku X do Daily Mail, que usam uma grade 6 × 6.
Alfabética Sudoku
Variantes alfabéticas, às vezes chamadas Wordoku, apareceram; não há diferença funcional em um quebra-cabeça, a menos que as letras signifiquem algo.
Algumas variantes, como o guia de TV, contêm a palavra lida ao longo da diagonal principal, linha ou coluna após a resolução; determinar a palavra com antecedência pode ser visto como uma ajuda para a solução. Wordoku pode conter outras palavras além da palavra principal.
“Quadratum latinum” é uma variação do Sudoku com algarismos romanos (I, II, III, IV, …, IX), proposta pela Hebdomada aenigmatum, uma revista mensal de quebra-cabeças latinos e palavras cruzadas. Como Wordoku, não é funcionalmente diferente do Sudoku regular, mas adiciona uma dificuldade visual ao uso de algarismos romanos.
Hyper Sudoku
O Hyper Sudoku usa a grade clássica 9 × 9 com regiões 3 × 3, mas define quatro regiões internas 3 × 3 adicionais, onde os números de 1 a 9 devem aparecer exatamente uma vez. Foi cunhado 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 no The International New York Times (International Herald Tribune).
Ele foi chamado pela primeira vez de Hyper Sudoku na variação de Sudoku favorita de Will Shortz (fevereiro de 2006). Também é conhecido como Windoku porque, com suas quatro áreas de malha interna sombreadas, lembra uma janela com varas de vidro.
Matemática de Sudoku
Esta seção se refere ao Sudoku clássico, exceto para quebra-cabeças, hiper e outras variantes.
Uma grade de Sudoku completa é um tipo especial de quadrado latino com a propriedade adicional de nenhum valor duplicado em nenhum dos nove blocos (ou células 3 × 3).
A relação entre às duas teorias é conhecida após provar que um padrão de primeira ordem que não menciona blocos é válido para o Sudoku se e somente se for válido para quadrados latinos.
O problema geral de resolver quebra-cabeças de Sudoku em n 2 × n 2 grades de n × n blocos é conhecido como NP-completo.
Muitos algoritmos de computador, como backtracking e call dance, podem resolver com sucesso a maioria dos quebra-cabeças 9 × 9, mas uma explosão combinatória ocorre à medida que n aumenta, criando restrições nas propriedades do Sudok que podem ser construídas, analisadas e resolvidas à medida que n aumenta. expresso como um problema com a coloração dos gráficos.
O objetivo é construir uma coloração 9 de um gráfico particular, dada uma coloração 9 parcial.
O menor número possível de pistas para um Sudoku adequado é 17 (comprovado em janeiro de 2012 e confirmado em setembro de 2013).
Mais de 49.000 Sudokus com 17 pistas foram encontrados, muitos deles por entusiastas japoneses.
Ao contrário do número de tabuleiros de Sudoku completos, o número mínimo de quebra-cabeças de Sudoku de 9 × 9 não é exatamente conhecido. (O quebra-cabeça mínimo é aquele em que você não pode descartar nenhuma pista sem perder a exclusividade da solução.)
No entanto, técnicas estatísticas em conjunto com o gerador de quebra-cabeças [39] mostram que (com um erro relativo de 0,065%) 3,10 × 10 37 quebra-cabeças mínimos e 2,55 × 10 25 são quebra-cabeças mínimos irrelevantes.
Veja mais sobre games aqui.