Sunday, March 21, 2010

Painting by Numbers (2)

As a follow up on Painting by numbers here is a big one:

There is also one I cannot solve quickly (may be an error in reproducing the input on my side):

To make sure we are hitting the limits of MIP solver technology here and this is not due to some transcription error in the input data I should try this data with some other solver, e.g. a constraint programming system. (I did a simple check on the input: the count of the cells covered by horizontal clusters must be the same as the count of the cells covered by the vertical clusters).

1 comment:

  1. The original puzzle (I'm guessing it is #65 from webpbn) is fairly easy to solve with CP, so I'd guess that there is probably some error in the transcription. For reference, the statistics for finding all solutions with Gecode were:
    runtime: 0.022 (22.817000 ms)
    solutions: 1
    propagations: 1931
    nodes: 35
    failures: 17
    peak depth: 9
    peak memory: 839 KB

    If you haven't seen it, I'd reccomend you try to use the export-page on webpbn: