# A flag-packing problem

An entry in Fortnightly Topic Challenge #45: Flags

You are provided with a 9x9 grid of squares and 21 minimalistic flags (pictured below, all shown to scale).

TASK: Assign a colour (Black, Blue, Green, Orange, Red, White, or Yellow) to each of the 81 numbered cells so that the grid can be exactly partitioned into 21 shapes equivalent to the pictured flags (without rotation or reflection). Each cell must be covered by part of exactly one flag, every pictured flag must appear in its own right, and the following rules must be satisfied:

1. Horizontally or vertically adjacent cells belonging to different flags must be different colours.

2. All cells containing a square number are the same colour.

3. Only 1 cell in the bottom row of the grid is occupied by a European flag (i.e. one of the flags in the top row of the image, from Denmark to Russia).

4. The flags of Austria and Russia are adjacent (i.e. at least one cell in the Austria flag borders a cell in the Russia flag, horizontally or vertically).

This puzzle can be solved purely by logical deduction - no guesswork is required. Please explain the logical steps leading to your answer.

NB The symbols on the flags of Cameroon and Guatemala can be ignored. Flags are all 3x3, 3x1 or 1x3 grid cells in size.

Colour guide available here. Bk=Black, B=Blue, G=Green, O=Orange, R=Red, W=White, Y=Yellow.

• Now I want to see a puzzle like this, only allowing overlaps, so each cell can belong to multiple flags. Might get tricky to put together, and in this case there'd be multiple solutions (e.g. the Denmark flag has 2 Austria flags already built in, so you really couldn't use both of them in 1 puzzle.) Dec 16, 2020 at 16:14

I think I have the answer:

The first step is to determine the color of the square numbers.

Now, because the 16 and the 25 are adjacent and have the same color, they must be part of the same flag. This means they must be part of the flag of Denmark, Sweden or Finland. So let us try first with Sweden. There are 2 possible positions, either with the top of the flag in the 1st or 2nd row. Starting with the 2nd row, we have:

The yellow 9 could be taken by Lithuania, but then we have no choice for the yellow 1. We could use Cameroon instead (as pictured) but then we have no choice for the yellow 4. So this position is not possible. The other possibility is having the Swedish flag in the top row. But this means Lithuania must be used for the yellow 9 and we have no choice for the yellow 1. So, we cannot use the Swedish flag.

Next, let us try the

Finnish flag. Again, we start with the top of the flag in the 2nd row:

The only choice for the blue 9 is Estonia. But then we have a problem with the blue 1. It cannot be Sweden or Guatemala as they would both border the blue 4. And if we place the Finnish flag in the top row, there is no choice for the blue 9 at all. So it cannot be the Finnish flag and must be the Danish flag.

Again, the flag could be in

two positions. If the top of the flag was in the 2nd row, we get this:

The white 9 could be Russia or Bulgaria. But Russia needs to border Austria, which would not be possible. So it must be Bulgaria. The choices for the white 36 are now N. Ossetia or Russia. But again, it cannot be Russia as it need to border Austria, which isn't possible. So it must N. Ossetia and the white 1 must be Russia. The only way to make Austria adjacent to Russia is as shown. But now we have a problem with the white 4. It must be at the end of a horizontal flag and there is no horizontal flag with white at the end. So the Danish flag must be in the top row.

Knowing this, we get

the following snapshot:

Again, Russia cannot use the white 9 as it needs to border Austria. And it also cannot use the white 1, so we must have the situation above (Estonia is the only possibility for using the white 81).

A few more

placements are shown below.

Bulgaria is the only remaining choice for the white 1 and Cameroon the only choice for being below the Danish flag. In addition I have started to look for positions where the Finnish flag can be placed. These are shown as 3x3 thick border boxes.

When you now consider

how the placement of the Swedish flag affects the possible locations of the Finnish flag, it turns out that the only possible placement of the Finnish flag is as shown below:

Below the Finnish flag there must be

a horizontal flag. The only possibility is the flag of Guinea. And the only possibility for the flag below Guinea is Guatemala. Now, Mali cannot be used to cover the white 4 and we need 2 more horizontals in the 2 bottom rows, so one of them must be Mali. It can only be placed as shown below. This means Nigeria cannot be the last remaining horizontal in the 2 bottom rows as it clashes with the green of Mali. Hence the last horizontal must be Cote d' Ivoire. And Nigeria must cover the white 4. The 2 verticals which need to be placed at the left end of the bottom row must both be non-European and can only be Armenia and S. Leone as shown.

It remains to place

the Swedish flag. It cannot be placed with the top left corner in square 28 or square 20 as this would leave spaces which could not be filled with vertical 3-pieces. So it must be placed with the top left corner in square 12. We now have 5 remaining flags (Germany, Hungary, Lithuania, Netherlands and Gabon) and there is only one spot where Lithuania can be, giving us:

Neither Germany nor Gabon can have their top in the 2 square or the 40 square and because of their common yellow color, it must be Germany in square 39 and Gabon in square 29. This in turn forces the Netherlands to use square 2 and Hungary to use square 40. And we are done!

Whew! That was a long explanation. But I hope it makes sense.

An excellent puzzle, as usual!

• Confirmed via integer linear programming. Dec 16, 2020 at 1:58
• Well done Jens, you have the final answer exactly right :) Your logical process is generally the same as the path I created although there are a few areas where it could be tightened up a little. (I knew this would be a tricky one to write up, so that's understandable...). e.g. Once you place the Finnish flag you can actually map out the rest of the grid in terms of what shapes will fit where, which gives you the Swedish flag immediately. Also the logic which is hidden behind your 'bit of fiddling' at the end is actually quite nice - it would be a shame not to mention it! :)
– Stiv
Dec 16, 2020 at 9:47
• @Stiv I've expanded on the "bit of fiddling". :-)
– Jens
Dec 16, 2020 at 15:30
• Thanks Jens - nice job. Yes, it's the 'common yellow' that makes for a neat end to the puzzle. Glad you enjoyed it - here's a checkmark for you! :)
– Stiv
Dec 16, 2020 at 16:53