Choosing random elements of a 2D array with a minimum distance between them

I have a matrix of r rows and c columns.

I will throw a sequence of bombs at this matrix, each bomb falls in a random cell and destroy a square of "radius" d. A bomb cannot fall in an already destroyed place.

For better visualization, let r = c = 15 and d = 2. The red cells are the cells where bombs fall. The red and the black cells are destroyed and new bombs cannot fall there.

⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️
⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️⬛️⬛️⬛️
⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️⬛️🟥⬛️
⬜⬜⬜⬜⬜⬜⬜⬛️⬛️🟥⬛️⬛️⬛️⬛️⬛️
⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️⬛️⬛️⬛️
⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️
⬜⬛️⬛️⬛️⬛️⬛️⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️
⬜⬛️⬛️⬛️⬛️⬛️⬜⬜⬜⬜⬛️⬛️🟥⬛️⬛️
⬜⬛️⬛️🟥⬛️⬛️⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️
⬜⬛️⬛️⬛️⬛️⬛️⬜⬜⬜⬜⬛️⬛️⬛️⬛️⬛️
⬜⬛️⬛️⬛️⬛️⬛️⬜⬜⬜⬜⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜

My question is: what's the fastest way to choose a sequence of random positions for bombs satisfying this condition?

---

One of my thoughts was to throw every cell in a hashset, getting a random element inside it, removing all the cells in a distance d of the chosen cell in the hashset and repeat this as much as I need. I don't know how badly this affects the uniformity of the choice and don't know the complexity of getting a random element in a hashset (although I suppose is linear).