A liberty puzzle

Do you want pictures as responses if they match but don’t beat your numbers?

2 Likes

Any contributions are welcome!

It will be quite interesting to see if we have similar solutions.

3 Likes

I got these for 3 and 2 liberties.

I could only get 17 so far for 1 liberty

5 Likes

Very nice! For 3 liberties I had exactly the same :smiley:

2 Likes

I managed to improve to 7 chains for 4 liberties! I’ll hold off a little bit on posting it to let more people think about it for themselves.

2 Likes

There is a ton of mathematical literature about “tiling / tessellation”, but perhaps this particular type of problem has not yet been explored in the literature.

I think the chains and their intended liberties can be viewed as tiles, but the liberties are allowed to overlap when tessellating. These problems could be stated as: how to tessellate the 5x5 grid with a set of tiles (where each tile is a possible chain plus its intended liberties), but the tiles are allowed to partially overlap (on the liberties)? Specifically, the original post asks for tessellations that use the maximum number of tiles.

However, there is a complicating wrinkle to this problem: the points adjacent to the chains that should not be liberties must be filled with stones of a different color or the edge of the board. With only two colors to work with, this adds a complication that potentially reduces the possible solutions.

Thus, I conjecture that allowing more than two colors of stones would increase the solution space. I wonder if “four colors suffice” for achieving the maximum, or if a different number is the most one would need to maximize their score.

What are your best solutions with more than two colors of stones?

Now, I think the problem has at least three parameters to consider: size of the board, number of stone colors, and number of liberties per chain. Of course, other generalizations, like rectangular boards, wider bounds on the liberty count (instead of a single fixed number), etc., are also possible.

@Vsotvep built a tool for playing Diplomatic :dagger: Go that could be useful here:
https://vsotvep.github.io/MulticolorGo.html?st=&bs=5

4 Likes

Interestingly, so far I haven’t seen any situations where more than two colors help. My best configuration for 4 liberties actually only uses one color, but 2 colors are obviously helpful for the other cases. So the number of colors that is sufficient in general is either 2, 3 or 4, but for small boards at least I suspect you might never need more than 2.

3 Likes

My other attempts:

1 liberty: 18 chains (wrong, see below)

4 liberties: 7 chains

3 Likes

Here is a diagram to help explain what I mean about the tiling perspective:

The above is just an illustrative subset of the tiles allowed, when considering the two liberty problem. For the actual problem, the tile set would have to be expanded to include chains with three or more stones as well, but I just omitted those for this illustration. When placing them, rotations, mirroring, and changing the color are allowed, and the tiles may overlap where they indicate liberties. However, on the edges that are highlighted with red, they must be adjacent to the edge of the board or stones of a different color.

4 Likes

In your one liberty one, black stones in the top corners have no liberties.

Here’s my 17

4 Likes

Whoops :face_with_hand_over_mouth: Thanks for catching my blunder!

5 Likes

I think this is 17 chains with one liberty with 3 colours (but where in the arrangement I think it’s necessary to use 3 colours)

3 Likes

It’s tricky to get to 18 groups. I think with the one liberties ones the empty space for liberties are fairly constrained. They can’t be a one point jump or kosumi from each other. Need to be at least a knights move, two point jump etc, spacings.

4 Likes

Or right next to each other, like in your other solution!

I was also thinking about it in this way yesterday, trying to place the liberties rather than the stones so to speak. But no matter what I did, 18 chains always seemed just out of reach (haven’t tried to prove it impossible yet though).

It would be very interesting to find a board size where having more than 2 colors provably gives a larger maximum!

3 Likes

It can clearly happen for arbitrary graphs, the simplest example being the complete graph on 4 vertices (with 2 colors you can only make 2 chains with 1 liberty, with 3 you can fit 3), so it’s just a question of whether this is ever realized on a “regular” square board.

2 Likes

I think this is a weirder 3 colour one with less symmetry. I wanted to try and arrange 6 or fewer empty spaces but have at least one two space gap.

Edited to remove one red colour chain.

Old one

I kind of like the tigers mouths being the same colour though.

4 Likes

Just to give an idea on the method if you find it interesting. I really like using @Vsotvep’s board that @yebellz linked :slight_smile: Possibly interested in it @le_4TC?

How I made the last one

I start off trying to place empty space (orange colour) so that stones (white colour) don’t have more than one liberty. Basically if they’re one point empty spaces they need to spread out as mentioned before. Two, three point empty spaces can exist but other spaces need to spread out from them also. You can see all the knights move relations between empty points.

Then I changed the colours of stones (white) to yellow if they neighboured an empty space (orange).

There’s still two points that aren’t touching an empty space so they’ll need to both be two point groups of stones (that’s 2 two points groups, 6 empty spaces, 15 one point groups 15+4+6=25).

Then I alternate black and white colours to see if I can do it with the least number of colours (I’ve highlighted the two point groups green\blue and connected them to an empty space

There’s some more forced colours and the middle group has to be an extra colour because it touches both black and white and we don’t want to reduce the number of groups on the board

I picked the red stone direction to be different to the last post just for fun.

4 Likes

It seems that all of the 17-chain solutions for 1-liberty per chain on 5x5 require 6 liberties and two chains with two stones (and the other 15 chains being single stones). To get to 18 chains, we would either need to find a solution that uses only 5 liberties, while allowing us to add another single-stone chain, or find a way to replace a two-stone chain with two one-stone chains.

A single liberty can at most support 4 chains, but less if it is in a corner or on a side. Is there even a potential placement of five liberties that still supports the possibility of 18 chains? That might allow us to quickly rule out 5 liberty solutions. A better solution with only 4 liberties is clearly impossible, since that could only support a maximum of 16 chains.

8 or more liberties would not work since then there is only space for 17 or less stones. A 7 liberty solution would require 18 single-stone chains, which might give us an angle to rule out that possibility.

With our attention focused on 6 liberties, we would have to show that we need at least two chains of two stones each in order to always reach those 6 liberties, in order to prove that 17 is indeed a maximum solution (assuming that we also prove the other conjectures above).

3 Likes

Here’s one way to search for a solution. Place 6 (or 5 or 7) stones on the 5x5 board, while avoiding any one-space jump or kosumi (diagonally adjacent) relationship. Then count the liberties of those stones, which represents the total number of chains that could attach to those stones, which actually represent the eventual liberties for your actual solution. This quickly rules out a liberty placement without having to check how to place chains.

If you allow more than two colors of stones, it’s very easy to color stones around a liberty arrangement to maximize the number of chains supported by those liberties.

1 Like

Here’s a super messy (basically stream-of-consciousness) argument that 19 chains, at least, is impossible on 5x5:

Each empty point can only be a liberty to at most 4 different chains, and each chain consists of at least 1 stone.

So for instance to get to 20 chains, we would need 5 isolated empty points, each connected to 4 chains, which is impossible. (we would have to place all the five empty points in the central 3x3 square, but then some chains willl get 2 liberties)

So let’s look at 19 chains and 6 empty. Number of connected chains for each empty point would need to distribute in one of these ways:

4 4 4 4 3 0
4 4 4 4 2 1
4 4 4 3 3 1
4 4 4 3 2 2
4 4 3 3 3 2
4 3 3 3 3 3

But actually, having three 4’s is impossible: once again they will all have to be in the central 3x3, but they then will end up too close to each other. So we are limited to the last 2 options above.

If we are to achieve 19 chains, each point that is not one of the 7 empty has to be a 1-stone chain. This makes what can happen in the corners quite limited. If a corner is not empty, there has to be an empty point next to it, which has at most 3 chains. If a corner is empty, it is connected to at most 2 chains. Thus in the scenario “4 4 3 3 3 2” from above, we can tell exactly where each empty point must be placed:

Two 4’s in the central 3x3
Three 3’s adjacent to three of the corners
And a 2 in the last corner.

Here none of the empty points are allowed to touch, and kosumi’s and jumps are forbidden as usual. Now it’s easy to see that this arrangement is impossible, since a stone at either of the circles makes all of the crosses forbidden:


(so after the three 3’s are placed next to the corners, there is not any space left for the two 4’s in the center)

Ok, one possible configuration left: “4 3 3 3 3 3”. None of the empty points are in the corners, so there must be four of them adjacent to corners, but then (looking at the above image again), the center is completely forbidden, so the last “4” is impossible to place.

If I didn’t make a mistake (very well might have with how messy this got), this proves that 19 chains on 5x5 is impossible (also I don’t think this assumed 2 colors?).

In many parts of this argument the given task seems not even close to working, so maybe with some tidying up a similar argument could prove 18 impossible?

2 Likes