1

imagine a 2d map with 6 regions R1-R6. Each region should be colored in with 1 of 4 colors, but no adjacent regions can be the same color.

here is my code:

% #1 initial facts
next(red,green).
next(red,blue).
next(red,yellow).
next(green,red).
next(green,blue).
next(green,yellow).
next(blue,green).
next(blue,yellow).
next(blue,red).
next(yellow,red).
next(yellow,blue).
next(yellow,green).
% #1 actual program
color(R1,R2,R3,R4,R5,R6).
color(R1,R2,R3,R4,R5,R6):-
    % region adjacency relations
    next(R1,R2),
    next(R1,R3),
    next(R1,R4),
    next(R2,R4),
    next(R2,R5),
    next(R3,R4),
    next(R3,R6),
    next(R4,R5),
    next(R4,R6).

Expected output:

R1= red, R2= blue, R3= blue, R4= green, R5= red, R6= red

My Output:

true

what am I doing wrong? Is this even wrong? Even if my code is successfully finding the right color configuration, how do I get it to print out its findings?

4
  • Depends which prolog. Does yours have a print command? If you put it as the last clause, it will only print if all preceding clauses succeed.
    – user3821934
    Commented Jul 14, 2015 at 22:06
  • 1
    Your program is currently too general due to the first clause of color/6. You get the solution you expect (as one among many different solutions) if you simply remove that first clause.
    – mat
    Commented Jul 14, 2015 at 22:07
  • I had a feeling it would be something like that. I started learning the stupid language last week. Commented Jul 14, 2015 at 22:08
  • @mat feel free to write that in an answer so that I can accept it. Commented Jul 14, 2015 at 22:09

2 Answers 2

3

Your program is currently too general due to the first clause of color/6. You get the solution you expect (as one among many different solutions) if you simply remove that first clause.

There is also a more beautiful way to write your program:

regions(Rs):-
        Rs = [R1,R2,R3,R4,R5,R6],
        % neighbouring regions have different colors
        dif(R1, R2),
        dif(R1, R3),
        dif(R1, R4),
        dif(R2, R4),
        dif(R2, R5),
        dif(R3, R4),
        dif(R3, R6),
        dif(R4, R5),
        dif(R4, R6),
        maplist(color, Rs).

color(red).
color(green).
color(blue).
color(yellow).

Example query and sample solutions:

?- regions(Rs).
Rs = [red, green, green, blue, red, red] ;
Rs = [red, green, green, blue, red, yellow] ;
Rs = [red, green, green, blue, yellow, red] ;
etc.

Notice the use of dif/2 () to state that two terms are different.

For more serious map coloring tasks, consider using constraints.

4
  • s(X): How about using a different name than regions/1?
    – repeat
    Commented Jul 15, 2015 at 4:52
  • 1
    Thank you! Regarding predicate names, there is almost always room for improvement. The point I would predominantly like to stress in this example is that the variables themselves denote the regions. There is no need for any indirection! A more specific name would be for example regions_with_admissible_coloring/1.
    – mat
    Commented Jul 15, 2015 at 7:08
  • OK. Names are always the hardest part:)
    – repeat
    Commented Jul 15, 2015 at 8:00
  • You're right. But this is a class project names have been pre-specified. Nothing I can do. Commented Jul 15, 2015 at 11:03
0

in case your Prolog doesn't offer dif/2, or you are willing to better understand the basic of this language, here is a possible correction of your code:

next(R1,R2) :-
    select(R1, [red, green, blue, yellow], Cs),
    member(R2, Cs).

color(R1,R2,R3,R4,R5,R6):-
    % region adjacency relations
    next(R1,R2),
    next(R1,R3),
    next(R1,R4),
    next(R2,R4),
    next(R2,R5),
    next(R3,R4),
    next(R3,R6),
    next(R4,R5),
    next(R4,R6).

this is marginally more efficient - on the inference count - than using dif/2.

edit still better, using iso_dif/2, or the 'old style' version

next(R1, R2) :- color(R1), color(R2), R1 \= R2.

of course, color/1 comes from mat' answer

8
  • Is this really faster than next(R1, R2) :- color(R1), color(R2), iso_dif(R1,R2).? (using iso_dif/2).
    – false
    Commented Jul 15, 2015 at 9:23
  • even with dif/2 - highly optimized, afaik in SWI-Prolog implementation - the difference is small - just 13,333 vs 27,878 inferences to compute all 192 solutions. Just, I wonder what dif/2 implementers think about iso_dif/2. I find the name a bit misleading...
    – CapelliC
    Commented Jul 15, 2015 at 9:37
  • Counting inferences is not a reliable performance measure: Your goal select(R1, [red, green, blue, yellow], Cs), counts as much as color(R1). What exactly is misleading for iso_dif/2?
    – false
    Commented Jul 15, 2015 at 9:41
  • @false: just a bit misleading, really
    – CapelliC
    Commented Jul 15, 2015 at 9:44
  • If you really want to make a constructive comment, you could add it to the actual definition of iso_dif/2.
    – false
    Commented Jul 15, 2015 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.