I have a game called Katamino, and upon frustration from taking too long to solve it, I did what every normal person would do in such a situation: created a program to solve it.
So what is Katamino? As you might find in the link, it's a game comprised of 12 pieces, each with an size of 5 squares, and a 12*5 game board. The challenge is to fit all the pieces together on the board at the same time.
Each piece has a specific shape (as you can see above), but for the sake of the challenge we will assume that we don't know the shapes ahead of time. That is both more generic and will make for a neater code. So, how do we start?
Below I wrote my take on this problem. Nonetheless, you are very much invited to try to solve it yourself, and tell me about it in the comments. So, for those who would like to try on their on, do not look down. For the rest of you, even if you only need a hint, keep reading.
*SPOILER ALERT*
Clarification: For my solution I used C# Windows Forms. If you managed to solve it with a different environment, share below.
My first thought was to just brute-force my way. Try all the possible combinations until I find a solution. However, that would take a long time, and we still haven't gotten past the first hurdle: How should we represent the shapes?
First of all, I used checkBoxes to get the user's input of each shape. I used 15 checkboxes which I found was enough for all possible shapes. (I could have managed with less but it looked nicer as a 5*3 rectangle than as some other weird shape).
Since each shape's size is 5, my thought was to represent each shape as a (boolean) 5*3 two-dimensional array, and mark each place with whether it is occupied or not. It looks something like this:
bool[,] arrayShape = new bool[5,3];
for(int i=0; i<5; i++) {
for (int j=0;j<3;j++) {
//checkbox[,] is the array which represents the checkboxes
if(checkbox[i,j].isChecked) arrayShape[i,j] = true;
}
}
However, we can’t stay with that. In real life, a shape can be turned around. For example, a T shape can be turned into an upside down T in order to fit in. In addition, a shape can be flipped in order to fit in. Thus, I decided to represent each shape in 8 different ways: regular, 90 degree turn, 180 degree turn, 270 degree turn, and same with the flipped shape. Thus, each shape is actually represented by an array of 8 shapes.
Since a two-dimensional array is non-efficient when you consider we are only using ⅓ of it, it would take up precious time when we start our program. Since we are basing it on brute-forcing, we need to be as efficient as we can if we want it to solve the game in a reasonable time.
The solution I came up with was representing each shape as a list of points, in the following manner:
List<Point> pointsShape = new List<Point>();
// go over all the possible points, and only add the ones which belong to the shape
for(int i=0;i<5;i++) {
for (int j=0;j<3;j++) {
if(arrayShape[i,j]) pointsShape.Add(new Point(i,j));
}
}
Thus, what we have in the end is an array of lists of points. Yeah, complicated, but the code is still going to be readable since the actual array is not often mentioned there.
After we found a way to get the shapes from the user, and now we have 12 shapes represented in the aforementioned manner, we will start working on the actual algorithm. As I’ve said, it works in a brute-forcing logic, but with a few tweaks our program will solve the game in a mere minute.
The basic logic is like this: Have an array of integers that will represent the game board. Go over all the points on the gameboard, and when we find a place to put our shape, change all the points where our shape should go to our shape’s ID (between 0 and 11 according to its place in the list of shapes). It will look something like this:
for(int i=0;i<5;i++) {
for(int j=0;j<12;j++) {
//function that checks if shape fits in that spot
//gameboard represents the current gameboard, with the shapes that are already on it
if(shapeFits(i,j,gameboard,shape) addShape(i,j,gameboard,shape);
}
}
What shapeFits basically does is like this: It takes our shape, which is a list of points, and it takes the point (i,j). It changes our points’ values so that the first point in the list goes on (i,j), and the rest are changed accordingly. (reminder: a point’s value is 0 if it’s free, and other if there’s another piece on it). The changing of the points looks something like this:
int changeX = points[0].X - i, changeY = points[0].Y - y;
for(int i=0;i<points.Count;i++) {
points[i].X = points[i].X -changeX;
points[i].Y = points[i].Y -changeY;
}
After we changed the points to the ones we want, we perform the check. For each point, we will check if it’s in the limits of the array, and then if it is occupied. If any of these clauses are false for any of the points, the function returns false. Else, it returns true. If it returns true, we simply update the game board with the new piece, and change all its points to the ID.
For each shape, we perform this check in all possible positions of the shape, and only advance to the next point if all 8 positions return false (we will discuss later ways to make this more efficient).
We perform this function recursively, so that if a shape doesn’t fit anywhere, we go back to the previous shape, and continue as if it had gotten false in that attempt. So, if shape 1 fit in point (1,2) with position number 5, and then shape 2 didn’t fit anywhere, we go back and try shape 1 in point (1,2) with position number 6, etc.
Just to clarify, the aforementioned program will work and it will eventually get to an answer. However, since we do not have all the time in the world, we want to make it more efficient in order for the program to solve it faster. For this there are several steps:
- Check if each shape is flippable, meaning we can get to the same position if we flip it. That would include a T, which is the same when flipped. Furthermore, it would include L, which is the same as when flipped and turned 90 degrees.
- Check if a shape is turnable, which is the same as flippable, only it’s with turning. For example, an I is the same when turned 180 degrees, and a + is the same when turned 90 degrees.
These will have the following effects:
Flippable- Do not check for the flip. That cuts the amount of check by a half (!).
Turnable by 90 degrees- If something is turnable by 90, it is turnable by all degrees (you are invited to check). Thus, do not check for any positions except for regular and flipped (unless it is flippable).
Turnable by 180 degrees- Only check for the first and second position, same for the flip side (In total, only check 1,2,5,6).
Combined, all of these cut our times by over a half. However, this is not enough, and we need to cut it down by a whole lot more.
Check all free spaces- For each group of free spaces which are surrounded by taken spaces, check their size. For example, in the following array:
1 0 2 2 0 0 3
1 0 0 2 0 3 3
1 0 0 2 0 3 3
1 0 4 2 0 0 0
1 4 4 4 4 0 0
We have two groups of free spaces: One with a size of 6, and one with a size of 9. However, logic tells us that if a group’s size is not divisible by 5, we cannot fill it up with shapes. Thus, in this case, we are doomed for failure and we need to retrace our steps and go back to the previous shape.
The actual algorithm for finding free spaces is not complicated and does not load on our program, and you can try writing your own. What is important is that this really cuts our time, and when I added this clause my program solved the board much more quickly.
And now, for the final step, we add a function that checks if all pieces can fit into the board. For example, if we look at the board above, considering our remaining shapes are:
5 5 5 6 6 6 6
5 5 6
We can clearly see that while 6 fits in the board (flipped and turned 90 degrees), 5 cannot fit. Thus, there is no point continuing in this direction as we will never reach a solution. In this case, we can go back to the previous shape and continue trying.
Finally, when we manage to fit all our pieces, we can print out the board to the screen.
That’s it! With a program based on the above, I was able to find a solution to the program in under a minute (actual times might vary based on your processor, however I would estimate that it would still get it done in under 5 minutes).
What do you think? Do you have a different solution? Let me know in the comments below, and also if you have ideas for future challenges!
No comments:
Post a Comment