Time to have fun solving some puzzles!
This post was released for Issue 12 of Bitcoin Magazine as the first one of a series of articles about puzzles and games. I hope you enjoy reading them as much as I enjoy writing them. The ceiling of my daughter’s bedroom is full of small star-shaped phosphorescent stickers. One night in 2009 she was a bit sick, so I sat next to her and held her hand until she finally fell asleep. Then I raised my head and I looked at that ceiling full of stickers for a while. A new logic puzzle was taking shape.
This puzzle evolved into my second published game (Hexellation, 2009). Hexellation uses a hexhex board (a hexagon made of hexagons), but for practical purposes we’ll use square grids here, so you can easily play with paper and pencil. In Hexellation, two players try to create a constellation of stars called ‘model’ without creating a forbidden constellation called ‘avoid’.
In this issue’s puzzle, we’ll focus on the ‘forbidden something’ mechanism only. I’ve always been fascinated by games with constraint mechanisms, where you try to achieve your goals while dealing with prohibitions. Does it sound familiar to you? Life itself.
Don’t miss the next issues of Bitcoin Magazine, as I will talk about how an automated game-generating programme also used this type of mechanism in 2007, when it created the first game ever invented by a computer.
THE PUZZLE
We’ll start by drawing two square grids of the same size next to each other (10 squares per side, for example, although you can use any size). The left one will be called ‘avoid’ and the right one will be the ‘sky map’. Now we’ll place a few stars (3, for example) on the ‘avoid’ grid, randomly. This arrangement of stars is the forbidden constellation.
Figure 1: a forbidden constellation
The goal of the puzzle is to place as many stars as possible on the sky map in such way that the forbidden constellation is not present on it, even by rotation. A constellation symmetrical to the forbidden one is allowed, as long as it is not also identical by rotation.
For example, the red constellations in figure 2 are illegal, as they are the same as the forbidden one (some of them are rotated). On the other hand, the green constellation is legal, as it is not the same as the forbidden one, no matter how you rotate it.
Figure 2: examples of legal and illegal arrangements of stars
A sky map that does not contain the forbidden constellation will be called a ‘proper sky map’. The sky map in figure 2 contains the forbidden constellation three times (indicated in red), so it is not a proper sky map. Remember that the configuration indicated in green is correct.
The proper sky map that contains the maximum number of stars possible for a given forbidden constellation will be its ‘solution’ (there can be several different solutions for a given forbidden constellation). The number of stars of a solution varies depending on the configuration and number of stars of the forbidden constellation.
Figures 3 and 4 show examples of solutions for trivial cases of forbidden constellations. The solution for the forbidden constellation in figure 3 has the maximum number of stars possible (99 stars).
Figure 3: a trivial constellation and its solution
By simply re-arranging the four stars into a 2x2 square (figure 4) we significantly reduce the number of stars of its solution to 75. Notice that none of the 25 remaining free spaces can be filled with a star, as it will complete a forbidden constellation and the sky map will not be a solution.
Figure 4: a 2x2 constellation and its solution
STRATEGY TIP
Don’t read this tip if you wish to discover the strategies by yourself!
An initial procedure to properly fill the sky map might be the following:
a) Start with an empty sky map.
b) Create a constellation on the sky map identical to the forbidden constellation.
c) Remove one of the stars from this newly created constellation. Let’s call it ‘stamp constellation’.
d) Replicate the stamp constellation as many times as possible on the sky map while avoiding creating the forbidden constellation.
e) Legally fill as many remaining spaces as possible.
Figure 5: a procedure to fill the sky map (steps ‘a’ to ‘d’)
And now, are you ready for the challenges?
THE CHALLENGES
Time to solve some puzzles! The following challenges are sorted by difficulty level, ranging from ‘immediate’ to ‘almost impossible’.
Challenge 1: Can you find the smallest forbidden constellation for this proper sky map (fig. 6)? This one is easier than it seems and there are many possible answers.
Figure 6: the Bitcoin sky map
Challenge 2: Can you find a solution for this forbidden constellation (fig. 7)?
Figure 7: the Bitcoinstellation
Challenge 3: Can you find a solution for this forbidden constellation (fig. 8)?
Figure 8: the brainburner
Challenge 4: Can you find a 4-star forbidden constellation so that its solution contains the lowest number of stars possible?
Challenge 5: Can you generalize this result for any grid and constellation size?
Challenge 6: Can you solve challenges 4 and 5 for a hexhex grid?
Please post your answers in my forum and I will reward the best post with a copy of one of my games! I’m looking forward to discussing your findings. Thank you for reading!
Update: Let's define 'smallest constellation' as the constellation with the minimum number of stars.