Planned SA tutorial takes forever to finish, so I decided to write a short post about the problem that I solved yesterday, while looking through past tasks from Deadline24 contest. The qualifications for this contest are very similar to Challenge24 and IPSC – they only give you inputs and they only want your outputs in return.
One task looked particularly interesting – it’s a direct adaption of something that is known as a dissection puzzle and it’s a type of diagram puzzle you can encounter during the WPC. The rules are very simple, you are given a shape on a grid, and your task is to divide (dissect) it into few smaller ones in such way, that each one of them looks the same. Usually rotations are allowed, but reflections are not. The ugly image on the left, shows an example of a solved puzzle. In this particular problem, the size of those small shapes is given. If you want to read the full problem statement you can find it here, but you don’t really need any more information.
If you have no slightest clue how to solve such problem, then let me assure you that everything is fine with you, since as far as I know (although there’s a small chance that I’m wrong) everyone solved this by hand during the contest.
This post will show you how to solve it in a very simple (conceptually), yet a bit unconventional way.
Now it’s a good time to see the inputs, here you can download the whole input set. Each of the ten tests contains a few diagrams. While some of them are rather easy (or even trivial), many of them are not. In few cases it’s easy to spot the shape, but dissecting everything and producing solution file is a very tedious process. And as problem solvers, we don’t like tedious stuff ;)
Problem Solving at its Finest
My favorite type of problems are those where it’s very hard to create an algorithm that will outperform skills of an average human. In this particular problem, we can combine the both advantages of those two worlds – ingenious human mind with machine perfection.
First let’s notice that if the shape is fixed, our problem is reduced to NP-complete problem known as exact cover, which in turn can be effectively solved with LP (Linear Programming). LP may sound scary if you have never used it, but formulating problems as LP problems is usually rather easy (assuming it’s possible) and it has quite many uses. The most important part is that, you don’t have to waste countless hours on producing clever heuristics. Instead, you just outsource your complex logic to an already highly-optimized LP solver. There’s no shame in being effective :)
So my idea was as follows – I’m trying to guess the correct shape, usually by starting with something smaller than the required size. If LP solver is able to find at least N shapes (where N is required number of shapes), I’m trying to extend the shape until it has the required size and matches the whole grid. I can also use unmatched cells as hints. If it’s less than N, then I’m trying to find a different starting shape.
Originally I started with inputting shape through text file, but it quickly turned out that it was a painful process, so I decided to build a graphic interface around my solver. Once you have a bit of experience with any visualization tool, adding such functionality is usually the matter of minutes.
Overall, I believe creating whole program took me around 60-80 minutes, while being half-asleep (I started coding at 2am), so I’d say it went pretty fast. But I already had some experience with LP solvers, so I didn’t have to spent 80% of my time googling the documentation.
The source code is available here. In order to compile it, you need CImg.h library (this is very simple to install since it’s just a single header file) and glpk library (it’s available under cygwin and it’s a pretty standard lib on most linux installations). In order to compile it, you need to add -lglpk for LP lib, and -lgdi32 or -lpthread -lX11 for CImg.h, depending on your platform. If you have problems, this might help you – there’s a “How to compile?” section at the bottom.
Running is pretty simple – first argument is a test number (from 1 to 10), and second describes the diagram (indexed from 0). Just make sure to run it in the same folder as the inputs. In order to select the shape, just click on the files. Q quits, N clears the current solution, C clears the current solution and shape and finally R runs the LP solver with current shape and shows the solution (and as a bonus, it also prints the number of shapes found and the ascii solution required by problem statement).
Main issue is that my call to LP solver is blocking – in order to stop the solver, you have to kill the program. This is very likely to happen when you choose a small shape on a big grid. It could be solved with a 5-minute fix, since glpk allows to add callbacks, but I thought it’s already good enough to solve all of the given inputs.
Using this program I was able to generate solutions to all diagrams (except the first one in the last test – that thing is pretty tough) in something between 10 to 15 minutes.
I wanted to show you 2 things: even in classic optimization problems, it’s often a good idea to use existing tools instead of always building your solution from scratch, and the second thing is that sometimes it’s easier to solve some subproblems by hand instead of automating your whole solution.
And yes, SA tutorial is on the way – my goal is to finish it before the first qualification round for TCO :)