New 2013 Madness: One Game A Month

   That's it. I caught the game jam bug.

   Not the acute, 48h, Ludum Dare variety. More like the chronic, one month strain.

   It all started with the story of a guy called @McFunkypants. In 2012 he set up as a personnal quest, among others, to code 12 games over 12 months. He succeeded and challenged everybody to do the same in 2013. So he set up the OneGameAMonth website, to provide a public platform to record progress. There are no prizes, mostly no rules, except the main one: write one game each month of 2013. A system of experience points (XP) has been tacked upon it, to gamify the making of games.

   And I signed up.

   What was I thinking? Oh yes, I know. I'm still trying to generate some external pressure to help me gather motivation and momentum. It worked fairly well for the two game jams I did this year (Liberated Pixel Cup and GitHub Game Off 2012). I think it's more because of the peer pressure of the group of people who joined me than because of the eyes of all other internauts. Real people made of blood and flesh that I see daily have more impact than virtual people made of bits and bytes. I don't know if it means I'm normal or if it means I'm old-fashioned.

The Plan

   So now I have to come up with a plan for 2013. Maybe not an extremely detailed overarching plan for all of 2013, but at least a sketch, a bunch of directions.

1. I need to get more disciplined if I want to achieve the goal. Build up a routine, probably, to avoid making excuses.
2. I'll revive and explore further the "tree-growing" concept that we abandoned for game-off-2012. It's already got its own GitHub repository and the proof-of-concept is live at http://slowfrog.github.com/branch-off/. I need to work on core game mechanics, to make sure they are viable. And I want to explore some rendering options. As a first step, I already added a drifting, procedurally generated cloud in the background.
3. In case I lack inspiration one month, I can expand on Domino Trail. There were several features that we had in mind at start and did not implement (edge-walls, cells with different speeds, new pieces with special behaviour).
4. I resorted to http://videogamena.me/ to help me generate ideas. It's really fun. It's less prescriptive than game idea generators, because it only produces a name. And that's the nice point: you have to put your imagination to work to devise a game that would fit the name. I've had very good runs of the generator and will only reveal one title that could be the hit of 2013: "French Bubblegum Castle." You've been warned. 

   Here I come, 2013!

Another season, another game programming contest

   Just when I thought I could relax, waiting for the results of the Liberated Pixel Cup (not really thinking about winning, but hoping at least to have a decent score), here comes GitHub with a context of its own: Game-Off 2012. One month to come up with a game that should be web-playable and loosely based on git concepts: branches, clones, forks, pushes and pulls. What was I supposed to do? Well, of course, participate.

   I thought about some concepts on my own. The first idea was to go all out on the theme, with an action platformer where you would run and jump on branches, pushing and pulling clones with forks. Nothing really original for gameplay. My second idea was to play the French touch by using French words that sound close to the theme: poule (chicken) for pull, phoque (seal, the animal) for fork, clown for clone. I did not venture further. I'm not sure I want to imagine what a game with clowns, chickens and seals would be. My third idea was to make a puzzle game. They are generally easier to make than real-time action games, and it's possible to end up with something acceptable, even without a real artist: you can always go the "abstract" way. The first puzzle idea was about a tree that you have to grow somehow, using actions like "fork" to add branches, "push" to bend them and cut to stop them growing. I even started a proof of concept, to see if it had any potential. Since GitHub required the game to be web-playable, I settled for HTML and JavaScript. Let's even say HTML5, for buzzword compliance, because it uses the fantastic <canvas> element.

Orphaned tree game concept

   At about that time, I asked for volunteers among my coworkers to help me. I met with two of them, and after our first brainstorming session, the tree growing concept was abandoned. We could not see clearly enough what the goal could be or how to make the game challenging. I thought the goal could be to fill a predefined shape with a set of available actions, but I was afraid all levels would end up being too easy to solve. Being short on time, we focused instead on a domino game, for which the goals and constraints were easier to imagine. In each level, you would have starting points, goals to reach and an assorted set of pieces to make a path from start to goal. Oh, and the board would use hexagons, not squares, to give it an original touch.

   At that point, there were three and a half weeks left. I had already set up the "infrastructure" (github repo, Google Group) so we started coding, slowly, on the low-level parts: how to handle hexagons and their coordinates, how to draw them, how to match a mouse position to an hexagon. Nothing technically hard. The only problem is that it is difficult for several people to start coding from scratch simultaneously. Even more so when the other guys are not so fluent with JavaScript. Anyway, I did most of the initial coding, and we had one formal work meeting every Tuesday to share ideas and build momentum for the next week. As you can see on the graph below, representing the number of commits for the last seven weeks, momentum took some time to build, but when we stopped, we had quite a lot.

Project commit history

   The idea we had, to be able to share a bit of the workload, was to make pieces and levels as independent and pluggable as possible. I refactored a big part of the code to allow that, and one of my coworker coded some of the missing pieces, the ones that fork the path. I also coded the basic UI allowing to select pieces and to put them on the board. From that, it was quite easy to make a basic level editor. The other guy was then able to completely rewrite the drawing code, replacing my ugly looking black and white rectangles that were supposed to be dominos, by a more abstract look that was more pleasant and easier to animate. We thought about making 3D models and realistic domino renderings in Blender, but had to ditch it, by lack of time and competency.

The last tutorial level

   One week before the deadline, we had all the low-level mechanics and pieces we needed, but we had not yet produced a single level, and the global look was not very engaging. That's what we focused on in that last sprint. I wrote nine entry level tutorials, with texts explaining all the mechanics and each one of us tried to design about seven levels to reach about thirty. We got exactly there: 30 levels + 1 level editor.
   We enrolled a few more coworkers for beta-testing and mobile platform testing. I coded some important stuff on the last two days (level locking and in-place rotation and delete) in response to our limited user tests. My team mates worked hard the very last days to find or draw pleasing images and icons, and the game was finally ready. 

   You can play it on GitHub. And you can browse the source also on GitHub.

   For those of you who like numbers (like me), the game contains 3.500 lines of JavaScript code (blank and comment lines excluded), which is about a third of my port of Desktop Dungeons. 

The glorious splash screen, committed during the last 24 hours

Lessons learned

   Doing a game jam is nice, doing it with other people is nicer still, at least in a small team. Different opinions can combine to produce things that would not have been possible alone. And being a small team, we could avoid the "design by committee" pitfalls.

    JavaScript is really cool for short prototype-y projects like this one. And apart from Opera that has poor canvas rendering performance, the game works very well on all desktop and mobile browsers.

    Doing HTML5 makes it easy to target mobile platforms, but their specificity regarding screen size and input methods must be taken into account to produce a good experience. We'll try to find hardware for tests sooner in the project next time. Hopefully, we'll win an iPad from GitHub, and the problem will be solved.

Chickenpix!

Long time, no post

I don't think anybody is really following this blog (except some of my most curious colleagues), but let's pretend for a second that I have an audience. I did not post anything for the last six months, mainly because I had nothing technical I considered worth sharing and I do not want this blog to become a diary of my breakfasts or other useless stuff. I does not mean I did nothing: just that the things I did were too small for me to talk about.

For instance, I picked up nurikabe. This is a puzzle game in the vein of sudoku, with rules that are, at first, a bit difficult to understand, but lead to an intersting way to waste one's time. There are parts that make it look like minesweeper (there are numbers that represent a count of something you have to find), others are more akin to the game of go (the black "stream" must be in one piece, so that you have to escape atari). It's nice to play "manually". And of course I wrote a solver, because that's what I do. But nothing exceptionnal to show: only a few heuristics bound with a brutish force search.

Game of nurikabe in progress

At one point, I tried to switch views, and wondered how the site I referenced above could generate all those puzzles. I probably did not spend enough time on that task, and have not come to a working model of how to do that. Nothing to show again.

I worked a bit on my other HTML5 game (a simple tower defense revolving around programmers and the SCRUM methodology, if you want to know). But I did not make enough progress to show it.

And then...

I spotted in the news that the OpenGameArt site was hosting an art & game programming contest during the summer, with open source and free software sponsors (the FSF, Mozilla, Creative Commons). I thought it would be interesting, and I asked a few colleagues if they wanted to participate, to help create team motivation. And so, during the last two months, I spent all my spare time working on that project. We started with a team of about eight people, but we ended up being only two to push any code. I think we did not really succeed in creating enough momentum, and the end result is not really a game, just a technical prototype of what the game could have been. It's called Chickenpix (hence the title of this post).

At first, since most potential coders were fluent in C++, we decided to choose that language over JavaScript. Then we looked for a portable and open source low-level libary that could fit our needs. We kept two of them, ClanLib and SFML. Why didn't we stick with only one? It would have been simpler, but my fellow coder worked on OSX and he could not make ClanLib work on his machine. And on the other side, I worked mainly on Linux in a VirtualBox VM, and SFML was awfully slow when rendering. I also wanted to make a Windows build, but with Visual Studio Express 2010, SFML was a nightmare to link, and I eventually gave up.

For the architecture, I wanted to experiment with the entity-component-system approach. Each game object (entity) is effectively nothing more than a container of components. Those components, in turn, are generally simple data structures containing state information. All the logic is then performed by the systems that are present. Any entity can contain any kind of components, and they can be added and removed dynamically.

The whole cast of characters

For instance, in chickenpix we have a dozen components, among which a Transform component holding the current position, a Mobile component for things that move, a Visual component for entities that need to be shown, and also Animated, Input, Audio, Camera, Scriptable, Collider. On the systems side, there is a Render system, that collects all entities with a Visual component, finds the Camera and displays everything accoding to their Transform. There is a Movement system that does the "physics" simulation, an Inputs system that gathers user input (keyboard and mouse) and calls contollers, a Scripting system that executes scripts.

Talking of scripting, we quickly evaluated the usual open-source possibilities for embedding: JavaScript with V8, lua with luajit and Python. V8 was rejected because we could not find a binary release, we could not make it build on Windows and we simply did not persevere. lua was deemed too "low-level" and unknown to almost all participants. I was all for Python and some other people knew it a little, but I had never embedded it. It ended up easy enough, once the reference count scheme was understood.

Technically, that's about all there is too say. And on the game design side, well... there was not really any time left for that.

Lessons learned

Working with other mildly motivated people, on a short schedule, in the middle of Summer is not the best way to build momentum. The human factor trumps the technical ones.

C++ is not as bad as I anticipated. Mind you, I already knew C++, but it had been a long time since I did anything more than a toy program with it. I was afraid of manual memory management and the associated problems. Lots of logging and some gdb sessions to pinpoint the cause of segfaults was enough to cure those.

Developing on the three main desktop platforms in parallel is not too hard, especially when each coder has a different preference and handles his platform himself. I have no other data point to really compare it to porting only after the first working version is done. I suspect there is a slight advantage with the multi-platform approach because the versions never have the possibility to diverge.

Supporting several low-level libraries was not too difficult and probably had a good effect on the architecture of the code. It forced us to think on a higher level and to provide adequate interfaces.

Entity-Component-System is interesting and has some good properties. But as all good things in life, you have to learn not to abuse it. Having the resource loading facility be a component of a fake entity seems like a hack, in retrospect. And having to switch between several modes of play led us to design transitions between distinct entity managers. I'm not sure it's the best way to do it.

We're not going to compete with Unity just yet.

Embedding Python for scripting is cool. The C API is easy enough to master and very well documented. No need to stress the benefit of scripting for games in general: it transforms part of the logic into "data" and data-driven programs are simply better (easier to test and reason about, no need to recompile for every change...)

Working in a virtual machine is kind of nice (you can switch physical machines by just moving the image) but there are still limitations when developing a game. Graphics hardware acceleration does not seem to work out of the box just yet.

Google webfonts is a great resource for free (as in freedom) fonts, not limited to the web.

github provides excellent tools for collaboration, that I had not yet tried when working alone: wiki, web pages, issue list, downloads. The code statistics and graphs are nice, but they give strange results sometimes (we did not code a single line of Objective-C!).

To all other LPC participants: good luck! Chickenpix has been a nice experience, but the final game will not be an obstacle on your way to victory :)

Hexiom, constraints and libraries

After my own forays into constraints programming, I received a comment by Pierre Schaus who solved the problem with his own Scala CP library. The solution is very elegant, and once the boilerplate code is removed (file parsing...), is very short and to the point. The constraints are expressed very clearly using a kind of DSL that is made possible by Scala's flexible syntax. Really enlightening!

This prodded me into looking at what were the available options in my preferred languages. I have learned a lot (but still have a long way to go) and I found two open-source libraries that are very powerful and quite performant, one for Java and the other for C++.

JaCoP: Java Constraint Programming

JaCoP, as its name implies, is a library for constraint programming in Java. It's been developed by two people from academia for more than ten years now. It's flexible, well documented and it ships with a wealth of good examples that are really helpful to get started.

The pros

Java is a big pro for me. Also, the way boolean variables are defined is handy: they are integer variables whose values are restricted to 0 and 1, so they can be used in arithmetic constraints without conversion. In Hexiom, to count the number of actual neighbors of a cell, I only had to sum the boolean variable telling me if a tile was present on each side. And finally, I liked the way constraints can be composited from some primitive constraints. For instance, I found the IfThenElse constraint very helpful and intuitive to use.

The cons

Composition of constraints being so cool, I was a bit disappointed to realize that only primitive constraints could be used as building blocks. The algorithm for the propagation of constraints has probably very good reasons for that, but still. For instance, seeing that X+Y=Z (XplusYeqZ) was a primitive constraint, I hoped that the Sum could also be a primitive, but it's not. That's not too bad, because often the solution only requires to decompose the constraint and introduce one or a few auxiliary variables. You only have to learn this habit.

The result

The code can be found in: https://github.com/slowfrog/hexiom/blob/master/src/com/slowfrog/hexiom/Main3.java

It uses the same constraints as the one from Pierre Schaus, even though the way they are expressed is a bit less elegant:

• the variables to resolve represent cells and the values represent either a tile (0 to 6) or the empty value (7 here)
• auxiliary boolean variables are used to model filled or empty cells
• a GCC (Global Cardinality Constraint) ensures that the correct tiles are used
• a local counting constraint is created for each cell, combined with a condition: if the cell is empty, its value is 7, if it's not empty, its value must be the count of filled neighboring cells

The code performs pretty well and solves all 40 levels in less that a minute. In fact, it solves 39 levels almost instantly, and the remaining one (level 38) in about a minute. However, I had to tweak the branching choice algorithm to get that result. As for my own constraint solver, the best result is obtained when solving variables in row-scan order, and choosing the most discriminating values first. Those values are 0 and 6, which impose respectively that all neighbors be empty or filled. The empty  value must be considered last. The good point is that JaCoP makes it really easy to define that strategy by just listing all values in the required order.

Gecode

Gecode is a C++ library that has been in development for a bit more than five years. It's also very flexible and quite well documented. Being C++, it's also quite easier to shoot oneself in the foot with it, but I guess that's to be expected. It also comes with a pre-compiled solver that accepts the flatzinc syntax as input (but I am still evaluating that part). And the library has won constraint processing contests several years in a row.

The pros

The performance of the program is excellent, with the right tweaks (same as always: the branching heuristics). One advertised advantage is that Gecode supports parallelism. I did not try it, but if it works, it's nice. So it's a virtual pro for me.

The cons

Compared to JaCoP, the variables and constraints seem more primitive and sometime more difficult to handle. Boolean variables cannot be used in arithmetic constraints: auxiliary integer constraints must be created. The difference between variables and arguments is not yet clear to me but seems to revolve around memory allocation. And I met several segfaults before the program ran successfully, because some functions allow nonsensical arguments. Maybe they could be checked better and meaningful exceptions could be raised. There is no obvious constraint composition mechanism, and the branching strategy seems less flexible. To implement the same one as with JaCoP, I had to change the empty value from 7 to -1, to make sure the values were tried in descending order starting at 6. In that case, zero is treated almost last, but it's not too problematic, because it does not appear in a lot of levels.

The result

The code can be found in: https://github.com/slowfrog/hexiom/tree/master/cpp

I have only tested it on Windows 7, with VC++ 10 express and Gecode 32bit.

It uses the same constraints as before, with a few more auxiliary variables and constraints to accommodate the library.

As already said, performance is awesome: all 40 levels are solved in less than half a second, including the dreaded level 38. I can officially call that fast!

Conclusions

Both libraries are very good! Even for a beginner like me, it's possible to get impressive results with a few hours of work. In the future, I might try Gecode standalone solver, to get the performance without the C++ troubles. I'll see if I can find an equivalent Python library. 

Overall, programming with constraints is fun, contrary to what the term might suggest.

Sikuli plays Hexiom for me

[Update: with some tweaking, my script sometimes succeeds with size-6, see at the end]

Yeah! Here is one of the first successful automatic runs of my Hexiom-playing bot. This is the combination of the solver I wrote about recently, and a bot coded with Sikuli.

Sikuli itself is a combination of OpenCV for the back-end, screen vision part, a Java middle layer and a scripting engine using Python as its language. It comes with an IDE that is quite easy to learn too.

What's great

The scripting part of Sikuli being Jython (Python implemented on top of the JVM) is great. It allows to code quickly and to fall back to Java for more preformance-sensitive parts. In my case, all the screen reading and playing logic is implemented in pure Python, but the problems are handed to Java for resolution.

OpenCV itself is great and fast enough.

And as previously said, the IDE is easy to learn and loaded with helpful tools like the screen capture utility and above all the pattern testing screen. It is invaluable to tweak the parameters of image matching, because small patterns like the digits of Hexiom can sometime lead to misses or false positives.

What's not so great

Sikuli, do no seem to offer a non-rectangular matching function. There's an open request for that on Launchpad, but from my quick investigation, it might be an OpenCV limitation. The only workaround is to match the biggest rectangular area that can fit in the preferred non-rectangular pattern. That is quite annoying: first, in Hexiom's case, all the patterns I'd like to use are hexagonal and second, using a smaller patterns leads to worse detection. After some tweaking, I succeeded in making the bot work every time on a size-4 puzzle, but it's not yet working on a size-6 one, because the board reading procedure making too many mistakes.

Wanna try?

Following these steps, you should be able to run the bot:

• Install Java, Sikuli and Firefox
• Fetch my code from github
• Compile java sources (in src/main/java to build/main/classes) or use Eclipse
• Open a Firefox window
• Set JAVA_HOME and SIKULI_HOME environment variables in a terminal
• Run ./autorun.sh 4 to solve a size-4 puzzle

You can also try with 6 instead of 4, but the results will probably be disappointing. Don't try 3 or 5: I haven't captured the appropriate digits yet.

Breaking news!

Sometimes, it works with size-6.

Daniel Hartmeier on his site with a somewhat different approach also succeeded, with a fully functional C program, see: http://www.benzedrine.cx/hexiom.html

Solving Hexiom using constraints

After my first try using brute force search to solve the Hexiom puzzler, and following recommandations I received in comments, I switched to an approach using constraint solving principles. It's not yet finished (I can still think of new constraints to add), but it's already working more or less as efficiently as the search version. I will try to highlight my findings in this post.

Search algorithm

My search algorithm was quite simple:

1. choose an empty cell
2. look for all tiles that can possible fit and try each one in turn
3. decide if the resulting position is solved, still open, or impossible
4. if still open, continue at step 1.

That being said, the latest implementation already took the current position into account in step 2. and 3. For instance, when looking for possible tiles, I only tried tiles with available numbers (obviously), and in a range of values that would still be correct considering surrounding values. That last element is already a kind of constraint application, albeit a simple one.
The third step is quite powerful too, in deciding whether a position is impossible to solve. It also computes possible values and detects mismatches. It can prune out a good deal of possiblities by finding violated constraints.

Constraint solving algorithm

The algorithm is, in fact, an hybrid between constraint solving and search.

1. When reading the input file, each cell is filled with the list of possible tiles, depending on available numbers, number of neighboring cells and locked tiles
2. A set of constraints is used to remove possibilities from cells. This step is repeated until nothing moves any longer.
3. Then we fall back on search, as before:
4. choose a cell
5. find all possible tiles and try each one in turn
6. decide if the resulting position is solved, still open, or impossible
7. if still open, repeat a step 2.

The tricky parts are number 2. and number 4.

Regarding constraints (step 2.), some are easy to find, some require a bit more work. I currently use three constraints, but I have thought of some more. The first constraint I use is the same as was implemented in the search algorithm: remove values that are outside the range of possible neighbors. For instance on the following figure, black cells have not been solved yet and we are trying to find which values are still possible in the blue cell. The minimum value is two, because we already have two neighbors. The maximum value is five, because we already have one empty cell as neighbor and the other ones are either filled or could be filled.

The second and the third constraints are mostly like the ones used in sudoku: when all tiles of a current value have been used, remove that possibility from all other cells, and when the number of cells that can host a given value is exactly the same as the number of available tiles with that value, fill all the cells with that value.

Step 4. is where heuristic is important: I have to decide which cell to try first and in which order to try the possible tiles. I have implemented four strategies to choose the next cell. One finds the cell with the fewest choices, the second finds the cell with the most choices, the third finds the cell with the highest possible value and the last just scans cells linearly, from top to bottom (like the search algorithm).

Results

The current results are good but not perfect. On the one hand, with the good heuristic, I can now solve level 40 in under a second and level 38 in two hours, whereas they completely resisted the search algorithm. On the other hand, solving the 38 other easy levels is a little slower than with the search. The code is available as usual on github. The java version could probably do with some low level optimization, like minimizing the number of instanciated objects.

Among heuristics, the one that chooses cells linearly does globally better than others. I does not fit my immediate intuition. I was inclined to choose cells with the least choices, thinking I would get better chances. It seems intuition is not always the friend of science.


What's next

This puzzle is a suprisingly rich field of exploration. I have a few more directions to go.

The first is expanding the set of constraints. I'm thinking of one constraint that could help remove the "empty" possibility from cells, when it's mandatory to fill remaining cells with tiles in order to reach a given count. Another one, or the same in reverse, could force empty cells when the correct number of neighbors is already present.

The second is around heuristics. What bothers me is that several of the ones I have implemented are perfect in some situation and awful in others. I can try to find new ones. Or I can try to take advantage of multiple cores by running several solvers in parallel, with different heuristics, and hope that one of them finishes quickly.

The third is another approach to the problem. Only choosing which cells to leave empty is sufficient to determine the complete board. Then it's only a question of matching the resulting board with the set of available tiles to see if it works. I'll describe that approach later, but I'm not sure it can lead to a workable solver. I'm afraid I won't be able to prune out branches as effectively.

The fourth is about automation. If you remember, my goal was to get the 60 Kongergate points granted for solving a random size-6 board in less than three minutes. To reach that goal, I have started using http://sikuli.org/ to play for me. It's not yet done, but it can almost read a size-4 board. After that, it will only need to launch the solver, read the results, and move the tiles accordingly. Should be fun to watch...


Credits

Thanks to fellow redditor julesjacob who described the general principles of constraint propagation that I implemented here and gave invaluable advice and pointers to good resources. And also to leonardo_m who piqued my curiosity for the D language by porting the Java version of the search algorithm.

You can also comment on reddit. 

Solving Hexiom (perhaps you can help)

Recently, when killing time on Kongregate and looking for achievements to boost my level, I discovered Hexiom, a puzzle game by a guy called Moonkey. As all good puzzlers, this one features a very small set of rules and gives birth to a large range of problems, with varying degrees of difficulty. The game comes with forty pre-defined levels and a "random-level" feature. To obtain 60 points on Kongregate, you need to beat the "impossible" challenge: complete a random level of size six in less than three minutes. Well, that might not be impossible, but it's darn tough. So my immediate thought was: "Ok, let's just write a solver for this thing, and pocket the 60 points!" But as of today, I still don't have those points.

The rules

So, what exactly are the rules of this game? As you can see, you have a board of hexagonal 'squares' (I call them cells), and you have hexagonal tiles in some of those cells. The tiles have a number on them, ranging from zero to six. They also have a color, but this one is changing. It's not a characteristic of the tile, as I will explain shortly. The goal is to put all tiles in cells such that each tile has a number of neighbors that exactly matches the number on the tile, as you can see below.

The number on the tile must match the number of neighbors

The color of each tile changes, just to give you a hint about its current status. If it's yellow, the number of neighbors is correct. If green, the tile does not have enough neighbors, if red, it has too many of them. A solved level is, therefore, filled with yellow tiles.

In some level, there are additional constraints. Some cells might be simply unavailable: they appear completely flat. Some other cells might have a tile already locked in, with grey 'claws'.

And that's all! You can move any free tiles to any free cell, until you come up with a correct combination.

Modeling the problem

I first defined some structures for the puzzle and a way to describe the levels in text files and to read them. A level is:

• a board containing cells
• a list of tiles (just the count of tiles for each possible number)
• a set of fixed tiles, if any.

The board is initially built just knowing its size. In fact in my model, all cells are created, even those where no tile can be put. The "is neighbor of" relation is precomputed to speed up the search.
The list of tiles is filled from all the tiles present on the board at startup. I just count the number of tiles for each possible value, because tiles don't have individual identity. I have also added a special value to mean "no number." Each cell that has no tile on it at startup counts as one "no number" tile. That way, when doing the search, it's always possible to chose a tile to fill a cell, even though it's not a real visible tile.
The set of fixed tiles is simply modeled as a partial solution: some of the tiles already have a destination. Something I noticed is that unavailable cells can simply be modeled as cells filled with a "no number" tile. Since there is already a tile in the cell, it's impossible to put another one: the cell is really unavailable. And since the tile is a "no number", it does not impose any constraint on neighboring cells. It's nice that it fits in the general model, without needing a special case: it makes the algorithm simpler.

The current solution

My current solver is a simple "search and backtrack". I examine each cell in turn, look for all possible tiles that could fit (determining what is the current minimum and maximum value possible), try them all, one after the other, and do the same on the next cell, if the current position is still acceptable.
At first, I programed in Python, for the ease of iterative testing. It was enough for the first batch of levels, but it quickly became too long. I did some micro-optimizations first: changing some data structures, and some loops. It went a little faster. I tried using the excellent PyPy instead of the standard CPython: it cut the runtime by about two.
The next not-so-logical step was to port the algorithm to Java. The performance got somewhat better and I could solve a few more levels. After profiling, I realized that a lot of time was spent creating and deleting short-lived objects, and using HashMaps. So I converted most HashMaps to arrays and found ways to drastically reduce object management. Another good speed gain.

And then I did what I should have done from the start: focus on improving the algorithm itself! The main bottleneck was the function that tested if a working position was solved or not. I changed it to return a status telling if the position was solved, still open, or impossible because of some failed constraint. That small change made it possible to prune out some search branches really early and solve all but two of the forty levels in no time. The current Java program solves 38 levels in about 3.5 seconds on my machine. After backporting that change to the Python code and when run with PyPy, it takes 46 seconds to solve the same levels.



The current limitations

But still, level 38 and level 40 resist the brutish-force search. So I ported the code again, to C this time. Since the Java code had already been mostly 'de-objectized', it was quite an easy translation. But the result is disappointing. Compiled with full optimization, either with Cygwin-GCC or with Visual C++ 2010 Express, the runtime is about the same as the Java version. It's even a bit slower, actually: 4.7 seconds vs 3.5 for Java.

Another limitation, if I were to try to grab the 60 points, is that all my solvers need a text file as input, and currently, typing the data for a size-6 level already takes a good part of the available three minutes. And even if the solver was instantaneous, I would still have to read the result and move all the tiles manually to their destination. If I really want those 60 points, I will have to resort to my old game-solving tricks: read the screen, solve the problem, and automate the displacement of tiles by simulating mouse events.


Where you can help

All my code is freely available on github. If you find a flaw in my algorithm, a problem with my code or think of something different that might run faster, just tell me.


Comments available also on reddit.