Um problema de sudoku é feito apagando números de um “tabuleiro completo”, que é a resposta. Então, quantos tabuleiros completos que obedecem às regras existem no total?
O tabuleiro 4×4 tem 288
Comecemos pelo menor, o 4×4 (blocos de 2×2, números de 1 a 4). Um exemplo:
Em cada coluna, linha e bloco, os números de 1 a 4 aparecem uma vez cada. Ao contar todos esses tabuleiros no computador, um por um, deu 288.
Fixando a primeira linha, a contagem fica mais fácil
Dá para reduzir o trabalho sem contar tudo.
Se você trocar os nomes dos números de um tabuleiro completo, como “trocar 1 e 2”, o resultado continua sendo um tabuleiro completo. Um tabuleiro com a primeira linha “2 1 3 4” vira um com a primeira linha “1 2 3 4” se você trocar o 1 e o 2. Ou seja, basta:
- contar só os tabuleiros com a primeira linha “1 2 3 4”, e
- multiplicar pelo número de jeitos de arrumar a primeira linha (4×3×2×1 = 24).
No 4×4, são 12 tabuleiros com a primeira linha “1 2 3 4”, e 12×24 = 288.
O tabuleiro 6×6 tem 28.200.960
É o tabuleiro com blocos de 2 linhas × 3 colunas, igual ao 6×6 Mini do NumberPlace. Com o mesmo método, fixando a primeira linha em “1 2 3 4 5 6”, são 39.168 tabuleiros. A primeira linha pode ser arrumada de 6×5×4×3×2×1 = 720 jeitos, então:
39.168 × 720 = 28.200.960
Dá 28.200.960, cerca de 100 mil vezes o do 4×4.
O tabuleiro 9×9 tem cerca de 6,67 × 10 elevado a 21
O número de tabuleiros 9×9 completos é
6.670.903.752.021.072.936.960
ou seja, cerca de 6,67 × 10 elevado a 21 (uns 6,7 sextilhões). Esse valor foi obtido em meados dos anos 2000, dividindo o tabuleiro em faixas e blocos, separando os casos e contando no computador. Mesmo contando 100 milhões por segundo, levaria mais de 2 milhões de anos.
Nesse total, há muitos tabuleiros que parecem iguais, só girados, espelhados ou com os nomes dos números trocados. Se esses tabuleiros “iguais na aparência” forem considerados um só, o total cai para cerca de 5,5 bilhões.
Existem ainda mais problemas
De um único tabuleiro completo, mudando quais números apagar, dá para fazer vários problemas diferentes. O NumberPlace cria na hora um tabuleiro completo novo a cada vez e apaga números dele para fazer o problema (Como se cria um sudoku). É muito improvável encontrar o mesmo problema duas vezes.
Quantos números é preciso deixar para a resposta ser única? Veja em Qual o mínimo de números dados?.
