3

I'm trying to use restrictions programming through Prolog CLP FD to solve a puzzle that was proposed. This puzzle consists in the next simple rules:

Yin Yang puzzle description

Now, in my code, I already cover the restrictions for the 2x2 grid AND that one piece MUST be connected to AT LEAST one of the same color.

The problem is that I cannot find a way to build the restriction that says that one piece MUST have a PATH (be connected) to all the other pieces of the same color, without passing through pieces of the opposite color, so I'm getting this kind of outputs:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 0

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

where the 1s are not all connected to each other.

How can I write this kind of graph restrictions in CLP FD?

EDIT: I am using SICStus Prolog.

josealeixo.pc
  • 391
  • 3
  • 13

2 Answers2

2

To reword your situation so that we can more clearly think about it:

  1. you can already generate answers
  2. but the answers are currently too general.

To make your program more specific, you must find a condition that is currently violated in one of the answers you generate, but which must hold in every solution, and then express this condition with constraints.

For example, consider again you case:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

Which condition is violated here? Obviously, the 1 pieces are not along a path. But describing a full path with CLP(FD) is extremely tedious, and since this is apparently taken from an exam or homework question, the idea suggests itself that there is a simple local criterion to express the desired condition.

By "local", I mean that you only have to take into account a few neighbours instead of the whole board.

So, consider again the 1 pieces. Obviously, every 1 piece has a neighbour that is also 1 in this answer. What else? Does every 1 piece have 2 neighbours? No currently, not. Should every 1 piece have 2 neighbours that are also 1? If not, how many exceptions are admissible?

If you think along these conditions, you will definitely obtain a nice solution.

One hint: Sometimes reified constraints are useful in such tasks. This means that you can for example say: B #<==> (X #= Y), and let B denote whether X #= Y holds. Note that you may not even need this in this case.

mat
  • 40,498
  • 3
  • 51
  • 78
  • So I pondered what you said and found a way to get a list telling me how many **equal** pieces are there adjacent to one piece (top, left, bottom or right). I then made one restriction saying that the number of pieces with only **one** equal adjacent piece should not be larger than 5 (because of the 2x2 base case, which has 4 cells), but now I'm getting a shorter set of solutions for other board sizes. Some that should appear do not. I fear this may not be the right way of constraint. How close am I? – josealeixo.pc Dec 21 '16 at 01:25
  • 1
    I think there may be a somewhat more direct way to encode this. For example, there could be a relation between the number of cells with an odd and even number of identical neighbours, which is satisfied by all connected paths. If you approach this as you did, which also seems interesting, you will likely have to relate these numbers to the *size* of the board. For beginners, I consider this a tough problem overall, in the sense that it requires a lot of insight to efficiently express the constraints with CLP(FD). Peter Szeredi discusses similar tasks in his slides, they are well worth a look. – mat Dec 21 '16 at 09:15
  • Could you please point me to he slides you refer to? I followed your advice and was able to constraint my solutions following the Euler Path theorem and saying that 2 and only 2 vertices should have an odd degree, but again, I'm losing solutions. – josealeixo.pc Dec 21 '16 at 17:53
  • 1
    The [slides](http://cs.bme.hu/~szeredi/ait/) describe a somewhat related covering problem (domino tiling), but still leave out the rather difficult "connectedness" constraint. Note that "2 and only 2" vertices is definitely too strict, since the path could be a complete tour. It is really rather difficult to model. The `circuit/1` constraint could help you, but again it is rather difficult: You would first have to map your problem to suitable different variables, and use auxiliary end points to describe not necessarily closed tours. Rather tough for beginners! – mat Dec 21 '16 at 21:47
  • Yes, indeed... How could I choose which cell I want to apply constraints? If I could apply something like the Flood and Fill algorithm, where I keep track of the visited cells and the "open" I could make sure that the "open" cells should not have any different cells. – josealeixo.pc Dec 21 '16 at 22:18
  • 1
    This obviously goes *far* beyond a simple exercise, but you could test whether the final graph (in a suitable representation) has exactly 2 **strongly connected components**. You can use Tarjan's algorithm to determine the strongly connected components in *linear* time. Note though that this puts the whole approach outside a *constraint-based* solution, since that amounts to "generate and test", without (much) *propagation*. A more elegant (and likely faster) approach is to stay with CLP(FD) constraints to express the connectedness. There may be a local criterion for it, but it is hard. – mat Dec 21 '16 at 23:17
  • Yes, I believe using **solely** CLP FD for this is near impossible. I'm going with the Euler path restrictions, because the work is due tomorrow. I just need to figure out why some solutions are appearing more than 1 time. Thanks for your patience Mat ;) – josealeixo.pc Dec 22 '16 at 20:07
0

did either of you solve this problem at last?

I'm very interested in this problem and want to see the code,if exists.

I think circuit/1 cannot help and want to see the usage for solving this.

Taku Koyahata
  • 558
  • 2
  • 13