Sudoku - Sudoku
Sudoku (数独, Sudoku , dígito único) ( / s u d oʊ k U , - d ɒ k -, s ə - / , originalmente chamado Number Place ) é uma lógica baseados, combinatória número-colocação de quebra-cabeça . No sudoku clássico, o objetivo é preencher uma grade 9 × 9 com dígitos de modo que cada coluna, cada linha e cada uma das nove subgrades 3 × 3 que compõem a grade (também chamadas de "caixas", "blocos" ou " regiões ") contêm todos os dígitos de 1 a 9. O criador de quebra-cabeças fornece uma grade parcialmente preenchida, que para um quebra-cabeça bem posicionado tem uma única solução.
Os jornais franceses apresentavam variações dos quebra-cabeças Sudoku no século 19, e o quebra-cabeça tem aparecido desde 1979 em livros de quebra-cabeças com o nome de Number Place. No entanto, o Sudoku moderno só começou a ganhar popularidade em 1986, quando foi publicado pela empresa japonesa de quebra-cabeças Nikoli sob o nome de Sudoku, que significa "número único". Ele apareceu pela primeira vez em um jornal dos Estados Unidos, e depois no The Times (Londres), em 2004, graças aos esforços de Wayne Gould , que desenvolveu um programa de computador para produzir quebra-cabeças únicos rapidamente.
História
Predecessores
Os quebra-cabeças numéricos apareceram nos jornais no final do século 19, quando os criadores de quebra-cabeças franceses começaram a fazer experiências com a remoção de números de quadrados mágicos . Le Siècle , um diário de Paris, publicou um quadrado mágico 9 × 9 parcialmente preenchido com subquares 3 × 3 em 19 de novembro de 1892. Não era um Sudoku porque continha números de dois dígitos e exigia aritmética em vez de lógica para resolver, mas características-chave compartilhadas: cada linha, coluna e subquadrado somados ao mesmo número.
Em 6 de julho de 1895, o rival de Le Siècle , La France , refinou o quebra-cabeça para que fosse quase um Sudoku moderno e chamou-o carré magique diabolique ('quadrado mágico diabólico'). Ele simplificou o quebra-cabeça do quadrado mágico 9 × 9 para que cada linha, coluna e diagonais quebradas contivessem apenas os números de 1 a 9, mas não marcasse as subquadras. Embora não estivessem marcados, cada subquadrado 3 × 3 realmente compreendia os números 1–9, e a restrição adicional nas diagonais quebradas levou a apenas uma solução.
Esses quebra-cabeças semanais foram destaque em jornais franceses como L'Écho de Paris por cerca de uma década, mas desapareceram na época da Primeira Guerra Mundial .
Sudoku moderno
O Sudoku moderno foi provavelmente projetado anonimamente por Howard Garns , um arquiteto aposentado de 74 anos e construtor autônomo de quebra-cabeças de Connersville, Indiana , e publicado pela primeira vez em 1979 pela Dell Magazines como Number Place (os primeiros exemplos conhecidos do Sudoku moderno). O nome de Garns sempre esteve presente na lista de colaboradores nas 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 sua criação como um fenômeno mundial. Se Garns estava ou não familiarizado com algum dos jornais franceses listados acima, não está claro.
O quebra-cabeça foi apresentado no Japão por Maki Kaji (鍜 治 真 起, Kaji Maki ) , presidente da empresa de quebra-cabeças Nikoli, no jornal Monthly Nikolist em abril de 1984 como Sūji wa dokushin ni kagiru (数字 は 独身 に 限 る) , que pode ser traduzido como "os dígitos devem ser únicos" ou como "os dígitos são limitados a uma ocorrência" (em japonês, dokushin significa uma "pessoa solteira"). O nome foi posteriormente abreviado para Sudoku (数 独), levando apenas o primeiro kanji de palavras compostas para formar uma versão mais curta. "Sudoku" é uma marca registrada no Japão e o quebra-cabeça é geralmente conhecido como Number Place (ナ ン バ ー プ レ ー ス, Nanbāpurēsu ) ou, mais informalmente, uma redução das duas palavras, Num (ber) Pla (ce) (ナ ン プ レ, Nanpure ) . Em 1986, Nikoli introduziu duas inovações: o número de dados foi restrito a 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 nos principais periódicos japoneses, como o Asahi Shimbun .
O cientista cognitivo Jeremy Grabbe descobriu que o Sudoku envolvia uma área da cognição chamada memória de trabalho . Um experimento subsequente de Grabbe mostrou que a prática de Sudoku de rotina pode melhorar a memória de trabalho em pessoas mais velhas.
Espalhe fora do Japão
Em 1997, o juiz de Hong Kong, Wayne Gould, viu um quebra-cabeça parcialmente concluído em uma livraria japonesa. Ao longo de seis anos, ele desenvolveu um programa de computador para produzir quebra-cabeças exclusivos rapidamente. Sabendo que os jornais britânicos têm uma longa história de publicação de palavras cruzadas e outros quebra-cabeças, ele promoveu o Sudoku para o The Times na Grã-Bretanha, que o lançou em 12 de novembro de 2004 (chamando-o de Su Doku). A primeira carta ao The Times sobre Su Doku foi publicada no dia seguinte, em 13 de novembro, de Ian Payn, de Brentford , reclamando que o quebra-cabeça o fez perder sua parada no tubo . Os quebra-cabeças do Sudoku se espalharam rapidamente para outros jornais como um recurso regular.
A rápida ascensão de Sudoku na Grã-Bretanha de uma relativa obscuridade para um recurso de primeira página em jornais nacionais atraiu comentários na mídia e paródia (como quando The Guardian 's G2 seção si anunciado como o primeiro suplemento de jornal com uma grade de Sudoku em cada página ) Reconhecendo os diferentes apelos psicológicos de quebra-cabeças fáceis e difíceis, The Times apresentou ambos, lado a lado, em 20 de junho de 2005. A partir de julho de 2005, o Canal 4 incluiu um jogo diário de Sudoku em seu serviço de teletexto . Em 2 de agosto, o guia de programação da BBC, Radio Times, apresentou um Super Sudoku semanal com grade 16 × 16.
Nos Estados Unidos, o primeiro jornal a publicar um quebra-cabeça de Sudoku de Wayne Gould foi The Conway Daily Sun (New Hampshire), em 2004.
O primeiro programa de Sudoku de TV ao vivo do mundo, Sudoku Live , foi um concurso de quebra - cabeças transmitido pela primeira vez em 1 de julho de 2005, na Sky One . Foi apresentado por Carol Vorderman . Nove equipes de nove jogadores (com uma celebridade em cada equipe) representando regiões geográficas competiram para resolver um quebra-cabeça. Cada jogador tinha um dispositivo portátil para inserir os números correspondentes às respostas de quatro células. Phil Kollin de Winchelsea, Inglaterra , foi o vencedor do grande prêmio da série, levando para casa mais de £ 23.000 em uma série de jogos. O público em casa estava em uma competição interativa separada, que foi vencida por Hannah Withey de Cheshire .
Mais tarde, em 2005, a BBC lançou o SUDO-Q , um game show que combinava Sudoku com conhecimento geral. No entanto, ele usou apenas quebra-cabeças 4 × 4 e 6 × 6. Quatro temporadas foram produzidas antes do show terminar em 2007.
Em 2006, um site de Sudoku publicou a canção tributo ao Sudoku do compositor Peter Levy, mas rapidamente teve que retirar o arquivo MP3 devido ao tráfego intenso. As rádios britânicas e australianas pegaram a música, que deve aparecer em um documentário britânico do Sudoku. A Embaixada do Japão também indicou a música para um prêmio, com Levy conversando com a Sony no Japão para lançar a música como single.
O software Sudoku é muito popular em PCs, sites e telefones celulares. Ele vem com muitas distribuições de Linux . O software também foi lançado em consoles de videogame, como Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , leitor de e-book Nook , tablet Kindle Fire, vários modelos de iPod e iPhone . Muitos telefones Nokia também tinham Sudoku. Na verdade, apenas duas semanas depois que a Apple Inc. estreou a App Store online em sua iTunes Store em 11 de julho de 2008, cerca de 30 jogos Sudoku diferentes já estavam nela, criados por vários desenvolvedores de software , especificamente para o iPhone e iPod Touch. Um dos videogames mais populares com Sudoku é Brain Age: Treine seu cérebro em minutos por dia! . Bem recebido crítica e comercialmente, ele gerou elogios especiais por sua implementação do Sudoku e vendeu mais de 8 milhões de cópias em todo o mundo. Devido à sua popularidade, a Nintendo fez um segundo jogo Brain Age intitulado Brain Age 2 , que tem mais de 100 novos quebra-cabeças Sudoku e outras atividades.
Em junho de 2008, um júri australiano relacionado a drogas que custou mais de A $ 1 milhão foi abortado quando foi descoberto que cinco dos doze jurados estavam jogando Sudoku em vez de ouvir as evidências.
Variantes
Variações de tamanhos de grade ou formas de região
Embora a grade 9 × 9 com regiões 3 × 3 seja de longe a mais comum, existem muitas outras variações. Os quebra-cabeças de amostra 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 Campeonato Mundial de Quebra-cabeças apresentou uma grade 6 × 6 com regiões 2 × 3 e uma grade 7 × 7 com seis regiões heptominós e uma região disjunta. Grades maiores também são possíveis, ou diferentes formas irregulares (sob vários nomes como Suguru , Tectonic , Jigsaw Sudoku etc.). O Times oferece um "Dodeka Sudoku" de 12 × 12 grade com 12 regiões de 4 × 3 quadrados. A Dell Magazines publica regularmente quebra-cabeças 16 × 16 "Number Place Challenger" (usando os números 1–16 ou as letras AP). Nikoli oferece 25 × 25 gigantes "Sudoku the Giant". Um quebra-cabeça de grade 100 × 100 apelidado de Sudoku-zilla foi publicado em 2010.
Mini Sudoku
Sob o nome de "Mini Sudoku", uma variante 6 × 6 com regiões 3 × 2 aparece no jornal americano USA Today e em outros lugares. 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 os solucionadores mais jovens de quebra-cabeças, chamada "O Sudoku Júnior", apareceu em alguns jornais, como em algumas edições de The Daily Mail .
Impondo restrições adicionais
Outra variante comum é adicionar limites à colocação de números além dos requisitos usuais de linha, coluna e caixa. Freqüentemente, o limite assume a forma de uma "dimensão" extra; o mais comum é exigir que os números nas diagonais principais da grade também sejam únicos. Os quebra-cabeças mencionados "Number Place Challenger" são todos desta variante, assim como os quebra-cabeças Sudoku X do The Daily Mail , que usam grades 6 × 6.
Sudoku Assassino
A variante Killer Sudoku combina elementos de Sudoku e Kakuro .
Sudoku Alfabético
Variações alfabéticas surgiram, às vezes chamadas de Wordoku ; nenhuma diferença funcional existe no quebra-cabeça, a menos que as letras signifiquem algo. Algumas variantes, como no Guia de TV , incluem uma palavra lida ao longo de uma diagonal principal, linha ou coluna depois de resolvida; determinar a palavra com antecedência pode ser visto como um auxílio na solução. Um 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 o Wordoku, não apresenta diferença funcional de um Sudoku normal, mas adiciona a dificuldade visual de usar algarismos romanos.
Hyper Sudoku / Windoku
O Hyper Sudoku ou Windoku usa a grade clássica 9 × 9 com regiões 3 × 3, mas define quatro regiões interiores 3 × 3 adicionais nas quais os números de 1 a 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 The International New York Times (International Herald Tribune). A primeira vez que foi chamado de Hyper Sudoku foi em Will Shortz 's Favorite Sudoku Variations (fevereiro de 2006). Também é conhecido como Windoku porque, com as quatro regiões internas da grade sombreadas, ela se assemelha a uma janela com barras de vidro.
Sudoku Twin
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 após cada grade individual ter sido pelo menos parcialmente resolvida.
Outras variantes
Os quebra-cabeças construídos a partir de mais de duas grades também são comuns. Cinco grades 9 × 9 que se sobrepõem nas regiões dos cantos na forma de um quincunce são conhecidas no Japão como Gattai 5 (cinco fundidas) Sudoku. No The Times , The Age e The Sydney Morning Herald , essa forma de quebra-cabeça é conhecida como Samurai Sudoku. O Baltimore Sun e o Toronto Star publicam um quebra-cabeça dessa variante (intitulado High Five) em sua edição de domingo. Freqüentemente, nenhum dado é colocado nas regiões sobrepostas. Grades sequenciais, em oposição à sobreposição, também são publicadas, com valores em locais específicos em grades que precisam ser transferidos para outras.
Uma versão de mesa do Sudoku pode ser jogada com um baralho de Set de 81 cartas padrão (veja Jogo de Set ). Um quebra-cabeça tridimensional de Sudoku foi publicado no The Daily Telegraph em maio de 2005. O Times também publica uma versão tridimensional sob o nome de Tredoku. Além disso, uma versão Sudoku do Cubo de Rubik é chamada de Cubo Sudoku .
Muitas outras variantes foram desenvolvidas. Alguns são formatos diferentes no arranjo de grades 9 × 9 sobrepostas, como borboleta, moinho de vento ou flor. Outros variam a lógica para resolver a grade. Um deles é "Greater Than Sudoku". Neste, uma grade 3 × 3 do Sudoku é dada com 12 símbolos de Maior que (>) ou Menor que (<) na linha comum dos dois números adjacentes. Outra variante da lógica da solução é o "Sudoku sem noção", no qual 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". Uma nova variante mistura Sudoku com o quebra-cabeça de ladrilhos 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. Exemplos e outras variantes podem ser encontrados no Glossário de Sudoku .
Matemática do Sudoku
.svg)
Esta seção refere-se ao Sudoku clássico, desconsiderando quebra-cabeças, hiper e outras variantes.
Uma grade Sudoku completa é um tipo especial de quadrado latino com a propriedade adicional de nenhum valor repetido em qualquer um dos nove blocos (ou caixas de células 3 × 3). A relação entre as duas teorias é conhecida, após ter sido comprovado que uma fórmula de primeira ordem que não menciona blocos é válida para o Sudoku se e somente se for válida 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 dancing links, podem resolver a maioria dos quebra-cabeças 9 × 9 com eficiência, mas a explosão combinatória ocorre à medida que n aumenta, criando limites para as propriedades de Sudokus que podem ser construídos, analisados e resolvidos à medida que n aumenta. Um quebra-cabeça Sudoku pode ser expresso como um problema de coloração de gráfico . 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. Sudokus com 18 pistas e simetria rotacional foram encontrados, e há pelo menos um Sudoku que tem 18 pistas, exibe simetria diagonal bidirecional e é automórfico . O número máximo de pistas que podem ser fornecidas sem renderizar uma solução única é quatro a menos de uma grade completa (77); se duas instâncias de dois números cada estão faltando nas células que ocupam os cantos de um retângulo ortogonal, e exatamente duas dessas células estão dentro de uma região, os números podem ser atribuídos de duas maneiras. Como isso se aplica aos quadrados latinos em geral, a maioria das variantes do Sudoku tem o mesmo máximo.
O número de grades de solução de Sudoku 9 × 9 clássico é 6.670.903.752.021.072.936.960 (sequência A107739 no OEIS ), ou cerca6,67 × 10 21 . Isso é mais ou menos1,2 × 10 −6 vezes o número de quadrados latinos 9 × 9. Vários outros tamanhos de grade também foram enumerados - consulte o artigo principal para obter detalhes. O número de soluções essencialmente diferentes, quando simetrias como rotação, reflexão, permutação e reclassificação são levadas em consideração, mostrou-se ser apenas 5.472.730.538 (sequência A109741 no OEIS ).
Ao contrário do número de grades de Sudoku completas, o número mínimo de quebra-cabeças de Sudoku de 9 × 9 não é conhecido com precisão. (Um quebra-cabeça mínimo é aquele em que nenhuma pista pode ser excluída sem perder a exclusividade da solução.) No entanto, as técnicas estatísticas combinadas com um gerador de quebra-cabeça mostram que cerca de (com erro relativo de 0,065%) 3,10 × 10 37 quebra-cabeças mínimos e 2,55 × 10 Existem 25 quebra-cabeças mínimos não essenciais.
Competições
- O primeiro Campeonato Mundial de Sudoku foi realizado em Lucca , Itália , de 10 a 12 de março de 2006. A vencedora foi Jana Tylová, da República Tcheca . A competição incluiu inúmeras variantes.
- O segundo Campeonato Mundial de Sudoku foi realizado em Praga, República Tcheca , de 28 de março a 1º de abril de 2007. O campeão individual foi Thomas Snyder, dos EUA. O time campeão foi o Japão.
- O terceiro Campeonato Mundial de Sudoku foi realizado em Goa, Índia , de 14 a 16 de abril de 2008. Thomas Snyder repetiu-se como o campeão geral individual e também ganhou o primeiro Troféu Clássico (um subconjunto da competição contando apenas com o Sudoku clássico). A República Tcheca venceu a competição por equipes.
- O quarto Campeonato Mundial de Sudoku foi realizado em Žilina , Eslováquia , de 24 a 27 de abril de 2009. Depois que o ex-campeão Thomas Snyder dos EUA venceu a qualificação geral, Jan Mrozowski da Polônia saiu de um playoff de 36 competidores para se tornar o novo Sudoku Mundial Campeão. A Eslováquia, nação anfitriã, emergiu como a melhor equipe em uma competição separada de times de três membros.
- O quinto Campeonato Mundial de Sudoku foi realizado na Filadélfia, Pensilvânia , de 29 de abril a 2 de maio de 2010. Jan Mrozowski da Polônia defendeu com sucesso seu título mundial na competição individual, enquanto a Alemanha venceu um evento por equipes separado. Os quebra-cabeças foram escritos por Thomas Snyder e Wei-Hwa Huang , ambos ex-campeões de Sudoku dos Estados Unidos.
- O 12º Campeonato Mundial de Sudoku (WSC) foi realizado em Bangalore, Índia , de 15 a 22 de outubro de 2017. Kota Morinishi, do Japão, venceu o WSC Individual e a China venceu o evento por equipes.
- O 13º Campeonato Mundial de Sudoku aconteceu na República Tcheca.
- Nos Estados Unidos, o The Philadelphia Inquirer Sudoku National Championship foi realizado três vezes, cada vez oferecendo um prêmio de $ 10.000 para o vencedor da divisão avançada e uma vaga no US National Sudoku Team viajando para o campeonato mundial. Os vencedores do evento foram Thomas Snyder (2007), Wei-Hwa Huang (2008) e Tammy McLeod (2009). No evento de 2009, o terceiro colocado finalista na divisão avançada, Eugene Varshavsky, teve um péssimo desempenho no palco depois de definir um tempo de qualificação muito rápido no papel, que chamou a atenção de organizadores e competidores, incluindo o ex-campeão Thomas Snyder, que pediu uma reconsideração dos organizadores seus resultados devido a uma suspeita de trapaça. Após uma investigação e um novo teste de Varshavsky, os organizadores o desclassificaram e deram a Chris Narrikkattu o terceiro lugar.
Veja também
Referências
Leitura adicional
- Delahaye, Jean-Paul, "The Science Behind Sudoku" , Scientific American , junho de 2006.
- Provan, J. Scott, "Sudoku: Strategy Versus Structure", American Mathematical Monthly , outubro de 2009. Publicado também como um relatório técnico da Universidade da Carolina do Norte UNC / STOR / 08/04 , 2008.
links externos
- 'Sudoku Variations' de Fun With Puzzles
- Sudoku em Curlie - uma lista ativa de links de Sudoku
- Próxima jogada de quebra-cabeças 'Pai do Sudoku' ( BBC )