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.
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.
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.
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.
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!
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.
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.
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
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).
Go
Thanks for catching my blunder!
