# Brainteaser Analysis

This will be my first in what I hope will be an ongoing themes of posts explaining the math behind some neat brainteasers. Warning: the content of the posts will be much more enjoyable if you first attempt the brainteaser for a few minutes before reading the detailed solution.

Fill the grid below with the numbers 1 – 8 making sure that adjacent numbers do not touch (for example, 5 cannot touch 4 or 6).  In this game, if the squares are diagonal from each other, they are still considered to be touching.

Give up? Or did you solve it with some trial and error? If you did, congratulations! Either way you should stick around so you can see how to solve it systematically.

We need to introduce the basics of Graph Theory to attempt this problem. According to Wikipedia “A graph is a collection of vertices and a collection of edges that connect pairs of vertices”. A “vertex” is another name for a point and an “edge” is another name for a line that connects two points. So if you had a “graph” of a country, the cities would be vertices and the roads would be edges. Graphs are useful for solving real world problems and fun to play around with. For example, say you have one friend you know from work and one friend you know from school, but they do not know each other. Below is a graph of your relationships.

This graph reveals some things that we know intuitively. First, friend 1 and friend 2 do not know each other since there is no edge connecting them. Second, since there are 2 edges touching “you” we know you have 2 relationships. These concepts are extendable to other environments.

Time to draw a graph for the brainteaser! We will represent each square as a vertex and draw it as a small circle.  If 2 squares are touching we will connect them with an edge.

Just like the relationship graph, we can glean some helpful insights from this graph.  It is clear that some vertices connect to more vertices than others do. For example, the 2 outside vertices (highlighted in blue) only have 3 edges touching them. We call this the degree of the vertex. Thus, the 2 outside vertices each have degree 3 (this is similar to our previous example where “you” had 2 relationships or degree 2). Further, we can see that the 2 most inner vertices (highlighted in red) have degree 6. We can see that the top 2 vertices (highlighted in green) have degree 4. As you would expect, the bottom 2 vertices (highlighted in yellow) also have degree 4. Now for some quick number crunching!

We will assign each of our 8 numbers a number “P” which will stand for the number of possible other numbers it is permitted to touch in our game (a bit confusing, I know, but stay with me). For example, since the number 3 is permitted to touch 1, 5, 6, 7 and 8, but not 2 and 4, its p-value is 5. The number 4 is permitted to touch 1, 2, 6, 7, and 8. Therefore, it also has a P-value of 5.  Below is a table of all of our 8 numbers and their associated P-values.

 Number P-value 1 6 2 5 3 5 4 5 5 5 6 5 7 5 8 6

The 2 red vertices have the highest degree, 6 (since there are 6 lines touching each red point), so we will focus on them. If the degree of one of the red vertices is 6 then any number that could go there must also have a P-value of at least 6 as well. If the number had a P-value of 5, then when trying to place the surrounding numbers we would “run out” of candidates. Give it a try!  Now refer to the diagram below where we attempt to place the number “4”, which has a P-value of 5, in the red dot space.

We have used up all the numbers available to the 4 and there is nothing left to place in the left- most blue space (since 3 and 5 are illegal).

So the only candidates for the red vertices are 1 and 8. I have placed them in the boxes below.

This also forces the placement of the 2 since it cannot touch the 1. Similarly for the 7, there is only one square not touching the 8.

The 3 now only has two spots available since it cannot touch the 2, so we can place it in either one. Similarly, the 6 only has two spots available since the 7 is touching two of the remaining four spots. We will slot the 3 in the bottom spot for now. (After we solve it with the 3 and the 6 in the places I put them, you can try to see what happens if you put the 3 in the top spot and then the 6 in the bottom spot.)

The 5 cannot go next to the 6 so its place is fixed and the 4 cannot go next to the 3 so it is fixed as well.

And there we have it, a solved brain teaser. Just like in a game of Sudoku, once you can get a couple numbers figured out the rest fall into place quite easily. The trick was using a “graph”.