Problem 5, map coloring, availablecolors, etc.

Master / Vertiefung Künstliche Intelligenz
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Problem 5, map coloring, availablecolors, etc.
I think I managed to fix the situation with the notebook. There may or may not be a bug in [m]availablecolors[/m] (apart from the fact that it does the opposite of what it says). It works for me now on some tests. If it does not work for you, please let me know just how it crashes, best here in the forum.

If you run the sample paint query on a clean setup, you should get

ColoredMap = [sa:red, tas:red, vic:red, nsw:red, qld:red, nt:red, wa:red]
3

In https://kwarc.info/teaching/AI/resources/hw5-setup.txt there is a missing semicolon, isn’t it?

arrangecolors([Country:Neighbors|Rest], ColorList, TempList, ColoredMap) :-
member(Color,ColorList),
% Tracing:
% write(‘Color:’), write(Color),write(’ TempList:'), write(TempList),nl,
different(Color,Neighbors,TempList) ← here
arrangecolors(Rest,ColorList,[Country:Color|TempList], ColoredMap).

4

We already submitted a working solution with the original code.
Do you want us to find another one with the updated code?

original:
sortedcountries(Countries,TempList,SortedCountries) :-
countrieswithconstraints(Countries,TempList,[],CountriesWithConstraints),
keysort(CountriesWithConstraints,SortedCountriesWithConstraints),
% write(SortedCountriesWithConstraints), nl,
pairs_keys_values(SortedCountriesWithConstraints,_,SortedCountries).

5

[m]arrangecolors[/m] is in the Edit section, which is the one you were supposed to fix.
As for [m]sortedcountries[/m], either is ok.

6

Is there a solution to this assignement somewhere?

7

Unfortunately the original solution got corrupted and I didn’t get around to rewriting it - sorry about that! Someone might be willing to share their working solution.

8

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Edit section

arrangecolors([],_,ColoredMap,ColoredMap).
arrangecolors(CountryList, ColorList, TempList, ColoredMap) :-
%5.1.(4)
%Aenderung des ersten Elements um sortedcountries zu benutzen"

%5.1.(4)
%Aufrufen von sortedcountries mit neuer Liste L
sortedcountries(CountryList,TempList,L),

%5.1.(4)
%um die geordnete Liste zu benutzen Aufruf von istgleich
istgleich(L,[Country:Neighbors|Rest]),

%5.1(2)
%Zeile 21, in der member aufgerufen wird, da member eine Farbe aus ColorList nimmt, falls different true ist.
%Falls differnet aber false ausgibt backtracked member automatisch und versucht es mit der naechsten Farbe.
member(Color,ColorList),
different(Color,Neighbors,TempList),
arrangecolors(Rest,ColorList,[Country:Color|TempList], ColoredMap).

%5.1(3)
restrictedness(Neighbors,TempList,R) :-

%Suche moegliche Farben
availablecolors(Neighbors,TempList,[],List),
%Da availablecolors eine Liste mit Duplikaten ausgeben kann -> removeDuplicates
removeDuplicates(List,L),
%Die Laenge von L ist dann die Anzahl der nicht zu gebrauchenden Farben
length(L,S),
%-> 4-S = R
R is 4-S.

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Maybe useful things

findneighbors(X, Map, Who) :-
map(Map, Countries),
neighbors(X,Countries,Who).

neighbors(,[],[]).
neighbors(X,[X:Neighbors|], Neighbors) :- !. % Try this without the !
neighbors(X,[_|RestofCountries], Neighbors) :-
neighbors(X,RestofCountries, Neighbors).

adjacent(X,Y,Map) :-
findneighbors(X, Map, Countries),
member(Y, Countries).

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% This you will most likely use
different(C, Nbs, [S1:C1|Rest]) :-
not((member(S1,Nbs), C = C1)),
different(C, Nbs,Rest).
different(,,[]).

availablecolors(_,[],Colors,Colors).
availablecolors(Neighbors,[NB:Color|TempListTail],TempColors,Colors) :-
member(NB,Neighbors) →
availablecolors(Neighbors,TempListTail,[Color|TempColors],Colors);
availablecolors(Neighbors,TempListTail,TempColors,Colors).

%5.1(3)
%Hilfsfunktion removeDuplicates aus frueherer Hausaufgabe
delete(_,[],[]).
delete(Xa,[Xa|Ra],Na):-!,delete(Xa,Ra,Na).
delete(Xa,[Ya|Ra],[Ya|Na]):-delete(Xa,Ra,Na).
removeDuplicates([],[]).
removeDuplicates([Xb|Rb],[Xb|Nb]):-delete(Xb,Rb,Ub), removeDuplicates(Ub,Nb).

countrieswithconstraints([],_,L,L).
countrieswithconstraints([Country:Neighbors|Rest],TempList,Accumulator,CountriesWithConstraints) :-
countrieswithconstraints(Rest,TempList,[R-(Country:Neighbors)|Accumulator],CountriesWithConstraints),
restrictedness(Neighbors,TempList,R).

sortedcountries(Countries,TempList,SortedCountries) :-
countrieswithconstraints(Countries,TempList,[],CountriesWithConstraints),
keysort(CountriesWithConstraints,SortedCountriesWithConstraints),
% write(SortedCountriesWithConstraints), nl,
pairs_keys_values(SortedCountriesWithConstraints,_,SortedCountries).

istgleich([],[]).
istgleich([Country:Neighbors|Rest],[Country:Neighbors|Rest]).

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Main
paint(Map,ColoredMap) :-
map(Map, Countries),
colors(ColorList),
% Tracing:
% write('ColoredMap is '), write(ColoredMap), nl.
arrangecolors(Countries,ColorList,[], ColoredMap).

%5.1(5) ich verstehe nicht was in dem Fall tiebreaker bedeuten soll
%im Zweifel regelt aber prolog mit backtracking

1 „Gefällt mir“
9

Thanks!