Actually playable games based on graphs?

Question

In computer science lessons, we have recently got the task to program something using graphs. Due to my enthusiasm for computer games, i would really prefer to implement a concept for a game. The requirements for the project are:

• the underlying graph mustn't be necessarily planar and it would be better if it's not necessarily plain, too (so you can't simply implement tic-tac-toe for example)
• the underlying concept shouldn't be too hard to understand
• the game should be enjoyable to some extend
• it should be a one-player game

(but only the first requirement is really necessary)

So does anyone have an idea? I'm very grateful about any proposal!

Answer 1

Though I question the on-topicness of this question, how about 9 men's morris?

I love this game and used to play it all the time. It's also generalizable to $n$ men's morris on various sized boards which might be interesting.

Answer 2

The game of Sim is very playable and is pure graph theory. The board consists of six dots. Two players, Red and Blue, take turns; a player's turn consists of picking two points that are not already connected with a line, and connecting them with a line of that player's color. A player who completes a triangle of their own color loses.

A famous theorem of Ramsey theory states that the game of Sim cannot end in a tie; after 15 half-moves, the board is full and must contain a triangle of one player's color. (If the game is played on a board with only five dots, it can end in a tie.)

Answer 3

You asked for one-player games; here's one: Planarity. The game presents a planar graph, and the player's job is to find a planar embedding of the graph by rearranging its vertices.

Answer 4

Maybe not what you are searching, but very interesting: the game Sprouts.

The game starts by drawing three dots.
...
The first player has a turn by joining two of the dots and marking a new dot in the middle of the line. Or the line may start and end on the same dot.
...
When drawing a line, it cannot cross another line. (This is important to remember!) A dot cannot have more than three lines branching to or from it.
...

Answer 5

Here is an interesting game, note that you can replace the hexagon with any other $n$-gon, you just need to keep two nodes on each of its edges with only one edge being connected to each node inside 1 $n$-gon. You can also make other generalizations etc.

http://entanglement.gopherwoodstudios.com/en-US-index.html