Why are graphs useful

Language: English/Inglês What is in this post: "Draw this figure wihout lifting your pencil" problem, Seven bridges of Königsberg problem, "Houdini's last trick"-simplified problem, graph representation of a problem, Eulerian trail, solution to problems

Wassup?
I've got 3 problems for you to solve. Ok, you don't need to solve them, but just try to read and understand them.

1. Drawing a figure

Can you draw this figure without lifting your pencil and writing any segment twice?

2. Seven Bridges of Königsberg

Find a walk through the city that would cross each and every bridge once and only once. The islands cannot be reached by any route other than the bridges, and every bridge must be crossed completely every time: one can't walk halfway onto the bridge and then turn around and later cross the other half from the other side.

3. Safe house

Mr. Vinci wants to close all the doors in his house. He wants to find a route such as he doesn't need to cross any door twice. He doesn't care whether he starts and finishes inside or outside the house. Can you help him?

Guess what... The problems are all the same with just different topologies. I know, it's kinda obvious now that you read them all in a row. But had I shown you problem 3 last week and now problem 2, you probably wouldn't realize they are the same kind of problem, unless you already knew this kind of stuff.

Just like there is a large amount of problems which can be translated into a simple equation, there is a large amount of problems which can be represented by a graph. What's the point? Well, many times, the context in which a problem is presented to you provides unnecessary details for it's resolution. If we can represent those problems in a consistent way that allows us to abstract ourselves from those details, we will be more successful at solving them. And a graph is a great representation for all these problems and many, many more (believe me, even some weirdest looking problems may end up being easily solved when represented through a graph) .
I bet that you can solve any of this problems easily, but just let me increase their dimensions and you will have a hard time unless you create a decent algorithm to do it. (even thought I won't focus on that  matter in this post, keep reading for some clues)

So what is a graph? Son, don't hope for me to explain you, but let me tell you, they aren't the plotting functions graphs in case you are thinking that. Just eat some wikipedia cerials!

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges.

So how would be the graphs for the problems presented above?
Like this:

Note: It is often good idea to label vertices or/and edges of the graph depending on the problem. In these problems, the focus is on the edges, so I labeled them. The numbers on the first image don't represent a weight of the edges in anyway: they are just labels. You can click on the image to see it in a bigger size.

There are graphs of various types and with different characteristics. For example, there can be weighted graphs when we have associated with each edge a cost (this cost can be money, gas, distance, time, etc..). We can have directed graphs where each edge can only be crossed in one direction... There is much to explore. Eat as many wiki cerials as you want on this.
In our case, our graphs are undirected (or directed if you double the number of edges by replacing each current edge \(x\) for \(x_\nearrow\) and \(x_\swarrow\)) and unweighted, since we don't care about any kind of cost associated with the edges.

My point with this post was to show you that graphs have the potential to reveal a "common denominator" for various problems and allow a -more focused on important things- approach.
But now it would be kinda anti climatic if I didn't talk about the solution for the problems so here we go...

All these problems challenge you to find the same thing, an Eulerian trail:

An Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.

Euler stated and it was later proven that an undirected graph has an Eulerian trail if and only if it has exactly 2 or 0 vertices with an odd number of edges. Why, might you ask? Well, you can convince yourself that this is true with empirical reasoning (although there are formal mathematical proofs for it).For example:

• You can think that every time you enter on a vertex, you will also need to leave it. If you enter it twice during your trail, you will also need to leave it twice. Also if you quited a vertex, you had to have entered on it before.The exception for this statements are the first and last vertex - you can leave the first vertex without ever entering on it, and you can enter on the last vertex without ever leaving it. So for every vertex in the middle of the trail, you need  a pair number of edges.
  
• You can imagine a squared shaped graph where your path will start and finish on the same vertex. If you add an edge to the graph on that vertex to make your possible path longer, you also have to add an edge somewhere else, otherwise the vertex would have an edge connecting to empty space.
• This operation took you from a graph with 0 odd degree vertices to a graph with 2 odd degree vertices. You just can't find an Eulerian trail with a different number of odd degree vertices, accept that xD
  

So the solutions to our problems are: 1-Really? 2-Impossible 3-I mean, really :| ?

There are many algorithms for finding Eulerian paths. Hell, you can even find them with elementary linear algebra, or a backtracking algorithm (not the best methods). If you use the first, you will need a veeeery big system to find the solution to all the variables. So, yeah, not a task for a human when the number of edges starts to get bigger then 5. Computers can do it ;). Check this out for much better algorithms to do it - which, by the way, I'm not familiar with:
http://en.wikipedia.org/wiki/Eulerian_path


Hasta la vista baby.

Solving minesweeper using algebra

Language: English/Inglês What is in this post: Minesweeper linear system, Mathematica solving the system

Have you ever wondered how to solve minesweeper in a mathematical way?
I have. It is pretty easy and straightforward. I'll show you a possible algorithm for this.
Consider the following  minesweeper puzzle:

I suppose you know the rules of minesweeper:  when a cell has a number 'x', it means that in the 8 cells around that cell, there is a total of 'x' mines. For example, around the '3' cell, there are 3 mines. The objective of the game is to pinpoint the location of all the mines. But for this, you need to make sure which squares don't have mines so you can click on them to get a number which will give you a new clue.

Ok, let's give names to the cells: I'll call \(x_1y_1\) to the bottom left cell, \(x_1y_2\) to the one above it, and \(x_2y_1\) to the one at it's right, etc...

We need to express mathematically the information that is given to us. Our variables are gonna be the unknown cells around the number cells that are visible.

Unknown cells around the number cells

The name of the each variable will be the name of the cell it represents. Each of the cell variables will have the value 1, if it has a mine, or 0 if it doesn't. It can't have the value 0.5 because a cell can't have half a mine, neither the value 2, because a cell has, at most, one mine.

Now it is easy to write what we see!

\begin{array}{lcl} \forall i,j : x_iy_j = 0 \lor x_iy_j = 1 \\ x_1y_1 + x_1y_2 = 1\\ x_1y_1 + x_1y_2 + x_1y_3 + x_2y_3 + x_3y_3 = 3\\ x_2y_3 + x_3y_3 + x_4y_3 = 1\\ x_3y_3 + x_4y_3 + x_5y_3 + x_5y_2 + x_5y_1 = 2\\ x_5y_2 + x_5y_1 = 2\\ \end{array}
Now I'll tell Wolfram Mathematica (a computer program) to solve this for me:

Simplify[Reduce[
  {x1y1 + x1y2 == 1 && 
    x1y1 + x1y2 + x1y3 + x2y3 + x3y3 == 3 &&
    x2y3 + x3y3 + x4y3 == 1 &&
    x3y3 + x4y3 + x5y3 + x5y2 + x5y1 == 2 &&
    x5y2 + x5y1 == 2 &&
    (x1y1 == 1 || x1y1 == 0) &&
    (x1y2 == 1 || x1y2 == 0) &&
    (x1y3 == 1 || x1y3 == 0) &&
    (x2y3 == 1 || x2y3 == 0) &&
    (x3y3 == 1 || x3y3 == 0) &&
    (x4y3 == 1 || x4y3 == 0) &&
    (x5y3 == 1 || x5y3 == 0) &&
    (x5y2 == 1 || x5y2 == 0) &&
    (x5y1 == 1 || x5y1 == 0) 
     }
  , {x1y1, x1y2, x1y3, x2y3, x3y3, x4y3, x5y3, x5y2, x5y1}
  ]]

The output is:

x1y3 == 1 && x2y3 == 1 && x3y3 == 0 && 
x4y3 == 0 && x5y1 == 1 && x5y2 == 1 && 
x5y3 == 0 && 
((x1y1 == 0 && x1y2 == 1) || (x1y1 == 1 && x1y2 == 0))

This means that \(x_1y_3, x_2y_3, x_5y_1\) and \(x_5y_2\) cells have a mine while \(x_3y_3, x_4y_3\) and \(x_5y_3\) cells don't.
Whether or not the \(x_1y_1\) and \(x_1y_2\) cells have a mine is undetermined, but we know that if \(x_1y_1\) has a mine, \(x_1y_2\) doesn't and vice-versa.

What we do at this moment is to fill the board with the results we are 100% sure about. If we do so we get the following board:

As you can see, when we looked at the beginning board we couldn't immediately say where were the mines. It was not obvious. But using algebra gave us some help.
Now you just have to repeat this process until the board is solved.
Note that not every minesweeper puzzles have a determinable solution: which means sometimes every variable will be undetermined when you solve the system.
Also, in Microsoft minesweeper, there is a counter for how many mines are left not flagged at each moment. This could be helpful in near end game situations where you can't find out any cell value to be determined. However, i didn't include this data in the resolution I purposed for matters of simplicity. If you are curious about how to do it, post a comment.