Katamino

(This article is not MAME related)

Some time ago I was shopping looking for a set of Pentomino pieces and found this game called Katamino®.

It looked like a decent enough set of wooden pieces, so I bought it. Pentominoes are a decades old puzzle, so I didn't expect anything more than that. Instead, when I opened the box, I was blown away by how cleverly the puzzle is presented.
The idea is credited to André Perriolat, who is the owner of the company that produces the game, DJ Games.

Here is how it works: take four pentominoes, and make a 5x4 rectangle with them. After you've accomplished that, add another pentomino, and make a 5x5 square. Then add another, and make a 5x6 rectangle. And so on, until you add the final piece to make a 5x12 rectangle. The box contains a board with a moving slider to place your pieces in.

There is only one rule: when you add the I piece, you cannot place it vertically. Otherwise it would be cheating, since you could take the solution to the previous puzzle and just stick the I to the side.
For the same reason, the I piece is not used for the 5x5 puzzles, since even if you put it horizontally it would still be a 5x4 rectangle with the I stuck to the side.

In the box there's a list of 12 such sequences that you can follow, each one ending with a different piece.

This is absolutely brilliant. You start with easy puzzles wich practically anyone can solve, and then gradually increase the difficulty until you complete the full puzzle--or run out of patience, whichever comes first.

Every time you complete one of the puzzles there's a sense of achivement--and then immediately of frustration, because to add one more piece you have to throw away the perfect shape you just created, and start again from scratch.

I liked this idea so much that I started thinking about it. How many ways are there to build sequences to play the game? Are the ones provided the best possible, or can they be improved? Let's see what the goal is:

• build 12 sequences, each one ending with a different piece


• every combination of pieces must be used only once

Things get interesting from the start. There are only 19 ways to select 4 pieces that can form a 5x4 rectangle; but 6 of them cannot be extended to 5x5 without using the I piece. This leaves us with 13 initial choices, just one more than what we need.

How can we rate our sequences to decide which ones are better than others? The obvious answer is to look at the number of different solutions for each combination of pieces. The less the solutions, the better the puzzle is. If two sequences have the same number of solutions, then the one that contains more puzzles which have a single solution is better.
The 5x11 puzzles are obviously the same for every choice, so we don't have to count them. This leaves us with 12 sets of 7 puzzles (from 5x4 to 5x10) for a total of 84 puzzles, which we want to be as hard as possible.

Turns out that the sequences accompanying my copy of the game aren't very good: there's a total of 3084 solutions, and only 20 puzzles with a single solution. Even worse, one of the puzzles is repeated twice.
It seems that I have and old version of the game (the instructions say (c) 1992-1998). The version currently being produced uses a better list, whith 1556 solutions and 26 single solutions (and no duplicates).

Writing a program to find the best solution is a remarkably difficult task. I'm not even sure if it has been classified. If it is, I'd expect it to be as part of problems related to graph theory.

With a mix of manual pruning and computer search, I've selected this sequence which looks quite good:

L P U F [1] W [1] I [4] Z [1] T [5] N [1] V [83] Y [1277] X [786]
L Y U F [3] Z [1] I [2] N [2] T [4] X [2] V [16] P [ 508] W   "
Y N V T [1] F [1] I [3] W [1] U [5] X [1] L [ 8] P [ 371] Z   "
L Y P W [5] N [1] V [1] I [5] X [1] Z [5] F [25] U [ 216] T   "
Y P U F [1] T [1] I [2] Z [1] N [2] X [1] W [ 2] L [ 183] V   "
L Y P T [1] W [1] F [1] N [5] X [3] Z [1] I [ 8] V [ 133] U   "
L V P Z [2] Y [1] T [2] I [5] X [1] W [1] F [15] U [ 125] N   "
L Y P Z [1] W [2] T [1] V [1] X [1] U [3] N [21] I [ 116] F   "
L N P U [2] Z [2] X [1] V [1] F [1] T [2] W [14] Y [ 112] I   "
L N V Z [2] U [1] T [1] F [2] I [6] W [3] X [ 1] P [ 101] Y   "
Y N P U [1] V [1] Z [1] X [1] F [2] T [1] W [ 1] I [  59] L   "
L Y V U [2] Z [1] F [1] W [1] X [1] N [1] T [ 1] I [  14] P   "

The numbers in square brackets are the solutions for each puzzle.
The total is 331 solutions, and 45 puzzles with a single solution.

I think this should be quite close to the minimum, but I don't have a way to prove it.

Can anyone do better?