Der Vier-Farben-Satz besagt, dass nicht mehr als vier Farben erforderlich sind, um die Regionen einer Karte einzufärben.

Die Herausforderung

Wenn eine Liste mit Statusgrenzen angegeben ist, weisen Sie jeder Status-ID eine Farbe zu, sodass keine zwei benachbarten Status dieselbe Farbe haben. Die Ausgabe sollte ein CSS-Stylesheet sein, das dem 2-Buchstaben-ID-Code des Staates die Farbe zuweist. Hier ist eine SVG-Karte, auf die das Stylesheet angewendet werden könnte. http://upload.wikimedia.org/wikipedia/commons/3/32/Blank_US_Map.svg

Die Regeln

• Kürzester Code gewinnt
• Es kann jede staatliche Grenzliste verwendet werden
• Es können nur 4 Farben verwendet werden.
• Die Statusliste kann fest codiert werden

Hinweis: Verwenden Sie die CSS- fill:Eigenschaft, um beispielsweise die Farbe zu ändern#AL{fill:green}

Hier ist eine Liste der Staatsgrenzen

AL-FL
AL-GA
AL-MS
AL-TN
AR-LA
AR-MO
AR-MS
AR-OK
AR-TN
AR-TX
AZ-CA
AZ-CO
AZ-NM
AZ-NV
AZ-UT
CA-NV
CA-OR
CO-KS
CO-NE
CO-NM
CO-OK
CO-UT
CO-WY
CT-MA
CT-NY
CT-RI
DC-MD
DC-VA
DE-MD
DE-NJ
DE-PA
FL-GA
GA-NC
GA-SC
GA-TN
IA-MN
IA-MO
IA-NE
IA-SD
IA-WI
ID-MT
ID-NV
ID-OR
ID-UT
ID-WA
ID-WY
IL-IA
IL-IN
IL-KY
IL-MO
IL-WI
IN-KY
IN-MI
IN-OH
KS-MO
KS-NE
KS-OK
KY-MO
KY-OH
KY-TN
KY-VA
KY-WV
LA-MS
LA-TX
MA-NH
MA-NY
MA-RI
MA-VT
MD-PA
MD-VA
MD-WV
ME-NH
MI-OH
MI-WI
MN-ND
MN-SD
MN-WI
MO-NE
MO-OK
MO-TN
MS-TN
MT-ND
MT-SD
MT-WY
NC-SC
NC-TN
NC-VA
ND-SD
NE-SD
NE-WY
NH-VT
NJ-NY
NJ-PA
NM-OK
NM-TX
NM-UT
NV-OR
NV-UT
NY-PA
NY-VT
OH-PA
OH-WV
OK-TX
OR-WA
PA-WV
SD-WY
TN-VA
UT-WY
VA-WV

Python, 320 Zeichen

import sys,random
S=[]
E={}
for x in sys.stdin:a=x[:2];b=x[3:5];S+=[a,b];E[a,b]=E[b,a]=1
C={0:0}
while any(1>C[s]for s in C):
 C={s:0for s in S};random.shuffle(S)
 for s in S:
    A=set([1,2,3,4])-set(C[y]for x,y in E if x==s)
    if A:C[s]=random.choice(list(A))
for s in C:print'#%s{fill:%s}'%(s,' bglrloieulmdede'[C[s]::4])

Verwendet einen zufälligen Algorithmus. Ordnen Sie den Status Farben in zufälliger Reihenfolge zu, indem Sie eine Farbe auswählen, die nicht mit benachbarten Status in Konflikt steht, die bereits gefärbt wurden. Scheint, in einer Zehntelsekunde oder so auf dem gegebenen Eingang zu arbeiten.

Beispielausgabe:

$ 4color.py < stategraph
#WA{fill:red}
#DE{fill:gold}
#DC{fill:blue}
#WI{fill:blue}
#WV{fill:red}
#FL{fill:lime}
#WY{fill:gold}
#NH{fill:red}
#NJ{fill:lime}
#NM{fill:gold}
#TX{fill:red}
#LA{fill:blue}
#NC{fill:blue}
#ND{fill:gold}
#NE{fill:blue}
#TN{fill:red}
#NY{fill:gold}
#PA{fill:blue}
#RI{fill:gold}
#NV{fill:red}
#VA{fill:gold}
#CO{fill:red}
#CA{fill:gold}
#AL{fill:blue}
#AR{fill:gold}
#VT{fill:lime}
#IL{fill:red}
#GA{fill:gold}
#IN{fill:lime}
#IA{fill:gold}
#OK{fill:blue}
#AZ{fill:lime}
#ID{fill:lime}
#CT{fill:red}
#ME{fill:blue}
#MD{fill:lime}
#MA{fill:blue}
#OH{fill:gold}
#UT{fill:blue}
#MO{fill:lime}
#MN{fill:red}
#MI{fill:red}
#KS{fill:gold}
#MT{fill:blue}
#MS{fill:lime}
#SC{fill:red}
#KY{fill:blue}
#OR{fill:blue}
#SD{fill:lime}

Beispiel in Svg eingefügt .

Prolog, 309 307 283 Zeichen

:-initialization m.
a-X:-assert(X);retract(X),1=0.
r:-maplist(get_char,[A,B,E,C,D,F]),(E=F;X=[A,B],Y=[C,D],a-X/Y,a-Y/X,(s/X;a-s/X),(s/Y;a-s/Y),r).
s+[]:- \+ (X*C,writef('#%s{fill:#%w}',[X,C]),1=0).
s+[X|T]:-member(C,[911,191,119,991]),a-X*C,\+ (X/Y,Y*C),s+T.
m:-r,bagof(X,s/X,L),s+L.

Der Algorithmus verwendet die Rückverfolgung / Tiefensuche, um die Karte auszufüllen.

Ein bisschen besser lesbar:

:- initialization(main).

% Found on http://awarth.blogspot.de/2008/08/asserts-and-retracts-with-automatic.html
assert2(X) :- assert(X).
assert2(X) :- retract(X), fail.

% Reads all states into clauses "state-State",
% and all connections into "State-Neighbor" and "Neighbor-State".
read_states :-
    % Read a line "AB-CD\n"
    maplist(get_char, [A,B,E,C,D,F]),
    (   A = F;
        State = [A, B],
        Neighbor = [C, D],
        % Memorize the connection between State and Neighbor in both directions.
        assert(State/Neighbor),
        assert(Neighbor/State),
        % Memorize State and Neighbor for the list of states.
        (state/State; assert(state/State)),
        (state/Neighbor; assert(state/Neighbor)),
        % Continue for all lines.
        read_states
    ).

% Print out all colors.
solve([]) :-
    once((
        State*Color,
        writef('#%s{fill:%w}', [State, Color]),
        fail
    )); !.

% Use depth-first search to color the map.
solve([State|FurtherStates]) :-
    member(Color, ['#911', '#191', '#119', '#991']),
    assert2(State*Color),
    \+ (State/Neighbor, Neighbor*Color),
    solve(FurtherStates).

main :-
    read_states,
    bagof(State, state/State, States),
    solve(States).

Aufruf:

cat borders.txt | swipl -q ./fourcolors.pl

Ergebnis (Zeilenumbrüche sind nicht erforderlich):

#AL{fill:#911}#FL{fill:#191}#GA{fill:#119}#MS{fill:#191}#TN{fill:#991}#AR{fill:#911}#LA{fill:#119}#MO{fill:#191}#OK{fill:#119}#TX{fill:#191}#AZ{fill:#911}#CA{fill:#191}#CO{fill:#191}#NM{fill:#991}#NV{fill:#991}#UT{fill:#119}#OR{fill:#911}#KS{fill:#911}#NE{fill:#119}#WY{fill:#911}#CT{fill:#911}#MA{fill:#191}#NY{fill:#119}#RI{fill:#119}#DC{fill:#911}#MD{fill:#191}#VA{fill:#119}#DE{fill:#119}#NJ{fill:#191}#PA{fill:#911}#NC{fill:#911}#SC{fill:#191}#IA{fill:#911}#MN{fill:#191}#SD{fill:#991}#WI{fill:#119}#ID{fill:#191}#MT{fill:#119}#WA{fill:#119}#IL{fill:#991}#IN{fill:#191}#KY{fill:#911}#MI{fill:#911}#OH{fill:#119}#WV{fill:#991}#NH{fill:#911}#VT{fill:#991}#ME{fill:#191}#ND{fill:#911}

In eine SVG- Datei eingefügt: http://jsbin.com/toniseqaqi/

JavaScript (ES6) 269 279

Rekursive Suche mit Rückverfolgung. ~ 80 Bytes für die Statuslistenanalyse.

 F=l=>{
   S=(a,b)=>S[a]=(S[a]||[]).concat(b),
   l.replace(/(..)-(..)/g,(_,a,b)=>S(a,b)+S(b,a)),
   k=Object.keys(S),
   R=(p,c=k[p])=>!c||['blue','gold','red','tan'].some(i=>!c.some(t=>S[t].c==i)&&(c.c=i,R(p+1)||(c.c='')),c=S[c]),
   R(0),
   k.map(k=>console.log('#'+k+'{fill:'+S[k].c+'}'))
 }

Ungolfed

F=l=>{
  var states = {}; // hash table with adiacent list for each state
  S=(a,b)=>states[a]=(states[a]||[]).concat(b);
  l.replace(/(..)-(..)/g,(_,a,b)=>S(a,b)+S(b,a)); // build the hash table from the param list 

  keys = Object.keys(states); // get the list of hashtable keys as an array (the 49 states id)
  Scan=(p)=> // Recursive scan function
  {
    var sId = keys[p]; // in sid the current state id, or undefined if passed last key
    if (!sId) return true; // end of keys, recursive search is finished 
    var sInfo = states[sId]; // in sInfo the aarray of adiacent states id + the color property

    return ['blue','gold','red','tan'].some( (color) => // check the four avaialabe colors
      {
        var colorInUse = sInfo.some( (t) => states[t].color == color); // true if an adiacent state already has the currnet color
        if (!colorInUse) // if the color is usable
        {
          sInfo.color = color; // assign the current color to the current state
          var ok = Scan(p+1); // proceed with the recursive scan on the next state
          if (!ok) // if recursive scan failed, backtrack
          {
            sInfo.color = ''; // remove the assigned color for the current state
          }
          return ok;
        }
      }
    )
  },
  Scan(0), // start scan 
  keys.forEach( (sId) => console.log('#'+sId+'{fill:'+states[sId].color+'}')) // output color list
}

Test in der FireFox / FireBug-Konsole

list = "AL-FL AL-GA AL-MS AL-TN AR-LA AR-MO AR-MS AR-OK AR-TN AR-TX AZ-CA AZ-CO AZ-NM "+
"AZ-NV AZ-UT CA-NV CA-OR CO-KS CO-NE CO-NM CO-OK CO-UT CO-WY CT-MA CT-NY CT-RI "+
"DC-MD DC-VA DE-MD DE-NJ DE-PA FL-GA GA-NC GA-SC GA-TN IA-MN IA-MO IA-NE IA-SD "+
"IA-WI ID-MT ID-NV ID-OR ID-UT ID-WA ID-WY IL-IA IL-IN IL-KY IL-MO IL-WI IN-KY "+
"IN-MI IN-OH KS-MO KS-NE KS-OK KY-MO KY-OH KY-TN KY-VA KY-WV LA-MS LA-TX MA-NH "+
"MA-NY MA-RI MA-VT MD-PA MD-VA MD-WV ME-NH MI-OH MI-WI MN-ND MN-SD MN-WI MO-NE "+
"MO-OK MO-TN MS-TN MT-ND MT-SD MT-WY NC-SC NC-TN NC-VA ND-SD NE-SD NE-WY NH-VT "+
"NJ-NY NJ-PA NM-OK NM-TX NM-UT NV-OR NV-UT NY-PA NY-VT OH-PA OH-WV OK-TX OR-WA "+
"PA-WV SD-WY TN-VA UT-WY VA-WV";
F(list);

Ausgabe

#AL{fill:blue}
#FL{fill:gold}
#GA{fill:red}
#MS{fill:gold}
#TN{fill:tan}
#AR{fill:blue}
#LA{fill:red}
#MO{fill:gold}
#OK{fill:red}
#TX{fill:gold}
#AZ{fill:blue}
#CA{fill:gold}
#CO{fill:gold}
#NM{fill:tan}
#NV{fill:tan}
#UT{fill:red}
#OR{fill:blue}
#KS{fill:blue}
#NE{fill:red}
#WY{fill:blue}
#CT{fill:blue}
#MA{fill:gold}
#NY{fill:red}
#RI{fill:red}
#DC{fill:blue}
#MD{fill:gold}
#VA{fill:red}
#DE{fill:red}
#NJ{fill:gold}
#PA{fill:blue}
#NC{fill:blue}
#SC{fill:gold}
#IA{fill:blue}
#MN{fill:gold}
#SD{fill:tan}
#WI{fill:red}
#ID{fill:gold}
#MT{fill:red}
#WA{fill:red}
#IL{fill:tan}
#IN{fill:gold}
#KY{fill:blue}
#MI{fill:blue}
#OH{fill:red}
#WV{fill:tan}
#NH{fill:blue}
#VT{fill:tan}
#ME{fill:gold}
#ND{fill:blue}