A liberty puzzle

[le_4TC]

This has nothing to do with regular go, probably not very interesting to most people

On this 5x5-board, there are 8 black chains, and 4 white chains, each with 2 liberties:

Can you find a way to fit more than 12 chains on 5x5 board such that all chains have 2 liberties?

How about for 1, 3, or 4 liberties? The best numbers I got after a few minutes of playing around (very likely not optimal yet):

1 liberty: 18 chains 17 chains
2 liberties: 12 chains
3 liberties: 12 chains
4 liberties: 6 chains 7 chains

I thought it might be a fun little puzzle to try to match/beat these numbers if you’re bored

[Vsotvep]

@yebellz will love this as well, I bet. I’ll look at it later

[shinuito]

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

[le_4TC]

Any contributions are welcome!

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

[shinuito]

I got these for 3 and 2 liberties.

I could only get 17 so far for 1 liberty

[le_4TC]

Very nice! For 3 liberties I had exactly the same

[le_4TC]

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.

[yebellz]

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 Go that could be useful here:
https://vsotvep.github.io/MulticolorGo.html?st=&bs=5

[le_4TC]

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.

[le_4TC]

My other attempts:

1 liberty: 18 chains (wrong, see below)

4 liberties: 7 chains

[yebellz]

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.

[shinuito]

@le_4TC

1 liberty: 18 chains

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

Here’s my 17

[le_4TC]

Whoops Thanks for catching my blunder!

[shinuito]

@yebellz

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

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)

[shinuito]

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.

[le_4TC]

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!

[le_4TC]

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.

[shinuito]

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.

[shinuito]

Just to give an idea on the method if you find it interesting. I really like using @Vsotvep’s board that @yebellz linked 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.

[yebellz]

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).