Posted by Danny TarlowI posted last time about constraint satisfaction problems that are locally consistent (arc-consistent) everywhere but inconsistent globally. Part of the interesting bit was the connection to "impossible" Escher-style art, such as the impossible triangle.
This is really only the beginning, though. There should be many more examples where we have local consistency but global inconsistency. For example, it's straightforward to extend the 3-cycle that produces the impossible triangle to any odd-cycle. This produces impossible pentagons, impossible heptagons, etc. I've drawn the pentagon and heptagon examples below: Naturally, I want to push this further, finding more interesting figures to draw. Here's a proposed algorithm:
- Generate a random constraint satisfaction problem that is arc-consistent but unsatisfiable.
- Translate the kernel--the locally consistent problem that remains after running arc-consistency--into a drawing.
For the first, how do we do it efficiently? I don't know, but we can think of doing guess and check for now. If somebody knows more about this, I'd be interested to hear about it. It seems related to generating hard instances to evaluate constraint satisfaction solvers.
For the second, perhaps somebody with some art background can help. How do we do this generally? I can extend the triangle example to odd cycles of this special form where each variable (corner) has two possible interpretations locally (UPDATE: I'm not sure this is the right interpretation): one where the figure is coming out of the page and one where it is going into the page. But how do we draw a visual analog of a variable with only one legal interpretation? How do we draw variables with more than 2 possible states? How do we draw examples with higher connectivity?
Does anybody know of references to any prior work on this topic?