Code and Reports

Code and Reports

I have put my solver up on Git Hub. I am about to addd my report there plus a jar and the shell script that runs it on the MTL computers. You can find it here would love to read the reports from other people for the first challenge.I wouldn't expect it, but if anyone actually wants to read the source I will happily go through and tidy it up with comments etc. :)Plus, if anyone wants to chat about Masyu puzzles or computing in general I would be very happy to hear from other people. Anyone who does this sort of thing for kicks must be ok. My email address isfrancisstephensatgmail

7 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Thanks John. Yeah, a very interesting read. I wanted to use the shape representation you used, but I thought of it too late. I can say that the fact that a move on a square was really two moves caused me a lot of headaches - my early code was pushing moves on in very unintuitive ways and that cost me a lot of time. It sounds like you managed to include a lot of the constraints that I would have liked to have included too. Now I am feeling restless waiting for the results to come in.The work sharing approach I used has been used on a (fairly primitive) sat-solver, also on Github, that has been tested on a big Azul machine with 600 cores - it scales well for depth first search tasks.I had a look at your company, Datalever, looks like a very cool place to work.

DataLever is a fun place, and we solve some hard and practical problems in the data-integration and data-quality space. Much of the multi-core parallelism is about moving lots of records around a dataflow graph efficiently and scalably. We don't use a task-decomposition model (its not quite right for this; anyway, we started well before such things were common). We use C++ and ACE for cross-platform IPC, networking, multi-threading, etc in the servers, and C# in the clients. Which is kind of why I wanted to try this contest, to learn about TBB and get some task-decomposition experience.

The line-shape model along with aggressive constraint processing introduced its own set of complexities. The biggest issue was that constraints could put line segments pretty much anywhere, which made calculations around global state (getting boxed in, isolated sections, etc) much harder. Also moves had to be prepared to chase through existing line sections as moves were made, because you can make moves that join two separate segments. And of course the move stack itself gets more complex, because it has to store all of the implicit constraints that came along with a move, so they could be undone during backtracking. Fun time though, I wish I'd had another week to work through a couple more globally-unsolvable states, and also improve the goal-seeking path finder.

I know what you mean by "another week" it really felt like I had just gotten a good basis for real development when I submitted. There is an emormous range of possible tweaks to try out.

Here's my Source Code



Thanks for that. I read your report, translated by google. It is really interesting to see the variety of approaches taken. I am looking forward to the results.

Leave a Comment

Please sign in to add a comment. Not a member? Join today