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.

Improve this question
$\endgroup$
9
  • $\begingroup$ I am pretty sure the best solution will be concentric circles. $\endgroup$
    – Florian F
    Commented 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$
    – Daniel Mathias
    Commented 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
    Commented Apr 3 at 20:49
  • 1
    $\begingroup$ @RobPratt That would be great! I feel you are the expert for this. $\endgroup$
    – Simd
    Commented 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$
    – Dmitry Kamenetsky
    Commented Apr 4 at 1:00

5 Answers 5

Reset to default
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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Answered at exactly the same time I asked about symmetry on the other answer :) $\endgroup$
    – Simd
    Commented 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
    Commented 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$
    – Weather Vane
    Commented Apr 3 at 19:29
  • $\begingroup$ Daniel Mathias also found 6 is the max. $\endgroup$
    – Florian F
    Commented 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$
    – Dmitry Kamenetsky
    Commented 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is excellent work and I love all the graphics! Let's see if anyone can do better. $\endgroup$
    – Dmitry Kamenetsky
    Commented 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
    Commented 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

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Have you got an integer programming formulation now? $\endgroup$
    – Simd
    Commented 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
    Commented 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$
    – Dmitry Kamenetsky
    Commented 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
    Commented 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$
    – Jaap Scherphuis
    Commented Apr 10 at 7:52

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