10
$\begingroup$

You are a city planner tasked with the placement of unit-square-sized houses in a rectangular-grid allotment, the size of which is up to you but must be as small as possible to save money. The number of houses is of no concern, however.

The problem is, the prospective homeowners are very picky about the number and arrangement of neighbouring houses. It is up to you to satisfy at least one of each kind of homeowner:

  • Some want no houses to the north, south, east, or west of their house
  • Some want only one house to their north, some only one to the south, some only one to the east, some only one to the west
  • Some want exactly two houses, to their north and east, north and south, north and west, south and east ... etc.
  • Some want exactly three houses, to their north and east and south, to their ... etc.
  • Some want to be surrounded by four houses, to their north south east and west

So in total, there are 16 unique kinds of homeowners (1 + 4 + 6 + 4 + 1).

As an example, consider this grid:

+---+
| o |    o = house
|ooo|    grid: 3x3
| o |
+---+

The above grid satisfies exactly 5 kinds of homeowners: all four of the kind that only want one neighbour, plus the one that wants four neighbours. The size of the grid is 3x3 = 9.

How can you arrange the houses, to satisfy at least one of all 16 kinds of homeowners, while minimising the size of the grid?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
8
$\begingroup$

So I got this for a 4x6 grid:

oo o
o o 
oooo
  oo
oooo
 o

Which technically minimizes the area to 24.

Naturally, all reflections and rotations work as well.

Also, a 3x8 solution which has the same score:

ooo
oo 
o o
 o 
ooo
ooo
  o
ooo

Also I will try to set a lower boundary for this problem:

Dimensions:

  • 3x3 minimum for the all-neighbor house

Number of spots:

  • 16 houses (at least)

  • The no-neighbors house:

    • If at a corner - 2 more spaces. However, the two-neighbor house that would fit in that corner would require 2 more spaces - so 4.
    • If at an edge - 3 more spaces - if edge is 4 or less it will ruin one corner spot requiring two more spaces - so either 5*something or 5 spaces in total.
    • If at an internal spot - 4 more spaces.

So far we've got a minimum of 20.

So the possibilities are 21 (3*7) and 20 (4*5).

Now we need a total of 4 + 4*1 + 6*2 + 4*3 + 0 = 32, "empties". However, any internal empty spot actually is empty for the neighboring houses (max four), and we also have "default" empty spots at the edges, each counting as 1 empty spot. So for the two cases we have:

  • 3*7: 32 - (6 + 14) = 12
  • 4*5: 32 - (8 + 10) = 14

So we need to have 12/14 empty values through empty spots. However, in order for an empty value to count as 4, it has to be surrounded by 4 houses.

SO FAR

So far 20 is the lower boundary, but I will think about it a bit more, I'm pretty certain that it can be proved that 3*7 and 4*5 will not work. For starters, we cannot place 4 internal empty spots in 3*7. I will give it more though and update this :)

Improve this answer
$\endgroup$
10
  • $\begingroup$ There are only 2^20=1M different cases for the 4x5 grid, I can write a simple program to check all of them once I get back to my computer. I think you're right though... $\endgroup$
    – 2012rcampion
    May 25, 2015 at 16:15
  • $\begingroup$ Testing both 4x5 and 3x7, I found no solutions. Right now I'm counting the number of 4x6 solutions. $\endgroup$
    – 2012rcampion
    May 25, 2015 at 17:47
  • $\begingroup$ @2012rcampion I already wrote such a program. The point was to get a formal proof for that :) $\endgroup$
    – dmg
    May 25, 2015 at 18:22
  • $\begingroup$ Proof by enumeration is a valid proof type =) $\endgroup$
    – 2012rcampion
    May 25, 2015 at 18:23
  • $\begingroup$ @2012rcampion It most certainly is, but I'm certain it is not the "cleanest" way to proof this :) $\endgroup$
    – dmg
    May 25, 2015 at 18:26
7
$\begingroup$

Not sure if this is the optimal strategy, but it works:

5x5 grid
000+0
++++0
000+0
000++
000+0

Where 0's are houses and +'s are empty plots. The 3x3 house group suffices the 1 that wants all sides surrounded, the 4 that want 3 sides, and 4/6 that want 2 houses (adjacent sides). The 3x1 house groups get the last 2/6 that want 2 houses (opposite sides), as well as all 4 of the 1 houses. Then the single one is (surprise) the one that wants no neighbors.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For a square grid, this must be optimal, as there must be at least 16 houses, and so you need more than 16 plots. But perhaps there's a better solution on a non-square grid? $\endgroup$
    – Glen O
    May 25, 2015 at 4:10
0
$\begingroup$

This is my best strategy that works for the given conditions:

3x7 grid
XXOXXXO
XOXOXXX
XXOXXXX

X's are the houses and O's are empty plots. It was a bit of trial and error before I stumbled across this, and the answer perfectly fits the requirements.

I would be greatly interested in seeing if someone can beat this.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ It's an interesting solution, but I think you misunderstood one of the requirements, that the arrangement of neighbours is unique. For example, it doesn't satisfy the one that wants only one house to their north; this is not the same as having houses that have exactly one neighbour. $\endgroup$
    – congusbongus
    May 25, 2015 at 5:22
  • $\begingroup$ I think he understood, he just missed that one. $\endgroup$
    – corsiKa
    May 25, 2015 at 15:57
  • $\begingroup$ Yeah, I just missed the unique orientation requirement when I crafted this solution. Now that my answer is wrong, should I delete it, or let it be? (First answer on PuzzlingSE) $\endgroup$
    – CodeNewbie
    May 26, 2015 at 4:36
0
$\begingroup$

Please see @dmg's excellent answer, which points out that the block must measure at least $3$ houses in each dimension. Therefore a grid whose size is a prime number (such as $17, 19$, or $23$) will not work, and neither will any grid whose size is $2$ times a prime number (such as $22=2*11$).

Clearly a grid of size $16=4*4$ (or anything smaller than $16$) doesn't work. Since @dmg already supplied two different solutions of size $24$, it remains only to check grids of size $18=3*6$, $20 = 4*5$, and $21=3*7$. We eliminate the $3*6$ grid, since placing the "no-neighbors" house anywhere but a corner results in fewer than $16$ houses, and the grid $$ \begin{matrix} x & 0 & x\\ 0 & x & x\\ x & x & x\\ x & x & x\\ x & x & x\\ x & x & x\\ x & x & x\\ \end{matrix} $$ simply doesn't work.

As @2012rcampion pointed out in a comment to @dmg's answer, there are only $2^{20}$, or about 1 million, possible ways to place houses in a $4*5$ grid, and similarly there are only $2^{21}$ possibilities in a $3*7$ grid, or about 2 million. So we could easily use a computer to brute-force our way through 3 million possibilities to find a minimum-size solution.

Actually it's much better than that, since we don't need to test all of these possibilities. For instance, there's no point in testing grids with fewer than $16$ houses placed. This represents a big savings: at most, we only need to test $$ \sum_{k=16}^{20} \binom{20}{k} + \sum_{k=16}^{21}\binom{21}{k} = 27896 + 6196 = 34092 $$ possibilities, rather than 3 million. (The notation $\binom{n}{r}$ represents the binomial coefficient $C(n,r)$, the number of subsets of size $r$ of a given set of size $n$.)

http://en.wikipedia.org/wiki/Binomial_coefficient

Of course, these numbers could probably be further reduced, based on the symmetries involved, etc. In any case, @dmg and @2012rcampion have been working on programs to look for solutions, but I thought that they might be interested in this strategy for reducing the number of cases to check.

Improve this answer
$\endgroup$
4
  • $\begingroup$ There are several cuts that we can do in the search space. First the "min 16 houses" cut, after that we can cut a bit based on the empty spots (as described in my answer, there is a semi-hard requirement of empty spots), and of course, we have the symmetries and rotation cutoffs (a factor 16 if I am not mistaken) $\endgroup$
    – dmg
    May 25, 2015 at 18:42
  • $\begingroup$ Actually I've already run through all 16M 4x6 cases (it took about a minute to actually run) and found that there are only 8 solutions (32 counting rotations and reflections): 4 with 16 houses, 2 with 17 houses, and 2 with 18 houses. Reducing the number of test cases is very valuable if you're actually doing a proof by enumeration, but such optimizations aren't needed to just find the answer if your computer does billions of operations per second. $\endgroup$
    – 2012rcampion
    May 25, 2015 at 18:45
  • $\begingroup$ I think you can start by assuming that (for example) it's $4\times 5$ and not $5\times 4$. In that case, the symmetries of the $4\times 5$ rectangle amount to a horizontal reflection, a vertical reflection, both, and neither (identity permutation). So the group of symmetries has order 4. See example 5.7 at: www-history.mcs.st-and.ac.uk/~edmund/lnotes/node7.html $\endgroup$
    – mathmandan
    May 25, 2015 at 18:48
  • $\begingroup$ @2012rcampion Naturally, that is how I actually found the solutions, checking if the solution is valid is ultra-fast. But hey, I try to reduce my carbon footprint :D $\endgroup$
    – dmg
    May 25, 2015 at 18:51
0
$\begingroup$

Since SE does not allow comments, here is an "answer". A fiddle that brute-forces the 3x8 combinations in 75 seconds on my machine, nothing fancy for optimizing the checks but it does the job. Can be changed for 4x6 or 5x5 (will take double time due to one more cell bit). If there were smaller solutions, they would show up in the results for larger grids too, with the first row having only zeros. But there are none.

http://jsfiddle.net/w4j5002x/8/

Improve this answer
$\endgroup$

Your Answer

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

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