b'\n_START_ARTICLE_\nProblem osmih dam\n_START_SECTION_\nZgodovina\n_START_PARAGRAPH_\nSkozi \xc4\x8das je problem obravnavalo veliko matematikov. Najbolj znani med njimi so Gauss, P\xc3\xb3lya in Lucas. Problem je poseben primer splo\xc5\xa1nej\xc5\xa1ega problema, ki zahteva re\xc5\xa1itve postavitev n dam na \xc5\xa1ahovnici n \xc3\x97 n._NEWLINE_Zanimivo je, da veliko ljudi pripisuje problem in njegovo re\xc5\xa1itev Gaussu. Problem je dejansko prvi predlagal nem\xc5\xa1ki \xc5\xa1ahist Max Bezzel leta 1848 v \xc4\x8dasopisu Berliner Schachzeitung. S posku\xc5\xa1anjem je do prvih 60 re\xc5\xa1itev pri\xc5\xa1el Franz Nauck in jih 1. junija 1850 objavil v \xc4\x8dasopisu Leipziger Illustrierte Zeitung. Nauck (sicer slep od rojstva) je tudi posplo\xc5\xa1il problem na n dam in \xc5\xa1ahovnico n \xc3\x97 n. Gauss se je po Nauckovi objavi re\xc5\xa1itev lotil problema in sam na\xc5\xa1el le 72 re\xc5\xa1itev, ki jih je zapisal 2. septembra 1850 v pismu svojemu prijatelju, astronomu Schumachru. Tedaj \xc5\xa1e niso poznali postopkov re\xc5\xa1evanja in s presku\xc5\xa1anjem se da nalogo re\xc5\xa1iti v dobrih desetih urah. Nauck je 21. septembra 1850 v isti reviji objavil vseh 92 re\xc5\xa1itev. Tak potek dogodkov je ugotovil nem\xc5\xa1ki raziskovalec problemov iz razvedrilne matematike V. Arens. Leta 1874 je S. G\xc3\xbcnther predlo\xc5\xbeil postopek re\xc5\xa1evanja s pomo\xc4\x8djo determinant, angle\xc5\xa1ki matematik Glaisher pa je \xc5\xa1e dodelal ta pristop. Glaisher je tudi prvi dokazal, da obstaja natanko 92 re\xc5\xa1itev._NEWLINE_Problem se je v 1990. zna\xc5\xa1el v raz\xc5\xa1irjeni ra\xc4\x8dunalni\xc5\xa1ki igri The 7th Guest.\n_START_SECTION_\nProblem osmih dam kot zgled uporabe razli\xc4\x8dnih algoritmov\n_START_PARAGRAPH_\nProblem osmih dam je dober zgled preprostega vendar ne trivialnega problema. Zaradi tega se velikokrat uporablja kot zgled za razli\xc4\x8dne programerske postopke, od katerih velja omeniti netradicionalne pristope kot so logi\xc4\x8dno programiranje ali genetski algoritmi._NEWLINE_Najve\xc4\x8dkrat se uporablja kot zgled problema, ki se ga da re\xc5\xa1iti z rekurzivnim algoritmom tako, da se problemu n dam dodaja posamezna dama k poljubni re\xc5\xa1itvi problema (n-1) dam. Z matemati\xc4\x8dno indukcijo se tako pride do problema 0 dam, kar predstavlja prazno \xc5\xa1ahovnico.\n_START_SECTION_\nZgled programa v pascalu\n_START_PARAGRAPH_\nSpodnji program re\xc5\xa1uje nalogo v programskem jeziku pascal s pomo\xc4\x8djo rekurzije. Izpi\xc5\xa1e vseh 92 re\xc5\xa1itev._NEWLINE_ program osemdam(output);_NEWLINE_ var st, j : integer;_NEWLINE_     a : array [ 1.. 8] of boolean;_NEWLINE_     b : array [ 2..16] of boolean;_NEWLINE_     c : array [-7.. 7] of boolean;_NEWLINE_     x : array [ 1.. 8] of integer;_NEWLINE_   procedure try(i:integer);_NEWLINE_   var j,k:integer;_NEWLINE_   begin_NEWLINE_     for j:=1 to 8 do begin_NEWLINE_       if a[j] and b[i+j] and c[i-j]_NEWLINE_       then begin_NEWLINE_         x[i] := j;_NEWLINE_         a[j] := false; b[i+j] := false; c[i-j] := false;_NEWLINE_         if i<8 then {rekurzivni klic}_NEWLINE_           try(i+1)_NEWLINE_         else_NEWLINE_         begin {izpis resitve}_NEWLINE_           inc(st); write(st:5,\'. \');_NEWLINE_           for k:=1 to 8 do write(x[k]); writeln;_NEWLINE_         end;_NEWLINE_         a[j] := true; b[i+j] := true; c[i-j] := true;_NEWLINE_       end; {if}_NEWLINE_     end; {for}_NEWLINE_   end; {try}_NEWLINE_  begin {glavni program}_NEWLINE_    for j:= 1 to 8  do a[j]:=true;_NEWLINE_    for j:= 2 to 16 do b[j]:=true;_NEWLINE_    for j:= -7 to 7 do c[j]:=true;_NEWLINE_    st:=0;_NEWLINE_    try(1);_NEWLINE_  end._NEWLINE_Vir: N. Wirth, Ra\xc4\x8dunalni\xc5\xa1ko programiranje I, Ljubljana, 1981.\n_START_SECTION_\nZgled programa v Q\n_START_PARAGRAPH_\nAlgoritem za re\xc5\xa1evanje problema n dam, zapisan v Q, ki uporablja postopek vra\xc4\x8danja (backtracking):_NEWLINE__NEWLINE_queens N\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0= search N 1 1 [];_NEWLINE__NEWLINE_search N I J P\xc2\xa0\xc2\xa0= write P || writes "\\n" if I>N;_NEWLINE__NEWLINE_\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0= search N (I+1) 1 (P++[(I,J)]) || fail if safe (I,J) P;_NEWLINE__NEWLINE_\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0= search N I (J+1) P if J<N;_NEWLINE__NEWLINE_\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0= () otherwise;_NEWLINE__NEWLINE_safe (I1,J1) P\xc2\xa0\xc2\xa0= not any (check (I1,J1)) P;_NEWLINE__NEWLINE_check (I1,J1) (I2,J2)_NEWLINE__NEWLINE_\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0= (I1=I2) or else (J1=J2) or else_NEWLINE__NEWLINE_\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0(I1+J1=I2+J2) or else (I1-J1=I2-J2);\n_START_SECTION_\nZgled programa za HP-41\n_START_PARAGRAPH_\nGlej HP-41.'