1

I have a set of puzzle challenges for a prototype jigsaw puzzle kit, similar to commercial products offered by Thinkfun and Popular Playthings. I have a candidate list of 300 puzzle challenges and would like to select 40 of them. For each challenge, I have a numerical value that represents the challenge's difficulty, another value that represents the challenge's difficulty after one hint is given, and a third value that represents the challenge's difficulty after a second hint is given.

When I present the puzzles ordered by difficulty, ideally the puzzles should also still have the same relative difficulty after a hint is given. For example, a hard puzzle with one hint should not be easier than an easy puzzle with one hint. If I can select 40 puzzles with that property, then I have the advantage that I can say "for younger children, give two hints for each puzzle" and not have to re-order the puzzle numbers.

I don't really need all subsets of 40 that fit my criteria, just one good one. If I had a list of all subsets, though, I would be able to choose one using more desiderata. For example, I would find one that best clusters into four groups of 10, and then label the challenges "easy", "medium", "hard", and "expert".

I would like to find all subsets of 40 of the points so that no matter which dimension I sort the subset on, the ordering is the same.

In other words, find a subset { P0, P1, P2, ... P39 } so that whenever A < B, X[PA] < X[PB], Y[PA] < Y[PB], and Z[PA] < Z[PB].

I tried a stupid recursive greedy algorithm and it is way too slow.

0

1 Answer 1

3

I eventually got the answer I wanted by a smarter dynamic programming approach.

The insight was to realize that although the nature of my problem didn't allow for a total ordering of all the elements, it did allow for a partial ordering of all the elements. The challenge, then, was to calculate the coverings in that partial order. To do that, I used the following algorithm.

for each Point in (all points sorted increasingly by dimension X)
   let Coverings[Point] = empty set
   let Lowerset[Point] = empty set
   let Candidates = {all previous points}
   for each PrevPoint in (all previous points sorted decreasingly by dimension X) 
      if (PrevPoint in Candidates and PrevPoint < Point)
         add PrevPoint to Coverings[Point]
       let Lowerset[Point] = union(Lowerset[Point], Lowerset[PrevPoint], PrevPoint)
         let Candidates = intersection(Candidates, inverse(Lowerset[PrevPoint]))
     endif
    end for
end for

Having the lines about Candidates isn't strictly necessary, but it makes the code a bit more efficient by not having to look through the same nodes over and over.

Once I had the set of all coverings, I was then able to send it to Graphviz dot to generate a Hasse diagram for my set.

And by looking at my Hasse diagram, I was quickly able to tell that the diameter of my graph was 40, which is just barely enough to do what I want to do.

P.S. I added a bit more of my code to keep track of the "depth" in which the node appears on the Hasse diagram. With that I was able to generate a simpler diagram that removed all coverings that jump a generation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.