Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to recreate an electronic version of the game shown below: Islands

The game is basically a connected graph, with the number representing the compulsory degrees of each vertex. The player must connect the entire graph while also keeping track of the degrees of each vertex.

My aim is to generate the correct graph, so that there will definitely be a solution. My initial idea is to randomly generate an adjacency matrix and check if the matrix is Eulerian. Does such an algorithm/formula exist?

Another method would be to generate a connected graph, then simply count the degree of every vertex and present that to the user. But I'd prefer the first option of generating an Eulerian graph from the start.

Perhaps I am even overcomplicating it. I'd be happy to hear of any other ideas.

share|improve this question
4  
I think your approach misses the "no enclosed areas" condition. Thus you really should start with a random tree, not any random connected graph. Maybe the more interesting part is uniqueness, i.e. to check that no other tree solves the puzzle (any connected graph matching the degree condition must be a tree as well) –  Hagen von Eitzen Dec 26 '12 at 10:09
    
I agree it should be a tree, I did miss that part. I'm not too bothered about uniqueness, I will write the program in such a way that all correct solutions are accepted. –  janvdl Dec 26 '12 at 10:17

2 Answers 2

up vote 3 down vote accepted

Usually it is crucial for puzzles like that to have a unique solution. So I would advise to generate a random spanning tree, derive the problem instance and then check if this is the only solution.

I would start to simplify the graph first. Here are three rules which you can apply in any order repeatedly

  1. If you have that the degree-bound equals the degree of the vertex in the graph, then all the incident edges have to belong to the spanning tree. Hence you select these edges and remove the vertex. Then you subtract from the degree bound of the adjacent vertices 1.

  2. If you have a degree-bound-0 vertex, then you can take this vertex and all incident edges out.

  3. If you have that the degree-bound is larger then the degree of some vertex then there cant be a solution.

If you still have vertices left you should backtrack. I recommend to start with a vertex with small vertex degree in the remaining graph. Then try out all possibilities to select the incident edges, and see if you can continue with the rules 1-3. By this you can backtrack quite easily through all solutions. While backtracking, record the selected edges. You still have to check everytime you resolved all vertices, if the induced graph contains no cycles.

share|improve this answer

Why don't you just construct a random spanning tree on a grid graph, then remove the edges?

share|improve this answer
    
Great, that Generate algorithm becomes remarkably nice to implement with such a rectangular grid! –  Hagen von Eitzen Dec 26 '12 at 11:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.