solution scoring

solution scoring

I and (apparently) one other contestant are discovering that it is very easy for a problem to flip between solvable in a short time to unsolvable in hours, based on minor adjustments to algorithms. See some of the samples I've uploaded. Because of that it has been hard to find cases suitable for multi-thread optimization -- they seem to either solve very quickly (in which case multi-core doesn't matter), or they solve so slowly that nobody wants to wait for the result, even with multi-core.Due to this effect, what do the judges anticipate doing when a solver does not come back for a very long time?

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

Same feeling. Find all the solutions. More reasonable


Taking this more generally, I feel that the NP complete problems are a poor choice for these challenges if the entire search tree is not searched (i.e. finding a single solution rather than a count of all solutions.) Then it's just about how lucky you are in choosing a start in the search, or smart pruning of the search space. Consequently, multi-threading does little to improve solution times compared to choosing a smart search strategy. However, if the challenge is to count all possible solutions, then "luck" doesn't come into it, and multi-threading and be used more to gain a performance advantage.

In the Masyu puzzle case, the NP-completeness of the problem is a minor factor. Even the "np complete" sample that I uploaded does not have that many configurations that absolutely must be tested (I think that the equivalent NP-complete Binary satisfiability problem only has a few terms). Pruning the search space and having good heuristics is what really matters when finding a solution. It is also easy to construct samples that have an exponential number of solutions, so outputting all of them is strictly infeasible even in cases where finding a solution is easy. However, I do find that the scalability ascpect of the problem is lacking for the reasons you state, and finding all solutions would actually test that (except that for some problems you can prove by constraint logic that there is only one solution, and no searching is needed).

It is definitely true that a really well built sequential solver could beat the pants off my parallel solver, no matter how good the worksharing is.It seems to me that we just have to not worry about the competition aspect. You work-sharing multi-threading cleverness probably won't win you the day in this comp, but I think that just thinking about writing NP-complete for multi-core problems seems really important. Even better, it's so much fun :)TLDR: Maybe it's not a great challenge for a threading comp - but it's still pretty awesome.

I agree, its been a really fun problem to work on. My solver has undergone multiple iterations as I've explored different problems and found ways for my solver to get confused and chase its tail forever.

Leave a Comment

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