Wednesday September 21, 2005 Jummikub
In the spirit of this company I decided that I would do some more sharing. This time, it is about a project for which I think I no longer have the sources: my home CVS server crashed, and I can't find a backup. (The good thing about that is that it also saves me from a couple embarrassing moments when you would take the opportunity to look at the code.:^0
The live demo is running here.
History
This project started when I was about 15. I'm aware of the fact that it sounds a little pathetic (...), but at that time I was obsessed by the fact that it should be possible to have an algorithmic solution for Rummikub problems. I remember locking myself in my room for the entire afternoon, working on it from different angles and trying to get my MSX computer to come up with a solution. But I couldn't figure it out.
Until a couple of years later. I was doing an internship at the University, and working on a class of problems that we tried to solve using mixed integer programming techniques. I remember that - on a sunny autumn afternoon - I sat in the basement of the building, and it suddenly hit me that I could use the same technique to solve my Rummikub case. Eureka! That night, I wrote the mathematical model down on a piece of paper, with the intent to turn it into a piece of software somewhere soon.
It never a happened. During the years that followed, I repeatedly lost and retrieved this piece of paper, but never found the time to work on it. Six years later, when I returned from my holiday, I finally decided that I would give it a try and program it in Java. Four years have now gone by after I deployed the bits to my server at http://www.agilejava.com/rummikub/.
What does it do?
If you know Rummikub, then you know that it is basically just a combinatorial problem. There are 106 tiles, in which every tile combines a certain number (1-13) with a certain color (red,blue,black,yellow). These tiles must be combined in color sets or number sequences. And the general goal is to - well - get rid of your own tiles as fast as possible. You can reshuffle the entire collection of sets and sequences produced by others to get rid of your own, and there are also a couple of Jokers that can be a substitute for any tile you need.
The picture above shows you the opening screen of the webapp. It's just a table, allowing you to select the number of tiles that you want to be part of the solution. Apart from that, it allows you to choose between two possible strategies (this is up to your preferences). If you hit the only button on this screen, it will try to combine the choosen tiles into the optimal collection of sets and sequences, as you can see below.
If you change the parameters, for example by adding two jokers, then the solution is completely different, as you can see below.
How does it work?
I already alluded to the fact that this has something to do with mixed integer programming, so - well, that's basically how it works. I will see if I can dig up the mathematical model somewhere and post that here as well. But basically, every request coming from the first screen will be turned into MIP model. The servlet will then pass this model to a Java based MIP solver (downloaded from sourceforge). The solver returns the optimal solution, and the servlet translates this optimal solution back to a series of sets and sequences.
Where can I get it?
You can download the war file here.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.