prologgraph-coloring

Solving the Graph Coloring with 3 color and lists - Prolog

I need to solve graph-coloring problem with Prolog. It's about Map of Latin America with 3 colors, and the problem description says the i-th member of Coloring should be used to Color the i-th member of countries, which is not very clear to me how to match them.

👇 Here's the program so far,

adjacent(brazil, suriname).
adjacent(brazil, guyana).
adjacent(brazil, venezuela).
adjacent(brazil, colombia).
adjacent(brazil, peru).
adjacent(brazil, bolivia).
adjacent(brazil, paraguay).
adjacent(brazil, argentina).
adjacent(brazil, uruguay).
adjacent(frenchguiana, suriname).
adjacent(suriname, guyana).
adjacent(guyana, venezuela).
adjacent(venezuela, colombia).
adjacent(colombia, ecuador).
adjacent(colombia, peru).
adjacent(ecuador, peru).
adjacent(peru, bolivia).
adjacent(bolivia, chile).
adjacent(bolivia, paraguay).
adjacent(chile, argentina).
adjacent(paraguay, argentina).
adjacent(argentina, uruguay).
adjacent(chile, peru).
adjacent(argentina, bolivia).

coloring([red,yellow,green]).

neighbor(X,Y) :- adjacent(X, Y). 
neighbor(X,Y) :- adjacent(Y, X).

conflict(A,Ca,B,Cb) :-
   adjacent(A,B),
   Ca \= Cb.

solve(?, ?) :-

👇 and this should the query. solve([brazil,colombia,argentina,peru,venezuela,chile,ecuador,bolivia,paraguay,uruguay,guyana,suriname,frenchguiana],Coloring)

I've seen the example algorithms on google, but seems different from the way i should do it.

Solution

  • I'll outline one approach to a solution without writing your code for you and depriving you of the immersive learning experience. :)

    You just need one argument for your solve predicate, which is the set of colors that your countries can be colored. That leads to a question already: what does it look like in terms of its structure? It seems logical for it to be a list of country-color pairs. A nice way to do pairs in Prolog is using a hyphen functor, e.g., uruguay-red.

    solve would do this:

    1. Gather a list of countries - you can use setof
    2. Bind the list of colors to a variable (call coloring)
    3. Call a predicate (maybe call it countries_colors) that will build a list of country-colors. It will need the list of countries, the list of color choices, and an empty list as a starting list of determined country-color pairs

    countries_colors would recursively look at each country in the country list, choose a color from the color list, and check if the country of that chosen color conflicts with any country-color pair determined so far (from the list of determined country-color pairs). It would:

    1. Pick a color
    2. Check whether the current country and color conflicts with a country-color pair in the current country-color list
    3. Step 2 backtracks to try a different color if it fails
    4. Include the new country-color pair in the country-color list and recursively check the rest of the countries against that list with different colors.

    If you implement this correctly, your current database will have no solutions. It's because your adjacency facts can't be true in two dimensions. You can get solutions if you just remove, for example, adjacent(argentina, bolivia). from the database.