Generalized Sudoku (jigsaw sudoku)
Muita gente sabe o que é um sudoku: um puzzle com números que se joga numa tabela com $9$ linhas e $9$ colunas. O objetivo é simples: preencher a tabela com os números entre $1$ e $9$, seguindo umas quantas regras. As regras que devem ser seguidas não são complicadas, mas quem já experimentou resolver sudokus sabe que às vezes pode ser bastante difícil completar o puzzle!
Para além de resolver problemas, os matemáticos também gostam muito de generalizar. Suponhamos que temos uma série de características e que olhamos para todos os objetos que satisfazem essas restrições; uma generalização desses objetos pode ser dada ao ignorarmos uma das características consideradas.
Posto isto, uma generalização que pode ser feita dos puzzles de sudoku usuais é a forma das caixas: um tabuleiro de sudoku pode ser visto como um tabuleiro $3 \times 3$ onde cada célula é um quadrado também $3 \times 3$. Podemos alterar a forma dessas "caixas" mas manter as regras do sudoku: os números de $1$ a $9$ não podem estar repetidos nem nas linhas, nem nas colunas nem nas regiões (que já não são quadrados $3 \times 3$). No início do post há um exemplo de um puzzle de sudoku generalizado, incluímos agora outro:
Um amigo tem andado a resolver sudokus deste estilo e pediu-me que escrevesse um programa para verificar se estes puzzles têm solução única ou não. E eu escrevi! O programa é bastante simples e só precisa de dois ingredientes: um pouco de recursão e uma maneira de representar um tabuleiro de sudoku generalizado.
Contar soluções de um puzzle deste tipo é simples; varremos o tabuleiro de cima para baixo, da esquerda para a direita: quando estou a "olhar" para uma célula, vejo todas as opções que existem nessa célula, experimento uma, e vou preencher o resto do tabuleiro. Se a certa altura estiver a tentar preencher uma célula que não tem jogadas válidas é porque fiz um erro numa célula anterior e portanto tenho de andar para trás e tentar outras opções. Sempre que conseguir preencher o canto inferior direito, é porque encontrei uma solução válida para o puzzle. A título de exemplo incluo aqui a única solução encontrada para o puzzle que incluí em cima:
O código que conta as soluções pode ser encontrado aqui.
Para além de resolver problemas, os matemáticos também gostam muito de generalizar. Suponhamos que temos uma série de características e que olhamos para todos os objetos que satisfazem essas restrições; uma generalização desses objetos pode ser dada ao ignorarmos uma das características consideradas.
Posto isto, uma generalização que pode ser feita dos puzzles de sudoku usuais é a forma das caixas: um tabuleiro de sudoku pode ser visto como um tabuleiro $3 \times 3$ onde cada célula é um quadrado também $3 \times 3$. Podemos alterar a forma dessas "caixas" mas manter as regras do sudoku: os números de $1$ a $9$ não podem estar repetidos nem nas linhas, nem nas colunas nem nas regiões (que já não são quadrados $3 \times 3$). No início do post há um exemplo de um puzzle de sudoku generalizado, incluímos agora outro:
Um amigo tem andado a resolver sudokus deste estilo e pediu-me que escrevesse um programa para verificar se estes puzzles têm solução única ou não. E eu escrevi! O programa é bastante simples e só precisa de dois ingredientes: um pouco de recursão e uma maneira de representar um tabuleiro de sudoku generalizado.
Contar soluções de um puzzle deste tipo é simples; varremos o tabuleiro de cima para baixo, da esquerda para a direita: quando estou a "olhar" para uma célula, vejo todas as opções que existem nessa célula, experimento uma, e vou preencher o resto do tabuleiro. Se a certa altura estiver a tentar preencher uma célula que não tem jogadas válidas é porque fiz um erro numa célula anterior e portanto tenho de andar para trás e tentar outras opções. Sempre que conseguir preencher o canto inferior direito, é porque encontrei uma solução válida para o puzzle. A título de exemplo incluo aqui a única solução encontrada para o puzzle que incluí em cima:
O código que conta as soluções pode ser encontrado aqui.
