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!
$\endgroup$ 25 Answers
$\begingroup$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.)
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$Here is an Android game I made inspired by Hamilton's Icosian game, where you must connect every node by visiting them only once. I used Mathematica to generate planar graphs that have only one solution, and then a custom software to turn the graph into a map by representing nodes as regions (or "villages") and edges as borders between regions.
The first few levels are pretty easy but it gets harder as you progress, although I unfortunately hit a limit on the number of "regions" you can fit inside a phone screen.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$Maybe not what you are searching, but very interesting: the game Sprouts.
The game starts by drawing three dots.$\endgroup$
...
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.
...
