# Deriving a 3x3 grid from another one

A $$3 \times 3$$ grid $$G$$ is filled with every number from $$1$$ to $$9$$. Now a new $$3 \times 3$$ grid $$H$$ is formed, such that $$H_{ij}$$ is the number of neighbors of $$G_{ij}$$ that are greater than $$G_{ij}$$. Two cells are neighbors if they are adjacent horizontally, vertically or diagonally. Given the grid $$H$$ shown below, can you derive the contents of grid $$G$$?

Solution:

$$\begin{pmatrix}5&6&7\\4&8&2\\9&3&1\end{pmatrix}$$

Deduction process:

Basically, $$9\rightarrow8\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow7\rightarrow5,6$$. First, notice $$9$$ must correspond to a $$0$$ in $$H$$, so it's in the $$(3,1)$$ position. Now every other number in $$H$$ is at least $$1$$, so $$8$$ must be adjacent to $$9$$ and correspond to a $$1$$ in $$H$$, hence at $$(2,2)$$. A similar reasoning puts $$1,2$$ at $$(3,3),(2,3)$$ respectively. Now $$3$$ must be at $$(3,2)$$, otherwise it would have at most one adjacent cell smaller than it, which is not true for all other ones. Continuing in this manner, $$4$$ must be at $$(2,1)$$, and then $$7,5,6$$ follows. (at this point one can even brute force it) This is probably not the fastest way though.

• Yeah, I was trying to edit in some logic. The difficulty is that at some point, the problem becomes simple enough that I would try to brute-force it and abandon logic... Commented Apr 8, 2021 at 3:58

I have the same final answer as the others, but using only one repeated method, namely

If there is only one $$0$$, it must be the greater remaining number, when we keep track, for each undiscovered cell, of the number of undiscovered neighbours that are greater.

This gives the following first step

$$\left(\begin{array}{ccc}x & x & x \\ x & x & x \\ 9 & x & x \end{array}\right)$$ and the new $$H$$: $$\left(\begin{array}{ccc}2 & 2 & 1 \\ 3 & 0 & 4 \\ x & 2 & 3 \end{array}\right)$$

We still only have one $$0$$, so it must be the maximum ie $$8$$, and we repeat this down to $$1$$:

$$G$$: $$\left(\begin{array}{ccc}x & x & x \\ x & 8 & x \\ 9 & x & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}1 & 1 & 0 \\ 2 & x & 3 \\ x & 1 & 2 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}x & x & 7 \\ x & 8 & x \\ 9 & x & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}1 & 0 & x \\ 2 & x & 2 \\ x & 1 & 2 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}x & 6 & 7 \\ x & 8 & x \\ 9 & x & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}0 & x & x \\ 1 & x & 1 \\ x & 1 & 2 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}5 & 6 & 7 \\ x & 8 & x \\ 9 & x & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}x & x & x \\ 0 & x & 1 \\ x & 1 & 2 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}5 & 6 & 7 \\ 4 & 8 & x \\ 9 & x & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}x & x & x \\ x & x & 1 \\ x & 0 & 2 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}5 & 6 & 7 \\ 4 & 8 & x \\ 9 & 3 & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}x & x & x \\ x & x & 0 \\ x & x & 1 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}5 & 6 & 7 \\ 4 & 8 & 2 \\ 9 & 3 & x \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}x & x & x \\ x & x & x \\ x & x & 0 \end{array}\right)$$

$$G$$: $$\left(\begin{array}{ccc}5 & 6 & 7 \\ 4 & 8 & 2 \\ 9 & 3 & 1 \end{array}\right)$$ $$H$$: $$\left(\begin{array}{ccc}x & x & x \\ x & x & x \\ x & x & x \end{array}\right)$$

• This is a very nice and general method. Commented Apr 8, 2021 at 18:46
• I ended up using this method, but didn't formalize it so well. It's not general though, because you could have multiple zeros in $H_n$ Commented Apr 8, 2021 at 19:33
• @Rad80 Yes, I noticed that, but it worked for this one, so I didn't bother making it stronger Commented Apr 8, 2021 at 19:51
• @Rad80 It turns out that grids $H$ that have a unique solution $G$, only have a single 0. Furthermore, there is always a single path connected 1 to 2 to 3 ... all the way to $N^2$. So it seems that this method will work for any such puzzle, no matter how large. Commented Apr 9, 2021 at 1:19
• That's really nice! Can you share the idea of the proof? Commented Apr 9, 2021 at 8:19

Step 1:

Wherever "9" goes in G, none of its neighbors will be larger. Therefore H in this spot will be 0, so the 9 in G is in R3C1. The middle cell is adjacent to all the others. Since its H is 1, only one other cell can be greater than it. Therefore its G is 8.

Step 2:

Wherever 1 goes in G, it is smaller than all of its surroundings, so its H number would be the max possible. This is only possible in R3C3. Then whenever 2 goes its H would be the max possible (considering the fact that 2 > 1), so it goes in R2C3. Similar logic places the 3 in R3C2.

Step 3:

The same logic places the 4 and the 5.

Step 4/solution:

Our H tells us that R1C3 can only be smaller than one neighbor. Therefore it can't have a 6 in G, because the 7 would go in R1C2 then R1C3 would be smaller than the neighboring 7 and 8. Therefore R1C3 is 7, R1C2 is 6, and the puzzle is complete.

• I'm sure you got this earlier than I did:) I was too lazy to draw pictures. Commented Apr 8, 2021 at 3:45
• Actually H can have a 0 without it being a 9 in G. You just need to be surrounded by everything smaller than you, ie local maxima, but not necessarily global maxima. So you need to refine step 1. Commented Apr 8, 2021 at 3:49
• My point was that the 9 can't go anywhere but that corner, because where-ever it goes must be a 0 Commented Apr 8, 2021 at 3:50
• oh i see. Yes that's true. It wouldn't work if there were multiple zeroes in H. Commented Apr 8, 2021 at 3:52
• Interestingly all such 3x3 puzzles that have a unique solution (784 of them), only have a single 0. Commented Apr 8, 2021 at 3:58

I came up with the same solution as the other answers, but I did it a different way

The solution:

5 6 7
4 8 2
9 3 1

Steps:

First notice that the center square touches all other squares. Since it's a 1, that means that there is only 1 number greater than it in the entire puzzle, so it must be an 8.

Then, notice the 0 in the corner. Since it's adjacent to the 8, and no adjacent values are greater than it, it must be the 9.

From this point, we can follow a path of squares where the number of neighbors greater than it have already been revealed. Since we have filled in the highest numbers already, each of these squares must have the next-highest value.

The 1 in the top-right corner is adjacent to the 8, so this must be a 7.

The 2 in the top-middle is adjacent to the 7 and 8, so this must be a 6

The 2 in the top-left is adjacent to the 6 and 8, so this must be a 5

The 4 in the middle-left is adjacent to the 5, 6, 8, and 9, so it must be a 4

The 3 in the bottom-middle is adjacent to the 4, 8, and 9, so it must be a 3

The 4 in the middle-right is adjacent to the 3, 6, 7, and 8, so it must be a 2

And finally, the 3 in the bottom-right is adjacent to the 2, 3, and 8 (and is also the only remaining square), so it must be a 1

Edit: I realized that this method is not guaranteed to work.

For example, the 1 adjacent to the 8 could have been a 6 instead of a 7, as long as there wasn't a 7 adjacent to it. I'll leave this answer up as it's interesting that it still worked.