Same color go pieces that can be placed on the Gomoku chessboard

Question

Question

The rule of Gomoku(Five in a Row) is that on an $n × n$ square chessboard, when there are five or more go pieces of the same color in any direction horizontally, vertically and diagonally, you win.

I want to know the maximum number of go pieces $P_5(n)$ that can be placed on the $n×n$ gomoku chessboard without five chess pieces being connected in a line.

---

Strategy

I thought of two strategies.

The first one is to form a group of four. This strategy has about 64% space utilization.

---

The second strategy is obtained using the greedy backtracking algorithm. Each vacant position is placed in the first allowed position. This strategy has about 80% space utilization.

It seems to be the optimal solution on the scale of $15 * 15$, but I cannot prove by induction that this property can be maintained on a larger chessboard.

Answer 1

Notice that each row must contain $3$ blank squares or lower. Otherwise, by the pigeonhole principle, 2 blank squares will always reveal a consecutive string of chess pieces with length $5$ or longer. Thus, the lower bound for the number of blanks squares is $45$ squares.

All that remains is to find an example such that this lower bound holds, which you have found by your last example.

We can just apply this pigeonhole principle theory across different lengths of squares.

In the end, the minimum amount of blank squares should be $n\lfloor \frac{n}{5} \rfloor$, where $n$ is the sidelength of the grid.

For any game that doesn't allow $m$ chess pieces in a row, we have the minimum amount of blanks squares to be $n\lfloor \frac{n}{m} \rfloor$.