How to infinitely tile a cartesian plane with the least "mine-coverage" for various "8-proximity" values?

Question

thanks for opening my question!

So I started playing Minesweeper again recently and started asking myself this question. Firstly, I refer to an infinite square grid with squares of arbitrary side length - $a$ - as the "cartesian" plane. These squares can be categorized into mines and non-mines, like in the game minesweeper. What I call "mine-coverage" - $c$ - refers to the ratio of mine squares and total squares. Lastly, "8-proximity" - $p$ - values correspond to the number of mine squares touching non-mine squares via an edge or a corner with a radius of 1. There are 8 neighboring squares to each square, hence "8-proximity". In my examples I want all non-mines to have the same $p$-value.

After a few days of thinking, these are the most "efficient" unit cells I came up with (+ meaning it's a mine square): The arrows for $p=2$ represent the borders of the unit cell, otherwise, the squares' collective outline does You can imagine the non-mine squares to include their $p$ value in the center just like in minesweeper.

Their corresponding $c$-values are: $1$ - $1/9$, $2$ - $1/5$, $3$ - $1/3$, $4$ - $2/5$, $5$ - $1/2$, $6$ - $1/2$, $7$ - $2/3$, $8$ - $3/4$.

Now, my question is, are these the unit cells minimizing $c$, or are there better alternatives? I came up with various different ways to tile the plane for $p$-values 2, 3, 4, 5, 6, 7 & 8, however, they have the same or even higher $c$-values, which is not in my interest.

Thank you so much for reading and have fun coming up with better tilings or possibly even proofing the most efficient tilings!

Kind Regards, Jason

Answer 1

Partial answer (for $p\in\{1, 2, 8\}$):

Draw an edge between every free square and adjacent mine square. Then you want every free square to be incident with $p$ edges. If mine fields are on average incident with $q$ edges, then we obtain the "handshaking" equation $$ p(1-c)=qc,$$ and from this $$ c=\frac{p}{p+q}.$$ Thus to minimize $c$ (for given $p$) is the same as to maximize $q$!

• $c=1$ and $c=2$: Your solutions have $q=8$, which cannot be beaten
• $c=8$: Your solution has $q=2\frac 23$. Clearly, no mine can have degree $>4$. Any mine of degree $4$ has four free diagonal neighbours and then its four direct neighbours must be mines of degree $2$. This leads to an average $q$ of exactly $2\frac23$. (To see this, imagine every degree-4-mine gave $\frac13$ of its degree to each neighbouring degree-2-mine, thereby reducing its own degree to $2\frac23$; at the same time each degree-2-mine has at most two(!) degree-4-neighbours and thus raises to at most $2\frac23$). So assume all mines have degree $\le 3$. Then necessarily the three free neighbours are two diagonal and one direct neighbour (why?), and the direct neighbour between the diagonal free neighbours turns out to be at most of degree $2$. With a similar argument as before, we find that $q\le 2\frac23$

The other cases may require a bit more work. E.g., your $p=2$ solution has $q=7$. Keep in mind that must show $q\le 7$, not merely $q<8$. This is certainly a feasible task, but I am feeling to lazy right now.