AI Project #2, R91922034, Hung-Te Lin, 林弘德

由於程式很小，我就直接把 code 跟我的感想等等混合說明如下：

% R91922034 Hung-Te Lin, AI Project 2

% Utility Functions

我的想法是，Prolog 會自己找答案，那我就想辦法讓它去自動著色，然後 做檢查把不合的拿掉。 著色有兩種方式，可以照區域上色，也可以對 Edge 兩邊。 本來我是寫成對 Edge 兩邊上色再去 match，不過後來考慮到題目要求 的格式是照 Region 輸出的，代表最後還是要做一次找 Region 的作； 所以 後來還是改成照 Region 上色。 所以，第一步是先寫出從給定的 Edge List 中找出所有 region 的部份。 我稱之為 extract_regions:

% extract_regions: extract region data from assigned map
%                  usage: extract_regions(EdgeList, [], Regions).
%  unify the bindings and regions
extract_regions([], Regions, Regions).
%  recursive rules
extract_regions([ [S,T] | Rest ], Bindings, Regions) :-
        member(S, Bindings) ->
        (member(T, Bindings) ->
            % both S and T in Regions
            extract_regions( Rest, Bindings, Regions ) ;
            % S in Regions while T is not
            extract_regions( Rest, [T|Bindings], Regions)) ;
        % S not in Regions
        (member(T, Bindings) ->
            % T in Regions while S in not
            extract_regions( Rest, [S|Bindings], Regions) ;
            % both S and T are not in Regions
            extract_regions(Rest, [S,T|Bindings], Regions)).

本來對建 region 有點頭痛，找了一下網路上的 prolog source 發現到有 if then else 的結構； 於是改寫成上面的形式，好寫多了。

% paint_colors: paint colors to regions
%               usage: paint_colors(Regions, Colors, Paintings).
%  first rule: if no region, just return nothing
paint_colors([], _, []).
%  search rule:
paint_colors([Rgn | Rest], Colors, [[Rgn,C] | Paintings]) :-
        member(C, Colors),
        paint_colors(Rest, Colors, Paintings).

後面就很好寫了： paint_colors 直接讓 Prolog 從 Colors 中拿出所有可以用的色表來上色。

%  utility to display all paintings.
%list-paintings(Regions, Colors) :-
%       paint_colors(Regions, Colors, Paintings),
%       write(Paintings),nl,
%       fail.

% same_color: check if any adjacent edges have same_color
%             usage: same_color(EdgeList, Colors, Paintings).
same_color(EdgeList, Colors, Paintings) :-
        member(C, Colors),
        member([S, T], EdgeList),
        member([S, C], Paintings),
        member([T, C], Paintings).

同樣，same_color 是我對所有的 EdgeList 去找有沒有違規的情形。 接下來測試一下各 utility 都沒有問題就可以來寫最後符合題目要求的 input 跟 output。 這裡有點小技巧，之前找不到 not，後來看到 \+ 可以達到類似的需求。

% the final program, in term project #2 specified format.
color(EdgeList, Colors, Coloring) :-
        extract_regions(EdgeList, [], Regions_BeforeSorting),
        sort(Regions_BeforeSorting, Regions),
        paint_colors(Regions, Colors, Coloring),
        \+ same_color(EdgeList, Colors, Coloring).

list-color(EdgeList, Colors, Coloring) :-
        extract_regions(EdgeList, [], Regions_BeforeSorting),
        sort(Regions_BeforeSorting, Regions),
        paint_colors(Regions, Colors, Coloring),
        \+ same_color(EdgeList, Colors, Coloring),
        write(Coloring), nl,
        fail.

list-color 是我用來自動 (不用按 ;)把所有解列出來的函式。

這次作業滿有趣的， Prolog 有很多好處，不過一開始想很麻煩。 它的 debug 之類也沒那麼直覺。 還有就是我本來寫了一堆的東西， 後來多半無用，因為之前忘了 Prolog 會去幫我找答案。 最後是因為 Google 幫我找到一堆好程式，看了他們的寫法後才變成這麼精簡。