Homo ludens
A while back, as a simple finger exercise in Java I wrote my own little Tetris variation Alphis.
(The game requires at least Java 2, so it probably won't run in plain
Internet Explorer, whose users might want to enter this decade and download Java 5
anyways.) When I taught the second Java course last summer, this game
was a perfect example to go through in the first lecture, since it uses
many things that were taught later in that course, such as
multithreaded programming, streams and advanced graphics.
In this game, the pieces consist of a single vertical block of letters. Instead of falling down, the user gets to place the piece in leisure by clicking on the column where he wants to place the piece. The user can also cyclically rotate the letters of the word with the middle button. Whenever words of English language appear (in either direction), these letters are highlighted and they disappear. The longer the word, the more points it yields, so that the points awarded grow exponentially with respect to the length of the word. Occasionally, the pieces rise with new random letters appearing below, and the game ends when the user can no longer place a piece anywhere in the field. The highest score that I have been able to achieve was about 3000 points.
Initially, I wrote the random piece generation code so that each letter was equally likely to be used. However, this leads to a lousy game in which the game field gets quickly filled with crap letters like Z and X. So it's better to weigh the individual letter probabilities so that they are more like English. This way, proper words often appear. It is surprisingly difficult to create long words: the longest word that I have ever been able to create was only six letters long. It's difficult to create longer words, since useful blocks of letters that could be used as a part of a long word tend to be words or parts of words that fit well to the surrounding letters and thus disappear before I get a chance to use them.
I also wrote a very simple Newtonian physics engine as an experiment, and then built a game Murray on top of it. In this game, the player indirectly controls the red ball so that at the times when the user presses the left button, a force affects the red ball to the direction of the cursor. The game field consists of balls and polygons, so that for each polygon, there is one ball of the same colour. The task of the game is to make each ball hit once the polygon with the same colour, and when all balls have done so, the game moves to the next level. Some of the balls are connected with springs which affect their movement. The fields are generated randomly, so some field may turn out to be unsolvable. This doesn't matter, since the user can freely move between fields. If the game is not entertaining enough by itself, putting challenges for the user doesn't really make it any better.
I also wrote a Sudoku Solver (needs Java 5) to be used as a demonstration program in the algorithm course. I am really crappy in solving Sudokus or any other types of puzzles with my brain, so I have to write computer programs to perform these tasks for me. The classic backtracking algorithm works well with Sudoku, but there is room for many optimizations of the search procedure to make the algorithm as fast as possible. With all Sudoku puzzles that I found and tried, the applet solved them as soon as I pressed the button. If anybody knows a really difficult Sudoku puzzle that makes my applet totally choke, I would be happy to see such a puzzle so that I could improve this applet.
In this game, the pieces consist of a single vertical block of letters. Instead of falling down, the user gets to place the piece in leisure by clicking on the column where he wants to place the piece. The user can also cyclically rotate the letters of the word with the middle button. Whenever words of English language appear (in either direction), these letters are highlighted and they disappear. The longer the word, the more points it yields, so that the points awarded grow exponentially with respect to the length of the word. Occasionally, the pieces rise with new random letters appearing below, and the game ends when the user can no longer place a piece anywhere in the field. The highest score that I have been able to achieve was about 3000 points.
Initially, I wrote the random piece generation code so that each letter was equally likely to be used. However, this leads to a lousy game in which the game field gets quickly filled with crap letters like Z and X. So it's better to weigh the individual letter probabilities so that they are more like English. This way, proper words often appear. It is surprisingly difficult to create long words: the longest word that I have ever been able to create was only six letters long. It's difficult to create longer words, since useful blocks of letters that could be used as a part of a long word tend to be words or parts of words that fit well to the surrounding letters and thus disappear before I get a chance to use them.
I also wrote a very simple Newtonian physics engine as an experiment, and then built a game Murray on top of it. In this game, the player indirectly controls the red ball so that at the times when the user presses the left button, a force affects the red ball to the direction of the cursor. The game field consists of balls and polygons, so that for each polygon, there is one ball of the same colour. The task of the game is to make each ball hit once the polygon with the same colour, and when all balls have done so, the game moves to the next level. Some of the balls are connected with springs which affect their movement. The fields are generated randomly, so some field may turn out to be unsolvable. This doesn't matter, since the user can freely move between fields. If the game is not entertaining enough by itself, putting challenges for the user doesn't really make it any better.
I also wrote a Sudoku Solver (needs Java 5) to be used as a demonstration program in the algorithm course. I am really crappy in solving Sudokus or any other types of puzzles with my brain, so I have to write computer programs to perform these tasks for me. The classic backtracking algorithm works well with Sudoku, but there is room for many optimizations of the search procedure to make the algorithm as fast as possible. With all Sudoku puzzles that I found and tried, the applet solved them as soon as I pressed the button. If anybody knows a really difficult Sudoku puzzle that makes my applet totally choke, I would be happy to see such a puzzle so that I could improve this applet.
Here's a 16x16 sudoku for you. It takes 45 seconds for my sudoku solver to solve it. The solver uses a combination of backtracking and heuristic pruning.
http://www.uta.fi/~sh65234/sudoku/problem.java
Posted by Simo | 3:42 PM
Thanks, I'll try it when I modify my solver to handle larger sudoku fields.
Posted by Ilkka | 5:54 PM
The sudoku solver chokes if the initial numbers are not correct. For example, try typing two 9's on the first row. It looks like there is no sanity check for the initial values.
Posted by Dyro | 2:55 AM