Place 4x12 detainees on a 7x7 grid of cells

Question

You are a prison captain and you have got 4 groups of detainees, let's call them Red, Blue, Green and Yellow. You have got 12 of each. The prison is a square grid 7x7 cells. You need to place the 48 detainees into the 49 cells (so 1 cell will remain empty). The catch is that you can't place two detainees of the same colour into adjacent cells (not even corner adjacent, i.e. ones that touch by their corners), as that way they would organize a riot and escape.

Can you do it? If so, how? If no, why?

---

Note that for instance for 4 detainees per group on a 4x4 grid it's easy:

R B R B
G Y G Y
R B R B
G Y G Y

It's also doable for 2 detainees per group on a 3x3 grid:

R G B
Y - Y
R G B

Answer 1

There is a solution:

A computer program finds 48 solutions. The solution above can have 4! = 24 permutations of the four colours and each solution can be reflected.

Answer 2

^{Inspired by my answer to a more general puzzle.}

This is a stream-of-consciousness answer showing exactly the thought process needed to find the solution. If you just want to know the answer, skip to the end.

Let's label the 4 different groups of detainees by A, B, C, D, and look at how we might place them in the 48 cells provided. First of all, note that any $2\times2$ square of cells must contain each of A,B,C,D exactly once. So we can start off with:

A B * * * * *
C D * * * * *
* * * * * * *
* * *   * * *
* * * * * * *
* * * * * * *
* * * * * * *

Now the first two cells in row 3 must be A and B in some order, and the first two in row 4 must be C and D in some order, and so on all the way down. Something like this (up to reordering of each pair):

A B * * * * *
C D * * * * *
A B * * * * *
C D *   * * *
A B * * * * *
C D * * * * *
A B * * * * *

We can do the same starting from the right-hand side instead of the left. But so far the A's and B's outnumber the C's and D's, so let's balance that by swapping them on the right:

A B * * * C D
C D * * * A B
A B * * * C D
C D *   * A B
A B * * * C D
C D * * * A B
A B * * * C D

Extending the same pattern inwards looks promising, but let's stop before the central column since we can't go beyond the hole there (and we need to consolidate the difference between AB and CD in a single row at some point):

A B A * D C D
C D C * B A B
A B A * D C D
C D C   B A B
A B A * D C D
C D C * B A B
A B A * D C D

But now there are no viable possibilities for any of the cells in the central column: each one is next to an A, a B, a C, and a D. So we'll need to change some of the half-rows from ABA to BAB (or vice versa) or CDC to DCD (or vice versa). Bearing in mind that too many ABA's compared to BAB's will make the A's outnumber the B's, let's try filling the top half of the square with ABA's and CDC's (so that the top half of the central column can be B's and D's) while filling the bottom half with BAB's and DCD's (so that the bottom half of the central column can be A's and C's):

A B A * C D C
C D C * A B A
A B A * C D C
C D C   B A B
B A B * D C D
D C D * B A B
B A B * D C D

At this point we have 10 A's, 11 B's, 11 C's, and 10 D's. So in the central column, we want the A's and D's to outnumber the B's and C's. The final answer is:

A B A D C D C
C D C B A B A
A B A D C D C
C D C   B A B
B A B A D C D
D C D C B A B
B A B A D C D

... which we can easily check satisfies all the required conditions.

Answer 3

Here is my solution(I used numbers 1 to 4 for groups)

I started with the space in the middle, then put 1-2-3-4 on each side then spiraled all the way out. 2121343
3434212
2121343
434_212
1213434
4342121
1213434

Answer 4

@M Oehm already gave a construction, but for completeness I will add the analysis which yield all solutions.

Remark: Never mind, I just noticed @Rand Al'Thor already posted something similar.

First, notice that up to relabeling, there are 2 possible combinations for a 3x3 square:

A B A
C D C
A B A

and

A B A
C D C
B A B

Also, notice that for every 2x3 block, its left and right sides contain the same letters:

A ? A
B ? B

or

A ? B
B ? A

Now look at the top-left corner of the grid - (1, 1), let's say it is colored in A. Using the first observation above, we see that least one among (1, 3) and (3, 1) is colored also in A, WLOG (1, 3) is A. Using the second observation above, we see that either (3, 1) and (3, 3) are colored in A, or (3, 2) is colored in A.

If we assume the latter, then (3, 4) must be colored in A, then (1, 6) must be colored in A, then (3, 7) must be colored in A, and finally (1, 8) must be colored in A. This makes a total of 7 A's in the first 3 rows, and there should be 5 more in the last 3 rows. Using similar arguments, we see that the only option for them are the cells (5, 2), (7, 2), (6, 4), (5, 6), (7, 6). However, now if (3, 1) is colored in B, then also (1, 2), (3, 3), (1, 4), (3, 5), (1, 6), (3, 7), (5, 1), (7, 1), (5, 3), (7, 3), (5, 5), (7, 5), (5, 7), (7, 7) should be colored in B as well, which makes a total of 15 Bs, which is impossible.

Thus we see that each of the 4 3x3 corner squares has all of its vertices painted in the same color. It is easy to see that these colors are different for all of them, otherwise the number of As will become larger than 12. From here it is straightforward to see that up to relabeling, there is just one possibility for the 4 3x3 corner squares:

A C A ? B D B
B D B ? A C A
A C A ? B D B
? ? ? X ? ? ?
C A C ? D B D
D B D ? C A C
C A C ? D B D

Now we just have to fill out the remaining 12 squares.

Answer 5

The answer is Impossible

The formation of a prisoner in the middle must be :

aba
cdc
aba

if you create other formation such as :

abc
cda
abc

then you extend it like this

abcabc
cdacda
abcabc

any 2 $a$ prisoner will adjacent each other or like this :

cdabcda
abcdabc
cdabcda

2 prisoners $a$ at the corner will adjacent.

so

You can not create any other formation, besides it will make any two prisoner in a group adjacent one other so if there are 4 groups with equal numbers of prisoners, only $2^n$, grid of cells can satisfy the formation, although 1 cell can be empty.

Here is a related puzzle

Answer 6

This intuitive approach worked almost trivially and was being written up when the computerized solution was posted, and thus seemed irrelevant, but seems relevant after all in light of the other manual approaches posted.

Step 1. If a simple solution exists, it might have the following rotationally symmetric layout.

   +-----+-----+-----+-----+-----+-----+-----+
   |  R                    |              B  |
   +                       +                 +
   |   A 3 x 4 pattern     | Same pattern,   |
   +   based on having R   +  rotated and    +
   |   at the outer corner |   based on B    |
   +-----+-----+-----+-----+ being at the    +
   |                 |empty| outer corner    |
   +   Same pattern, +-----+-----+-----+-----+
   |   rotated and   |      Same pattern,    |
   +   based on Y at +  rotated and based    +
   |   outer corner  | on G at the corner    |
   +                 +                       +
   |  Y              |                    G  |
   +-----+-----+-----+-----+-----+-----+-----+

Step 2. Noting that a pair of rows or columns behaves like alternating dominos, any of which might be flipped, the two rows along the top edge of the grid would consist of:

   +-----+-----+-----+-----+-----+-----+-----+           +-----+        +-----+      +-----+
   |  R  |  g  |  r  |  g  |  r  |  g  |  B  |           |  r  |        |  r  |      |  b  |
   +     |  &  |  &  |  &  |  &  |  &  |     +   where   |  &  |   is   |     |  or  |     |
   |  b  |  y  |  b  |  y  |  b  |  y  |  r  |           |  b  |        |  b  |      |  r  |
   +-----+-----+-----+-----+-----+-----+-----+           +-----+        +-----+      +-----+
   |                                         |
   :                                         :

Step 3. As there must be a discontinuity in the orientations of r & b tiles, perhaps their orientations flip at the boundary between the 3 x 4 regions of step 1.

   +-----+-----+-----+-----+-----+-----+-----+
   |  R           r        |  b           B  |
   +                       +                 +
   |  b           b        |  r           r  |
   +                       +                 +
   :                       :                 :

Step 4. Making the same assumption/guess for the other 3 edges of the grid produces:

   +-----+-----+-----+-----+-----+-----+-----+
   |  R     y     r        |  b     g     B  |
   +                       +                 +
   |  b           b        |  r           r  |
   +                       +                 +
   |  r     y              |        g     b  |
   +-----+-----+-----+-----+                 +
   |                 |     |              r  |
   +                 +-----+-----+-----+-----+
   |  y     r        |              b     g  |
   +                 +                       +
   |  g           g  |        y           y  |
   +                 +                       +
   |  Y     r     y  |        g     b     G  |
   +-----+-----+-----+-----+-----+-----+-----+

Step 5. This provides more than enough of a pattern to mindlessly fill the rest of grid.

 +-----+-----+-----+-----+-----+-----+-----+
 |  R     y     r     y  |  b     g     B  |
 +                       +                 +
 |  b     g     b     g  |  r     y     r  |
 +                       +                 +
 |  r     y     r     y  |  b     g     b  |
 +-----+-----+-----+-----+                 +
 |  g     b     g  |     |  r     y     r  |
 +                 +-----+-----+-----+-----+
 |  y     r     y  |  b     g     b     g  |
 +                 +                       +
 |  g     b     g  |  r     y     r     y  |
 +                 +                       +
 |  Y     r     y  |  b     g     b     G  |
 +-----+-----+-----+-----+-----+-----+-----+   

And it happened to work out.