6 minutes
Katamino
Katamino is a puzzle game where the goal is to fit a set of pieces on a board.
I played a lot with this game as a kid, but I figured it would also be a good puzzle to write a program that can solve it. This is a typical problem of recursive algorithm where one can write a function that takes the current board
as input as well as the remaining pieces
to place on the board. This function places one piece
on the board and then calls itself again with the new board
and the pieces
minus the one that was just placed on the board.
It gives us the following solver function, which is fairly simple:
I decided to represent each piece as a list of 0 and 1. For example the orange piece is:
And I built a Piece
class to be able to flip and rotate each piece in order to give all the possible orientations of a piece via the orientations
method. Note here that duplicates orientations are removed by overriding the built-in method __eq__
. As a result, the piece [[1,1,1,1,1]]
will have 2 orientations (one horizontal and one vertical) while more complex shapes like the orange piece above have 8.
Finally, we need to implement a Board
class to keep track of where we placed the pieces during the search. This is where we implement the possibilities
method which is a key part of our main function and enumerates the possible boards that can be made with the oriented piece.
First, we get the list of valid_locations
where this piece can be placed on the board within its limits (regardless of what is on the board at this point), then loops through each location and place the piece on the board with place_piece
and check whether the piece is sitting on another piece.
The last (and defintely not least) thing we need to check is whether the board we have is even a valid one and worth pursuing further. Let's take an example. Imagine you placed the orange piece on the board and it looks like this:
Well this board is not worth continuing because no piece can ever fit in the hole left in the upper left corner. Because there is only 3 empty squares left and katamino pieces are all of size 5. So in order to do that, we run a Breadth-First-Search on the 0 on the board and check that the remaining holes are all multiples of 5 so that there is the possibility for a piece to fit.
Now solving the puzzles takes between 1sec and ~5min on my 2017 Mac (1.8GHz Intel Core) depending on the number of pieces in the puzzle. The results look like below:
And the output is:
1131 Words
2024-11-01 14:57