6
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ I am pretty sure the best solution will be concentric circles. $\endgroup$
    – Florian F
    Apr 2 at 16:06
  • 2
    $\begingroup$ @FlorianF This is an extension of the bonus version. Concentric circles only work up to N=6. $\endgroup$ Apr 2 at 16:11
  • 1
    $\begingroup$ 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/… $\endgroup$
    – RobPratt
    Apr 3 at 20:49
  • 1
    $\begingroup$ @RobPratt That would be great! I feel you are the expert for this. $\endgroup$
    – Simd
    Apr 3 at 20:54
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 4 at 1:00

5 Answers 5

6
$\begingroup$

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.

enter image description here

$\endgroup$
6
  • $\begingroup$ Answered at exactly the same time I asked about symmetry on the other answer :) $\endgroup$
    – Simd
    Apr 3 at 19:13
  • 1
    $\begingroup$ Symmetry has a big advantage, you only need to check 1/8th of the figure. $\endgroup$
    – Florian F
    Apr 3 at 19:15
  • $\begingroup$ 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). $\endgroup$ Apr 3 at 19:29
  • $\begingroup$ Daniel Mathias also found 6 is the max. $\endgroup$
    – Florian F
    Apr 3 at 19:31
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 4 at 1:01
5
$\begingroup$

enter image description here 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.

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

UPDATE: I found some nice symmetric solutions:

N = 12

enter image description here

N = 14

enter image description here

N = 18

enter image description here

I found some new solutions

N = 12

enter image description here

N = 13

enter image description here

N = 14, love that circle that breaks symmetry

enter image description here

N = 15

enter image description here

N = 16

enter image description here

N = 17

enter image description here

N = 18

enter image description here

N = 19, my biggest breakthrough

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Knowing how much I had to fiddle for my 20-grid, respect for the tedious work this must have been. $\endgroup$
    – Florian F
    Apr 5 at 10:46
  • 1
    $\begingroup$ I wrote a program to find these, so it was doing most of the tedious work for me :) $\endgroup$ Apr 5 at 12:30
  • $\begingroup$ Oh, ok. Then I take back what I said :-P . But this explains why you didn't use more symmetry. $\endgroup$
    – Florian F
    Apr 6 at 10:31
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6 at 14:26
  • 2
    $\begingroup$ 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. $\endgroup$
    – Florian F
    Apr 7 at 8:51
4
$\begingroup$

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
$\endgroup$
2
  • 1
    $\begingroup$ @RobPratt I hope you will show us your solutions. $\endgroup$ Apr 4 at 16:55
  • 1
    $\begingroup$ Guys please post your solutions first, before updating this table. $\endgroup$ Apr 5 at 7:28
3
$\begingroup$

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

$N=12$:

enter image description here

$N=13$:

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Have you got an integer programming formulation now? $\endgroup$
    – Simd
    Apr 9 at 20:59
  • 2
    $\begingroup$ @Simd No, I just solved an ILP over a large set of randomly generated circles, not all possible circles. $\endgroup$
    – RobPratt
    Apr 9 at 21:20
  • $\begingroup$ @RobPratt I have a stupid question. From this large set of random circles did you remove duplicates - circles that cross the same squares? $\endgroup$ Apr 10 at 2:44
  • 1
    $\begingroup$ @DmitryKamenetsky No, and I also didn’t explicitly remove dominated sets of cells. The ILP solver will do this automatically. $\endgroup$
    – RobPratt
    Apr 10 at 2:59
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 10 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.