CODEWITHSUNDEEP
javascriptalgorithmpuzzle
Адександр Мороз
Адександр Мороз

Reputation: 29

Is there fast algorithm to solve a puzzle

I have a puzzle to build some shape from pieces. I enumerate all places in the shape with numbers, then for each piece a compose a set of set of numbers, that this piece can take. So I have set A of set B of set C of natural numbers, for example,

[
  [ [1,3,5], [2,4,8], [1,5,9] ],
  [ [1,2,3,9], [3,5,19], [10,12,33], [14] ],
  ...
  [22,46,50], [13,15,33,44,57], ..., [7,17]
]

I need to select one set C from each set B so, that all numbers were unique and it will be solution for puzzle, for example,

[1,3,5] from first set,
[10,12,33] from second and so on,
where [1,3,5,10,12,33,..] <== contains unique numbers

Is there any algorithm (faster then brute force) to solve this task?

Upvotes: 1

Views: 319

Answers (1)

user555045
user555045

Reputation: 64913

It's NP-complete, as you might have expected. That doesn't mean it's hopeless (brute force sets a very low bar to beat), see below for an approach, it does mean that it is not expected that an algorithm exists that does it in polynomial time in the worst case. So you won't get a nice answer such as "do a bipartite matching" or something like that.

Anyway, it's NP-complete, in two steps:

It's in NP

Fairly obvious, given a particular selection of "for each B, which set C is selected" (polynomial size) it's easy (polynomial time) to verify that a set C is picked from every B and that there is no overlap.

It's NP-hard

There are going to be lots of ways to do it, but here's one example: reduce graph coloring to this problem.

For every vertex of the graph, make a set B. For every color k for every vertex i, make a set C(i,k) in B(i).

The idea is, if a particular set C(i,k) is picked in a set B(i), then that chooses the color k for vertex i, and we use the global "uniqueness" constraint to prevent an adjacent vertex from getting the same color. So:

In the set C(i,k) that corresponds to coloring B(i) with color k, add the number pairToInt(i, k). To the set C(j,k) that corresponds to coloring B(j) with k (j adjacent to i in the input graph), also add that number. This bans coloring both i and j (adjacent) with the same color, because those sets C contain the same number and cannot be simultaneously selected. It does not ban non-adjacent vertexes from having the same color. pairToInt could be the Cantor Pairing Function or something simpler, doesn't matter as long as unique pairs map to unique integers.

For example you could use a SAT formulation:

  • introduce a variable x[i] for every set C
  • for every set B, make a clause that forces at least one of the sets in B to be selected
  • for every pair of sets in C that share a number, make a clause that forces at most one of those sets to be selected

That's not too big, only quadratic size. By the way the solver might select multiple sets C for one B, but you can just discard the excess until only one C is selected per B. Discarding in that way wouldn't break the other constraints. This would be dangerous if there was a constraint that every number must be picked, but we don't have that constraint.

The question then is, is that faster than brute force? Practically it should be, for example a CDCL-based solver would quickly discover patterns of incompatible choices and avoid them in the future, and Boolean Constraint Propagation is used to quickly fill in the consequences of a decision rather than brute-forcing them too, so time is mostly spent on the hard "core" of a problem instance. Brute forcing would spend a lot of time on the easy parts as well.

Upvotes: 2

Related Questions