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!
Best Answer
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.)