Islands game and graph theory
I'm trying to recreate an electronic version of the game shown below:
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.
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
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.
If you have a degree-bound-0 vertex, then you can take this vertex and all incident edges out.
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.
Why don't you just construct a random spanning tree on a grid graph, then remove the edges?