3

There is a puzzle: "Fill the board with letters from A to G, that in the field and in its surrounding each letter is placed only once (can't be repeated). This rule concerns also fields with not full surrounding e.g. edge fields.

honeycomb

Could you tell me if there is a mathematical equation, which solve the puzzle?

Honeycomb puzzle

dantopa
  • 10,342
Jacek
  • 31

3 Answers3

1

The interesting thing about this puzzle is how constrained the solution is.

Suppose you wanted to construct one of these puzzles, starting with a "honeycomb" with no letters filled in. Consider one of the hexagonal cells of the honeycomb and the six cells adjacent to it. The conditions of the puzzle require these seven cells to be filled with seven different letters, one copy each of the letters A to G. For example, you could fill them in as shown below.

enter image description here

Figure 1

(This particular arrangement actually occurs in the center of the given puzzle after filling in the empty cell surrounded by six filled cells.)

If you measure the distance between two cells by counting the number of steps you must take to travel from one cell to the other, where each step moves from one cell to an adjacent cell, the conditions of the puzzle prevent any letter from being less than three steps distant from any other copy of the same letter, because if there were a path of two steps, the cell in the middle of that path would have two copies of one letter in cells adjacent to it.

It follows that the letter in the center of this group of seven cells cannot appear in any of the $12$ cells adjacent to the group, each of which is two steps from the center cell. So the unshaded cells below can only be filled with the other six letters; in this example, A, B, C, E, F, or G.

enter image description here

Figure 2

Since there are $12$ cells to be filled with six letters, at least one letter must occur two or more times. Suppose A is such a letter.

Among the unshaded cells, we can rule out putting an A in any cell other than the ones marked v, w, x, y, and z, since the other unshaded cells are too close to an A.

We can rule out putting an A in the cell marked x, since then we cannot place other A.

If we put an A in the cell marked v, we cannot place an A in cell w. If we then place an A in cell z, cells w, x, and y must be filled with other letters; the letters B, D, F, and G are all too close to each of the cells w, x, and y, so we can only fill those cells with C and E. But that would require two copies of one of those letters, and these three cells are all too close to each other to hold two copies of one letter. Therefore, if we place a A in cell v, we must place the second A in cell y. Conversely, if we place an A in cell y, we obviously can only place the second A in cell v.

Likewise, we can place an A in cell w if and only if we place an A in cell z.

This means we have exactly two choices how to place two As in these cells. Let's take the second choice (since it happens to agree with the example in the question): an A in cell w and an A in cell z.

Then the only letter we can put in cell x is E, and the only letter we can put in cell y is C. We arrive at the configuration below:

enter image description here

Figure 3

We have established that it is impossible to get more than two copies of A into the $12$ cells surrounding the central cluster; the same reasoning applies to every other letter we could put in those cells. Since we still must fill $12$ cells with six letters, this means that every letter must appear exactly twice in those $12$ cells.

Following the same logic that we used for the letter A (could appear in cells v and y or in cells w and z, no other combinations), we can conclude that a C must occur in the cell marked t and an E must occur in the cell marked n.

enter image description here

Figure 4

The cells within two steps of cell v dictate that we must put an F in cell v, which dictates that we must put another F in cell q. Similarly we must put a letter G in cell u and therefore also put a G in cell r. The remaining two cells, p and s, therefore must be filled with the letter B.

enter image description here

Figure 5

It follows that by knowing the arrangement of the seven letters in one cell and its six adjacent cells, plus knowing one more letter adjacent to that group of cells, we know all the letters adjacent to that group of cells. We can now repeat this pattern indefinitely to deterministically fill in all the other cells in the plane as long as each cell we fill is part of a complete set of $12$ adjacent cells around a cluster of seven cells (six cells adjacent to one cell) where all letters in the cluster plus one more adjacent letter are known.

That is, aside from the choices involved in choosing a letter, placing six other letters around it, and choosing one of the two ways one of those letters can be repeated adjacent to this cluster of seven cells, the only possible variations in how we fill in the honeycomb would be in border cells that are not part of a complete cycle of $12$ cells.

To fill in a large honeycomb, you could take a shortcut by observing that the repetitions of each letter form equilateral triangles. The figure below shows the triangles for A and B.

enter image description here

Figure 6

Note that the sides of the triangle for letter B and parallel to the sides of the triangle for letter A. No matter which letter we look at, we get equilateral triangles with sides parallel to the sides of other letters' triangles. You can then replicate each letter by building up its grid of equilateral triangles, for example as shown below.

enter image description here

Figure 7

You could do this for each of the letters, or you could just place copies of the letter A and then fill in the cells adjacent to each A the same way the are arranged for a copy of A whose adjacent cells are already known.


Now let's suppose instead that someone else has constructed a puzzle for you. Note that they were constrained by the same rigid constraints described above.

In solving a puzzle constructed by someone else, you need at least six different letters given as clues; if there are only five different letters, you will inevitably have unknown locations that could be filled in with either of the remaining letters. Moreover, you need either to have two copies of one letter (which will tell you which way to construct the sides of your equilateral triangles in order to repeat letters), or you must have two different letters in spaces that at vertices of the same lattice of equilateral triangles, because there are only two sets of possible equilateral triangles that can be built on any letter, and this will eliminate one of them.

The only tricky part of this is how to deal with letters on or near the border of the puzzle, which might not be part of a $19$-cell cluster or might belong to a cluster not well-enough connected to the others. In the example in the question, only eight cells are in question, namely the two cells in each "corner" of the puzzle.

David K
  • 98,388
0

In the case you've posted, the simple algorithm can be applied:

  1. Find an empty field, that is surrounded by 6 filled fields or filled field that is surrounded by 5 filled and one empty field (there are 2 such fields).
  2. Fill the empty field with missing letter
  3. If the board is not filled, go back to 1.

I suppose, that on the higher levels of difficulty you should use some different methods like in sudoku.

0

This puzzle is related to the Hadwiger-Nelson problem. Note that in the shown honeycomb you can see four equal letters forming a parallelogram and three more equal letters that can be supplemented to a homothetic parallelogram. This idea might speed up the solution process.