A constructor wishes to build a housing estate in a square terrain with 64 (8 x 8) smaller plots of land, at most one house to a plot. Local urban rules allow building a house in a plot only if at least half of the neighboring plots (within the development) are destined for parks.

What is the largest number of houses the constructor can build if he is to comply with the local rules?

In another, smaller terrain (6 x 6), another constructor built 22 houses complying with the same rules:

enter image description here

  • $\begingroup$ What neighbourhood? Moore or Von Neumann? $\endgroup$ – moonheart08 Dec 3 '18 at 19:03

Here's a way to do

39 (Old: 38 (Old Old: 36))

I'm not sure that this is optimal, though:

enter image description here

(pawns are houses, I'm kind of lazy to edit pictures of houses in onto a grid)

| improve this answer | |
  • $\begingroup$ It is still not optimal, buy you are nearly there! $\endgroup$ – Bernardo Recamán Santos Dec 3 '18 at 15:50
  • 1
    $\begingroup$ Is it optimal now? $\endgroup$ – Excited Raichu Dec 3 '18 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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