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

I have a matrix of r rows and c columns.

I want to choose n random cells from the matrix but with a minimum distance from each other, called d.

For better visualization, let r = c = 15, n = 4 and d = 2. The red cells are the chosen ones. The black cells are the space in which cells cannot be selected as they are inside the distance d of an already chosen cell.

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

My question is: what's the fastest way to choose n cells satisfying these conditions?

---

Of course there are plenty of slow ways to do that. 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 n times. 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).