java - Placing random circles without overlap (and without using brute force)?

Question

I've just submitted a Java assignment in which I needed to draw some circles randomly on the screen as part of a game. One of the challenges given to us was to make sure none of the circles overlapped. I ended up going with a strange approach (because I wanted to :D) that basically just created a pattern from the center of the screen using trig, which was fun. Although the circles in this method never overlap, it's not ideal... the distribution of circles is fairly packed around the middle of the screen with very little space being used in the corners.

I also created a (commented out) brute force approach that simply rerolled new coordinates if a proposed circle's x,y coordinates intersected an already-created circle, which while theoretically capable of looping to infinite, most likely wouldn't exceed ten intersections.

After discussing solutions with a friend (and after a TON of googling), we're actually very interested to see how this could have been done without brute force. The requirements:

• 20 circles with ten units radius to be drawn on a 640x480 window
• absolutely no overlapping of circles
• otherwise random distribution across the screen

Possible, using the standard library?

Answer 1

1. Make a list of 640x480 entries and put consecutive numbers from 1 to 307.200 (640x480) in them. Each entry represents one pixel on the screen.
2. Randomly pick a number from 1 to 307.200, which represents a pixel on screen. Draw circle there.
3. Calculate all pixels that fall within 10 pixer radius of this circle. Remove all entries representing those pixels from list.

Repeat ten times.