# Circles crossing every cell of an NxN grid

What is the least number of circles you need to draw, such that every cell of an NxN grid is crossed? A circle crosses a grid cell if one of the points on its circumference lies completely inside the cell (on the border doesn't count). Circles cannot lie outside the grid. What are the best answers for N = 1 to 20? Partial answers are welcome.

An earlier puzzle was about N = 8. This puzzle was suggested by Simd.

• I am pretty sure the best solution will be concentric circles. Commented Apr 2 at 16:06
• @FlorianF This is an extension of the bonus version. Concentric circles only work up to N=6. Commented Apr 2 at 16:11
• If you can enumerate the sets of cells that correspond to circles, the problem can be solved via set covering. See this related question for lines instead of circles: math.stackexchange.com/questions/4756401/… Commented Apr 3 at 20:49
• @RobPratt That would be great! I feel you are the expert for this.
– Simd
Commented Apr 3 at 20:54
• It is funny, because originally I considered of making the puzzle about line crossings, but dismissed it because I thought it would be too easy. I thought the answer would always be N. Commented Apr 4 at 1:00

I think I am still a fan of concentric circles. Modulo some adjustments for the corners.

Here is a 20-grid covered with 14 circles.

– Simd
Commented Apr 3 at 19:13
• Symmetry has a big advantage, you only need to check 1/8th of the figure. Commented Apr 3 at 19:15
• FWIW I calculated that the largest $N$ with a central circle that intersects the four corner cells but is still contained is $N=6$ (actually 6.828). Commented Apr 3 at 19:29
• Daniel Mathias also found 6 is the max. Commented Apr 3 at 19:31
• Very nice solution. What are you best results for other N using this method? I think we will need to make a table to record all the results. Commented Apr 4 at 1:01

My best effort: 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 11, 11, 13, 16, 17, 19, 20, 20, 22. The larger ones are definitely suboptimal.

• This is excellent work and I love all the graphics! Let's see if anyone can do better. Commented Apr 3 at 9:41
• Can 1 to 6 be done with only concentric circles? I am interested in how much symmetry it is possible to preserve.
– Simd
Commented Apr 3 at 19:11

UPDATE: I found some nice symmetric solutions:

N = 12

N = 14

N = 18

I found some new solutions

N = 12

N = 13

N = 14, love that circle that breaks symmetry

N = 15

N = 16

N = 17

N = 18

N = 19, my biggest breakthrough

• Knowing how much I had to fiddle for my 20-grid, respect for the tedious work this must have been. Commented Apr 5 at 10:46
• I wrote a program to find these, so it was doing most of the tedious work for me :) Commented Apr 5 at 12:30
• Oh, ok. Then I take back what I said :-P . But this explains why you didn't use more symmetry. Commented Apr 6 at 10:31
• I didn't want to restrict it so it could find the symmetry (or not) if needed. But I should try to use symmetry to simplify the search. Commented Apr 6 at 14:26
• The center of an odd-sized grid is a problem because symmetry means it is covered by 4 circles. (or one very small one). I wouldn't be surprised if solutions for odd-sized grids end up less symmetrical. Commented Apr 7 at 8:51

Making a community wiki so that all the answers are kept in one place. Anyone can edit it.

N Circles (Current Best Known Upper Bound) Credit
1 1 trivial
2 1 trivial
3 2 user1502040
4 2 user1502040
5 3 user1502040
6 3 user1502040
7 4 user1502040
8 5 Sunny Lu
9 6 user1502040
10 6 user1502040
11 7 user1502040
12 8 RobPratt
13 9 RobPratt
14 10 Dmitry Kamenetsky
15 11 Dmitry Kamenetsky
16 12 Dmitry Kamenetsky
17 13 Dmitry Kamenetsky
18 14 Dmitry Kamenetsky
19 14 Dmitry Kamenetsky
20 14 Florian F
• @RobPratt I hope you will show us your solutions. Commented Apr 4 at 16:55
• Guys please post your solutions first, before updating this table. Commented Apr 5 at 7:28

Here are two solutions that yielded the best-known values (not necessarily optimal).

$$N=12$$:

$$N=13$$:

• Have you got an integer programming formulation now?
– Simd
Commented Apr 9 at 20:59
• @Simd No, I just solved an ILP over a large set of randomly generated circles, not all possible circles. Commented Apr 9 at 21:20
• @RobPratt I have a stupid question. From this large set of random circles did you remove duplicates - circles that cross the same squares? Commented Apr 10 at 2:44
• @DmitryKamenetsky No, and I also didn’t explicitly remove dominated sets of cells. The ILP solver will do this automatically. Commented Apr 10 at 2:59
• Instead of a selection of completely random circles, how about restricting it to (a random selection of) circles with their centre on a line of symmetry of the square? (i.e. diagonals and vertical/horizontal lines through centre) The best solutions seem to use only such circles, so maybe that gives better or faster results. Commented Apr 10 at 7:52