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.

A título de exemplo, suponha-se que estamos à procura de todos os polígonos que satisfazem as seguintes restrições:

• Tem quatro lados;
• Todos os lados são iguais;
• Todos os lados fazem ângulos de $90^\circ$ entre si.

É fácil de ver que o quadrado é o único polígono que satisfaz estas duas retrições. Podemos agora perguntar-nos sobre quais os polígonos que obteríamos se levantarmos uma das restrições, generalizando deste modo o quadrado: se já não impusermos que os lados façam um ângulo de $90^\circ$ entre si, passamos a obter quadrados e losangos. Neste contexto podemos considerar que o losango é uma generalização do quadrado, ou que o quadrado é um losango específico. Se tivessemos levantado a restrição dos lados todos iguais, obtínhamos rectângulos: é por isso que dizemos que o quadrado também é um rectângulo, porque o quadrado é um rectângulo mais específico.

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.

Everyone knows what a sudoku is: a puzzle with numbers played on a grid with $9$ rows and $9$ columns. The goal is simple: to fill the grid with the numbers from $1$ to $9$ whilst following some rules. Despite the rules being simple, even seasoned players know the puzzles sometimes can be quite tricky!

Besides problem solving, another thing mathematicians enjoy doing a lot is generalizing. Suppose we have a set of characteristics and then we consider all objects that have those characteristics. If we did not impose one of the characteristics we could say we have a generalization of our objects.

As an example, suppose we are looking for all polygons that satisfy the following:

• Has four sides;
• All sides are equal;
• All adjacent sides make an angle of $90^\circ$.

It is easy to see that the square is the only polygon satisfying all $3$ criterion. We could care about the polygons that would satisfy a subset of those restrictions, thus getting a generalization of the square: if we do not impose the $90^\circ$ angles, then we would get squares and diamonds. In this case we can say diamonds are a generalization of the square, or the square is a specific diamond. If instead we lifted the restriction on the lengths of the sides, we would get rectangles: that is why we say the square is also a rectangle, because the square is a rectangle with a specific shape.

Having said that, we can easily generalize the sudoku puzzle: just allow the $3 \times 3$ boxes to have irregular shapes while having $9$ little squares. If we change those shapes, the rules now become: no repetitions per row, per column and per region. In the beginning we included an example of such a generalized grid, we include a different one here:

A friend of mine has been solving these puzzles and asked me to write a program to determine if a given puzzle has a unique solution or not. And so I did! The program is quite simple and uses just a bit of recursion on top of my representation of the non-square irregular regions.

Counting the solutions of these puzzles is straightforward; swiping the grid left to right, top to bottom: whenever I "look" at a given cell I just compute all possibilities, try one, and keep filling the grid. If I reach a point where a given cell has no legal plays, I must have made a mistake in some previous cell and I just undo my most recent guesses. Whenever I reach the bottom-right corner of the puzzle, it is because I was able to fill the grid completely. As an example I include the solution my program found for the last puzzle shown:

The code that computes the solutions can be found here.