11
$\begingroup$

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$?

enter image description here

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Sniped for a single typo check! (You posted while I was doing my final typo once-over) $\endgroup$ – bobble Apr 8 at 3:44
  • 1
    $\begingroup$ 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... $\endgroup$ – Tesla Daybreak Apr 8 at 3:58
7
$\begingroup$

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)$

$\endgroup$
6
  • 1
    $\begingroup$ This is a very nice and general method. $\endgroup$ – Dmitry Kamenetsky Apr 8 at 18:46
  • $\begingroup$ 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$ $\endgroup$ – Rad80 Apr 8 at 19:33
  • 1
    $\begingroup$ @Rad80 Yes, I noticed that, but it worked for this one, so I didn't bother making it stronger $\endgroup$ – Cyrille Corpet Apr 8 at 19:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Dmitry Kamenetsky Apr 9 at 1:19
  • $\begingroup$ That's really nice! Can you share the idea of the proof? $\endgroup$ – Rad80 Apr 9 at 8:19
5
$\begingroup$

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 1

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 2

Step 3:

The same logic places the 4 and the 5.
Step 3

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.
Step 4

$\endgroup$
6
  • 1
    $\begingroup$ I'm sure you got this earlier than I did:) I was too lazy to draw pictures. $\endgroup$ – Tesla Daybreak Apr 8 at 3:45
  • $\begingroup$ I had this solved about 10 minutes ago and the rest was typing up detailed explanations and pictures :) $\endgroup$ – bobble Apr 8 at 3:46
  • $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky Apr 8 at 3:49
  • $\begingroup$ My point was that the 9 can't go anywhere but that corner, because where-ever it goes must be a 0 $\endgroup$ – bobble Apr 8 at 3:50
  • $\begingroup$ oh i see. Yes that's true. It wouldn't work if there were multiple zeroes in H. $\endgroup$ – Dmitry Kamenetsky Apr 8 at 3:52
1
$\begingroup$

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.

$\endgroup$
0

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.