parllel programming essay
rohitroyemmanuel
Prologmapcoloring.pptxProlog map coloring program
One of the oldest problems in mathematics.
The program: prolog/map.pl
different (red, green) . different (red, blue) .
different (green, red) . different (green, blue) .
different (blue, red) . different (blue, green) .
coloring (Alabama, Mississippi, Georgia, Tennessee, Florida) :-
different (Mississippi, Tennessee) .
different (Mississippi, Alabama) .
different (Alabama, Georgia) .
different (Alabama, Florida) .
different (Georgia, Florida) .
different (Georgia, Tennessee) .
Now let’s execute the program
Running the program
The call
| ?- coloring (Alabama, Mississippi, Georgia, Tennessee, Florida) .
The result
Alabama = blue
Florida = green
Georgia = red
Mississippi = red
Tennessee = green ?
The ? at the end of the output says Prolog is ready for another question based on this set of propositions.
Questions about this program
What algorithm does it employ?
A child could probably explain it after studying it a few minutes. Why?
Extending it to 48 states would be obvious, however a bit tedious.
How would you flowchart it?
How many lines would it take to program this application in Java, C, or C#? More than 13?
Can you find a classical solution process on the Internet? Compare it to the Prolog solution.
Is the map coloring problem NP complete? See https://en.wikipedia.org/wiki/NP-completeness
