1
$\begingroup$

Say, given a $4\times 4$ grid with black and white dots on vertices. Each dot can form one (and only one) bond with a nearest dot of opposite color. Suppose every dot is guaranteed to find its other part. For one set of dot arrangement there can be many valid bond configurations. Question: an efficient algorithm to find all configurations?

For example, the following are 2 valid configurations of the same chessboard grid. How to find all others efficiently?

config 1

config 2

In such a simple form I guess this may be a classic problem for algorithm or graph theory courses, but I don't even know what's the keyword to search. I was thinking about exhaustive method: loop over all dots, bookkeeping all bonds(T/F) and reject conflicts during the process; it was, of course, exhaustive.

[edit]

Another example using $2\times 2$ chessboard grid. There are only 2 valid solutions.

O--X  or  O  X
          |  |
X--O      X  O
$\endgroup$
  • $\begingroup$ I think you should ask first "Does an efficient algorithm for this exist?". If there is an exponential number of configurations, then there is no efficient solution. $\endgroup$ – klaus Oct 26 '17 at 16:16
  • 1
    $\begingroup$ You have a lot of questions, the usual rule is one per post. Do you need all results? What are the constraints? What should answer contain? Have you tried running your brute force for small grid? $\endgroup$ – Evil Oct 26 '17 at 16:36
  • $\begingroup$ Is finding a proper configuration NP-complete? If yes, then counting their number is almost surely #P-complete. $\endgroup$ – rus9384 Oct 26 '17 at 18:22
  • $\begingroup$ Whoa. I didn't know this can be a problem as hard as NP-complete. Is there a rule of thumb to determine whether a problem is NP? @Evil, I edited my original post and add an example of $2\times 2 $ grid. Hope that clarifies the question. $\endgroup$ – ceylon Oct 26 '17 at 19:34
  • 1
    $\begingroup$ You don't have to think of NP-completeness or something, because counting perfect matchings on planar graphs can be done by FKT algorithm. However here is the listing, and there is surely exponential number of solutions, so you may want a practically efficient algorithm. $\endgroup$ – Willard Zhan Oct 26 '17 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.