Sudoku O que é o Sudoku Anti-Cavalo?
O Sudoku Anti-Cavalo é um sudoku normal com uma regra tirada do xadrez. Preencha a grelha de modo que:
- cada linha, coluna e caixa de 3×3 contenha os algarismos de 1 a 9 exatamente uma vez;
- e duas casas separadas por um salto de cavalo nunca tenham o mesmo algarismo — duas casas numa direção e uma para o lado, o L do cavalo no xadrez.
Nada na grelha assinala a regra. Vale em todo o lado, para cada casa, e uma casa tem entre duas e oito casas a um salto de cavalo. As vizinhas na diagonal não são casas de cavalo: duas casas que se tocam num canto podem ter o mesmo algarismo sempre que estejam em caixas diferentes.
Um salto de cavalo nunca fica numa linha ou coluna, mas pode ficar dentro de uma caixa: de R1C1 só alcança R2C3 e R3C2, e ambas já estão na caixa de R1C1. Cada casa, exceto os nove centros de caixa, tem exatamente duas das suas casas de cavalo dentro da sua própria caixa, onde as regras normais já proíbem repetir. Dos 224 pares de cavalo do tabuleiro, 72 são assim, por isso a regra acrescenta de facto 152.
O que lhe diz a regra do cavalo antes de colocar seja o que for?
Imagine as casas de cavalo de cada algarismo dado. Cada um retira o seu algarismo de até oito casas a mais do que num sudoku normal, e quantas depende de onde a casa está:
| Casa | Onde na grelha | Casas de cavalo | Fora da sua caixa | Vizinhas |
|---|---|---|---|---|
| R1C1 | Os quatro cantos (4 casas) | 2 | 0 | 20 |
| R1C2 | Casas da margem junto a um canto (8 casas) | 3 | 1 | 21 |
| R1C5 | O resto da margem (20 casas) | 4 | 2 | 22 |
| R2C2 | Um passo na diagonal a partir de um canto (4 casas) | 4 | 4 | 24 |
| R2C3 | O segundo anel, exceto essas e os seus quatro centros (16 casas) | 6 | 4 | 24 |
| R2C5 | O centro de cada lado do segundo anel (4 casas) | 6 | 6 | 26 |
| R3C3 | O 5×5 interior, exceto o seu centro (24 casas) | 8 | 6 | 26 |
| R5C5 | O centro | 8 | 8 | 28 |
As «vizinhas» são as casas que não podem repetir o algarismo de uma casa: as 20 da sua linha, coluna e caixa, mais as suas casas de cavalo fora da caixa. Em média, nas 81 casas, são 23,75, cerca de um quinto mais do que as 20 do sudoku normal. A regra é mais forte no meio da grelha e nos cantos não faz nada.
Por isso, num tabuleiro real, leve as casas de cavalo nas suas marcas a lápis desde o início:
É um gotejar constante, não uma enxurrada. Em 40 tabuleiros por nível, as casas de cavalo dos algarismos dados riscam uma mediana de 17 marcas a lápis no Fácil e 29 no Especialista antes de se colocar qualquer algarismo, e fixam logo quatro casas no Fácil e duas no Médio. Uma casa vazia no Fácil começa com 2,7 candidatos pela sua linha, coluna e caixa, e com 2,3 contando as casas de cavalo. O trabalho a sério vem depois: cada algarismo que coloca retira-se também das suas casas de cavalo, e assim a regra continua a render até ao fim.
A regra do cavalo faz mesmo alguma coisa?
Cada tabuleiro que esta página distribui é construído para que a solução dependa dela: o gerador retira algarismos enquanto o puzzle tiver uma única solução com a regra do cavalo, depois verifica os mesmos algarismos dados como sudoku normal e continua a escavar até deixarem de ter uma única. No tabuleiro acima:
Verificámos 160 tabuleiros novos, 40 por nível: todos têm uma única solução com a regra do cavalo e mais do que uma sem ela. Como sudoku normal, os algarismos dados do Fácil têm uma mediana de três soluções e até 27, os do Médio uma mediana de 20, e os do Difícil e do Especialista mais de 200 em todos os tabuleiros que experimentámos. Um resolvedor que ignore a regra do cavalo encalha em todos os tabuleiros de todos os níveis.
O gerador desta página já fazia isto bem antes desta reescrita — a sua verificação de unicidade era completa, e 160 de 160 tabuleiros passaram no mesmo teste. O que falhava era a velocidade: preenchia a grelha casa a casa sem olhar em frente, e o pior de 1.000 preenchimentos medidos precisou de mais de 100.000 passos. Um tabuleiro demorava uma mediana de 25 a 57 milissegundos e até 310 num computador, tudo enquanto a página carregava; num telemóvel isso é um bloqueio visível. A reescrita distribui o mesmo tipo de tabuleiro em cerca de 2 a 4 milissegundos, 9 no pior caso.
Em que diferem os quatro níveis?
Passámos 40 tabuleiros novos por nível por um resolvedor que sabe uma técnica de cada vez, e depois fomos retirando técnicas para ver que tabuleiros paravam. A regra do cavalo aqui não é uma técnica: como uma linha ou uma caixa, limita-se a retirar um algarismo colocado das casas que alcança.
| Nível | Algarismos dados | Marcas que a regra do cavalo risca logo | Casas que fixa | Os únicos bastam | Precisa de candidatos bloqueados | Precisa de um subconjunto | Além do nosso resolvedor |
|---|---|---|---|---|---|---|---|
| Fácil | 34–38 | 17 | 4 | 100% | 0% | 0% | 0% |
| Médio | 29–30 | 21 | 2 | 98% | 3% | 0% | 0% |
| Difícil | 25 | 26 | 0 | 83% | 15% | 0% | 3% |
| Especialista | 21 | 29 | 0 | 28% | 53% | 3% | 18% |
40 tabuleiros por nível do gerador desta página, semente fixa; medianas, e proporções arredondadas, por isso uma linha pode passar um pouco de 100. O nosso passo de candidatos bloqueados inclui a versão do cavalo: quando todos os lugares que restam a um algarismo numa unidade veem a mesma casa, por linha, coluna, caixa ou salto de cavalo, essa casa perde o algarismo. O resolvedor sabe também pares nus e trios e o X-Wing; os tabuleiros «além do nosso resolvedor» continuam a ter exatamente uma solução. O Fácil e o Médio ficam alguns algarismos abaixo do alvo quando é isso que é preciso para a regra do cavalo sustentar o tabuleiro.
Os níveis são degraus a sério, e o Especialista é um grande. Os únicos nus e os únicos escondidos, com as casas de cavalo limpas, terminam todos os tabuleiros Fácil e 39 de 40 do Médio. É no Difícil que chegam os candidatos bloqueados, em cerca de um tabuleiro em sete. No Especialista os únicos sozinhos terminam pouco mais de um tabuleiro em quatro: metade precisa de candidatos bloqueados, e cerca de um em seis vai além de tudo o que o nosso resolvedor conhece. Esta página prometia antes que o Difícil precisava de pares e de pares apontados; medido, o Difícil cai com únicos mais de quatro vezes em cinco.
O gerador preenche uma grelha que já cumpre a regra do cavalo e retira algarismos um a um, mantendo uma remoção apenas enquanto o puzzle continuar com exatamente uma solução; uma pesquisa que não consegue terminar responde «não provado» e o algarismo fica. Voltámos a resolver 160 tabuleiros novos com um contador à parte escrito para isso: todos tinham exatamente uma solução, e cada solução mantinha separados todos os pares de cavalo. A verificação de unicidade mais profunda precisou de 84 passos de pesquisa dos 4.000 permitidos.
Que nível deve jogar?
Comece no Fácil, mesmo que o sudoku normal lhe seja fácil. A regra do cavalo é invisível, e os primeiros tabuleiros servem para ganhar o hábito de verificar os L; no Fácil todos os tabuleiros caem com únicos assim que o faz. O Médio é a mesma competência com menos algarismos dados: ao início chega menos de graça e mais vem das casas de cavalo dos algarismos que coloca.
O Difícil acrescenta candidatos bloqueados em cerca de um tabuleiro em sete, incluindo a versão do cavalo, em que um algarismo apertado em duas ou três casas de uma caixa se exclui de toda a casa que todas alcançam. O Especialista é um degrau a sério: menos de um terço dos seus tabuleiros cai com únicos. Todos continuam a ter exatamente uma solução, e nenhum exige adivinhar.
O que corre mal num Sudoku Anti-Cavalo
- Esquecer a regra. Nada na grelha lha lembra. Um tabuleiro que encrava a meio é quase sempre um em que se colocou um algarismo sem limpar as suas casas de cavalo.
- Contar com os cantos. As duas casas de cavalo de um canto estão na sua própria caixa, por isso aí a regra não diz nada de novo. Olhe para o meio da grelha, onde uma casa alcança oito.
- Confundir com o rei. Casas que se tocam na diagonal não estão a um salto de cavalo. Em caixas diferentes podem ter o mesmo algarismo.
- Verificar só num sentido. O cavalo salta nos dois sentidos: um 5 em R3C4 exclui o 5 de R5C5, e um 5 em R5C5 excluí-lo-ia de R3C4. Cada par vale pelas duas pontas, por isso limpe o L inteiro de cada vez.
- Esperar que a regra substitua as normais. Acrescenta vizinhas, não tira nenhuma. Linhas, colunas e caixas continuam a fazer a maior parte do trabalho em cada tabuleiro.
De onde vem o Sudoku Anti-Cavalo?
Michal Stajszczak apresentou-o no mathpuzzle.com, o site de enigmas de Ed Pegg, a 20 de agosto de 2006, como «a new (I hope) variant of sudoku»: um sudoku normal em que os mesmos números nunca estão «knight move connected». Os autores de competição adotaram-no com nomes como «No Knight Step Sudoku», e ficou famoso em maio de 2020 graças ao «Miracle Sudoku» de Mitchell Lee, que combinava a regra anti-cavalo com uma regra anti-rei e uma proibição de vizinhos consecutivos, e partia de apenas dois algarismos dados. Alex Bellos publicou-o como o seu Monday Puzzle no Guardian a 18 de maio de 2020, e a resolução do canal de YouTube Cracking the Cryptic tornou-se viral.
O que fazem os botões?
Selecione uma casa e depois um algarismo de 1 a 9; a página abre no Médio. Ao selecionar uma casa, ficam realçadas a sua linha, coluna e caixa e as casas a um salto de cavalo, e um algarismo que se repita numa delas é assinalado como conflito. Por baixo da grelha:
- Notas liga e desliga as anotações a lápis. Um algarismo certo apaga-se das notas da sua linha, da sua coluna, da sua caixa e das suas casas de cavalo; um errado deixa as suas notas em paz.
- Apagar esvazia a casa selecionada; carregar duas vezes no mesmo algarismo faz o mesmo.
- Desfazer retira a última alteração a uma casa, mas não as notas que um algarismo certo apagou noutro sítio, nem o contador de erros.
- Dica preenche uma casa com a sua resposta, escolhida ao acaso e não como a casa que poderia deduzir a seguir.
- Resolver pergunta primeiro, depois preenche a grelha e para o temporizador.
- Novo Jogo distribui outro tabuleiro no nível atual; os botões de nível distribuem um no seu.
Os algarismos 1–9, as teclas de seta, Backspace ou Delete e Ctrl+Z funcionam a partir do teclado. O tabuleiro é guardado neste navegador depois de cada jogada e fica à sua espera quando voltar.
Para onde seguir
O Sudoku Anti-Cavalo é a variante que acrescenta uma regra invisível em vez de desenhar uma. O X Sudoku acrescenta as duas diagonais longas como unidades extra, e o Hyper Sudoku quatro caixas sombreadas; ambos mantêm a nova restrição à vista. O Sudoku Kropki é a outra variante do site assente em casas vizinhas, com pontos que dizem como se relacionam dois algarismos que se tocam, e o Killer Sudoku é o indicado se preferir aritmética a geometria.