# the garden problem

## stevan apter — 2005-03-26 15:40:31

    in case some of you missed it, this one's fun:

    http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8

    from the author's description:

    ----------------------------------

    The garden layout problem is as follows:

    Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells

    on the grid so that you can reach each Planted cell while standing in an Empty cell.

    In other words, for each Planted cell, one of its four neighbors (no diagonals) must

    be Empty. Thus, you can tend your garden without ever standing in the planted areas

    (which would compact the soil and potentially damage the plants that are growing

    there).

    Of course, you want to maximize the amount of space used for plants in the garden,

    so you want to solve the above problem with the minimum number of Empty cells.

## John Carter — 2005-03-30 21:55:05

    On Sat, 26 Mar 2005, stevan apter wrote:

     >

    > in case some of you missed it, this one's fun:

    >

    > http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8

    >

    > from the author's description:

    >

    > ----------------------------------

    >

    > The garden layout problem is as follows:

    >

    > Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells

    > on the grid so that you can reach each Planted cell while standing in an Empty cell.

    > In other words, for each Planted cell, one of its four neighbors (no diagonals) must

    > be Empty. Thus, you can tend your garden without ever standing in the planted areas

    > (which would compact the soil and potentially damage the plants that are growing

    > there).

    >

    > Of course, you want to maximize the amount of space used for plants in the garden,

    > so you want to solve the above problem with the minimum number of Empty cells.

     I'll nibble (just a little) on this one.

    It looks to be one of those things you can apply symmetry groups and group

    theoretic tricks to massively decrease the space of possibilities.

    For example given any mxn board, you can apply a set of symmetry

    transforms (flip horizontally, flip vertically, swap planted and bare)

    On an mxm board you can also add rotations.

    ie. With the correct representation, you can massively decrease the size

    of the problem.

    ie. Half the secret to an efficient solution of this problem lies in being

    able to iterate over non-duplicate layouts efficiently.

    (Looking at the optimum boards, the "bare" patches are pretty sparse.

    ie. I suspect one can probably at least calculate a crude lower and upper

    bound on the optimum number of "bare" patches and only iterate across that

    subset as well.)

    ie. Most of the challenge in solving this problem lies in the analysis

    before you even fire up your editor to start coding in _any_ langauge.

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Refactorers do it a little better every time.

## stevan apter — 2005-03-31 00:14:16

    ----- Original Message -----

    From: "John Carter" <john.carter@...>

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, March 30, 2005 4:55 PM

    Subject: Re: [stack] the garden problem

    >

    > On Sat, 26 Mar 2005, stevan apter wrote:

    >

    > >

    > > in case some of you missed it, this one's fun:

    > >

    > > http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8

    > >

    > > from the author's description:

    > >

    > > ----------------------------------

    > >

    > > The garden layout problem is as follows:

    > >

    > > Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells

    > > on the grid so that you can reach each Planted cell while standing in an Empty cell.

    > > In other words, for each Planted cell, one of its four neighbors (no diagonals) must

    > > be Empty. Thus, you can tend your garden without ever standing in the planted areas

    > > (which would compact the soil and potentially damage the plants that are growing

    > > there).

    > >

    > > Of course, you want to maximize the amount of space used for plants in the garden,

    > > so you want to solve the above problem with the minimum number of Empty cells.

    >

    > I'll nibble (just a little) on this one.

    >

    > It looks to be one of those things you can apply symmetry groups and group

    > theoretic tricks to massively decrease the space of possibilities.

    >

    > For example given any mxn board, you can apply a set of symmetry

    > transforms (flip horizontally, flip vertically, swap planted and bare)

    >

    > On an mxm board you can also add rotations.

    >

    > ie. With the correct representation, you can massively decrease the size

    > of the problem.

    >

    > ie. Half the secret to an efficient solution of this problem lies in being

    > able to iterate over non-duplicate layouts efficiently.

    >

    > (Looking at the optimum boards, the "bare" patches are pretty sparse.

    > ie. I suspect one can probably at least calculate a crude lower and upper

    > bound on the optimum number of "bare" patches and only iterate across that

    > subset as well.)

    >

    > ie. Most of the challenge in solving this problem lies in the analysis

    > before you even fire up your editor to start coding in _any_ langauge.

    just so.

    the current state of my k implementation is here:

        http://www.nsl.com/k/garden.k

    i make two assumptions:

        1. a minimal solution for m rows, n cols can always be constructed

           from the set of symmetrical rows of length n.  for example, the

           set for n = 7 is:

         0 0 0 0 0 0 0

         1 0 0 0 0 0 1

         0 1 0 0 0 1 0

         1 1 0 0 0 1 1

         0 0 1 0 1 0 0

         1 0 1 0 1 0 1

         0 1 1 0 1 1 0

         1 1 1 0 1 1 1

         0 0 0 1 0 0 0

         1 0 0 1 0 0 1

         0 1 0 1 0 1 0

         1 1 0 1 0 1 1

         0 0 1 1 1 0 0

         1 0 1 1 1 0 1

         0 1 1 1 1 1 0

         1 1 1 1 1 1 1

        2. we can further reduce the search space by considering only

           those rows containing at least k 1s, where k is some

           function of n s.t. 1 < k < n.  for example, the set above

           is reduced to:

         1 1 0 0 0 1 1

         1 0 1 0 1 0 1

         0 1 1 0 1 1 0

         1 1 1 0 1 1 1

         1 1 0 1 0 1 1

         1 0 1 1 1 0 1

         0 1 1 1 1 1 0

         which finds two solutions:

         1 1 0 1 0 1 1

         0 1 1 1 1 1 0

         1 1 1 0 1 1 1

         1 0 1 1 1 0 1

         1 1 1 0 1 1 1

         0 1 1 1 1 1 0

         1 1 0 1 0 1 1

         1 0 1 1 1 0 1

         1 1 1 0 1 1 1

         0 1 1 1 1 1 0

         1 1 0 1 0 1 1

         0 1 1 1 1 1 0

         1 1 1 0 1 1 1

         1 0 1 1 1 0 1

    the implementation requires that m <= n, and that n is odd.  the

    script contains an earlier version without these restrictions, but

    i'm not happy with my analysis for those cases.  i expect to have

    a solution soon.

    the timings are much better than those published in the article i

    mentioned.  here they are for 3 x 3 -> 11 x 11.  "#" means "number

    of minimal solutions."

    results: 3.0 ghz

         rows   cols    ms     #   empties

         ----   ----    --     -   -------

          3      3      0      6      1

          3      5      0      1      4

          3      7      0      1      6

          3      9      0      1      7

          3     11     15      4     10

          4      5      0      2      6

          4      7      0      2      7

          4      9      0      6     10

          4     11     15      1     11

          5      5      0      1      7

          5      7      0      7     10

          5      9      0      6     12

          5     11     31      3     14

          6      7     15      1     11

          6      9      0      4     14

          6     11     78      3     17

          7      7     15      2     12

          7      9     15      1     16

          7     11    203      3     19

          8      9     31      1     18

          8     11    531      7     22

          9      9     78     12     21

          9     11   1390      1     24

         10     11   3671      2     27

         11     11   9687     19     30

    >

    > John Carter                             Phone : (64)(3) 358 6639

    > Tait Electronics                        Fax   : (64)(3) 359 4632

    > PO Box 1645 Christchurch                Email : john.carter@...

    > New Zealand

    >

    > Refactorers do it a little better every time.

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## John Carter — 2005-03-31 01:31:40

    On Wed, 30 Mar 2005, stevan apter wrote:

     >>> Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells

    >>> on the grid so that you can reach each Planted cell while standing in an Empty cell.

    >>> In other words, for each Planted cell, one of its four neighbors (no diagonals) must

    >>> be Empty. Thus, you can tend your garden without ever standing in the planted areas

    >>> (which would compact the soil and potentially damage the plants that are growing

    >>> there).

    > i make two assumptions:

    >

    >    1. a minimal solution for m rows, n cols can always be constructed

    >       from the set of symmetrical rows of length n.

     Hmm. I'm not sure I believe that. What about m==n==2?

    PE

    PP

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Refactorers do it a little better every time.

## stevan apter — 2005-03-31 02:27:50

    ----- Original Message -----

    From: "John Carter" <john.carter@...>

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, March 30, 2005 8:31 PM

    Subject: Re: [stack] the garden problem

    >

    > On Wed, 30 Mar 2005, stevan apter wrote:

    >

    > >>> Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells

    > >>> on the grid so that you can reach each Planted cell while standing in an Empty cell.

    > >>> In other words, for each Planted cell, one of its four neighbors (no diagonals) must

    > >>> be Empty. Thus, you can tend your garden without ever standing in the planted areas

    > >>> (which would compact the soil and potentially damage the plants that are growing

    > >>> there).

    >

    > > i make two assumptions:

    > >

    > >    1. a minimal solution for m rows, n cols can always be constructed

    > >       from the set of symmetrical rows of length n.

    >

    > Hmm. I'm not sure I believe that. What about m==n==2?

    as i said, the algorithm assumes odd n.  i should have added:  and n>2.

    (which is obvious from the code, and from the table of results.)

    > PE

    > PP

    >

    >

    >

    > John Carter                             Phone : (64)(3) 358 6639

    > Tait Electronics                        Fax   : (64)(3) 359 4632

    > PO Box 1645 Christchurch                Email : john.carter@...

    > New Zealand

    >

    > Refactorers do it a little better every time.

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## Greg Buchholz — 2005-03-31 16:17:48

    --- John Carter <john.carter@...> wrote:

     > On Wed, 30 Mar 2005, stevan apter wrote:

    > >    1. a minimal solution for m rows, n cols can always be constructed

    > >       from the set of symmetrical rows of length n.

    >

    > Hmm. I'm not sure I believe that. What about m==n==2?

    > PE

    > PP

        You can't access a planted cell from an empty cell through a diagonal.

     At least according to...

    http://hcsoftware.sourceforge.net/jason-rohrer/worklog/index.php?y=2005&m=3&d=14

    So the smallest answer for the 2x2 case would be one of...

    PE   EE   EP   EP   PP   PE

    EP   PP   EP   PE   EE   PE

    Greg Buchholz

    __________________________________

    Do you Yahoo!?

    Yahoo! Mail - now with 250MB free storage. Learn more.

    http://info.mail.yahoo.com/mail_250