From Wikipedia, the free encyclopedia
Problém ôsmih dám je problem šahovskega tipa in zahteva postavitev osmih dam na šahovnici 8 × 8, tako da druga druge ne napadajo. Pri tem veljajo običajna pravila gibanja dame. Barva figure je nepomembna, tako da lahko vsaka figura napade katerokoli drugo. Ali drugače rečeno, dve dami ne moreta hkrati biti v isti vrstici, stolpcu ali diagonali.
Skozi čas je problem obravnavalo veliko matematikov. Najbolj znani med njimi so Gauss, Pólya in Lucas. Problem je poseben primer splošnejšega problema, ki zahteva rešitve postavitev n dam na šahovnici n × n.
Zanimivo je, da veliko ljudi pripisuje problem in njegovo rešitev Gaussu. Problem je dejansko prvi predlagal nemški šahist Max Bezzel leta 1848 v časopisu Berliner Schachzeitung. S poskušanjem je do prvih 60 rešitev prišel Franz Nauck in jih 1. junija 1850 objavil v časopisu Leipziger Illustrierte Zeitung. Nauck (sicer slep od rojstva) je tudi posplošil problem na n dam in šahovnico n × n. Gauss se je po Nauckovi objavi rešitev lotil problema in sam našel le 72 rešitev, ki jih je zapisal 2. septembra 1850 v pismu svojemu prijatelju, astronomu Schumachru. Tedaj še niso poznali postopkov reševanja in s preskušanjem se da nalogo rešiti v dobrih desetih urah. Nauck je 21. septembra 1850 v isti reviji objavil vseh 92 rešitev. Tak potek dogodkov je ugotovil nemški raziskovalec problemov iz razvedrilne matematike V. Arens. Leta 1874 je S. Günther predložil postopek reševanja s pomočjo determinant, angleški matematik Glaisher pa je še dodelal ta pristop. Glaisher je tudi prvi dokazal, da obstaja natanko 92 rešitev.
Problem se je v 1990. znašel v razširjeni računalniški igri The 7th Guest.
Problem osmih dam ima 92 različnih rešitev, oziroma 12 rešitev, če upoštevamo še simetrijske operacije, kot so zasuk in zrcaljenje šahovnice v skladu z Burnsideovo lemo (Pólyev izrek).
Osnovne rešitve urejene leksikografsko so:
Splošni problem n dam ima število rešitev za n ≥ 1 (OEIS A000170):
Šahovnici za n = 2, 3 nimata rešitev.
Število osnovnih rešitev splošnega problema za n ≥ 1 (OEIS A002562):
n | različne rešitve (A000170) | (A032522) | (90°) A033148) | osnovne rešitve (A002562) |
---|---|---|---|---|
1 | 1 | 1 | 1 | 1 |
2 | 0 | 0 | — | 0 |
3 | 0 | 0 | — | 0 |
4 | 2 | 2 | 2 | 1 |
5 | 10 | 2 | 2 | 2 |
6 | 4 | 4 | — | 1 |
7 | 40 | 8 | — | 6 |
8 | 92 | 4 | 0 | 12 |
9 | 352 | 16 | 0 | 46 |
10 | 724 | 12 | — | 92 |
11 | 2.680 | 48 | — | 341 |
12 | 14.200 | 80 | 8 | 1.787 |
13 | 73.712 | 136 | 8 | 9.233 |
14 | 365.596 | 420 | — | 45.752 |
15 | 2.279.184 | 1.240 | — | 285.053 |
16 | 14.772.512 | 3.000 | 64 | 1.846.955 |
17 | 95.815.104 | 8.152 | 128 | 11.977.939 |
18 | 666.090.624 | 18.104 | — | 83.263.591 |
19 | 4.968.057.848 | 44.184 | — | 621.012.754 |
20 | 39.029.188.884 | 144.620 | 480 | 4.878.666.808 |
21 | 314.666.222.712 | 375.664 | 704 | 39.333.324.973 |
22 | 2.691.008.701.644 | 1.250.692 | — | 336.376.244.042 |
23 | 24.233.937.684.440 | 3.581.240 | — | 3.029.242.658.210 |
24 | 227.514.171.973.736 | 11.675.080 | 3.328 | 28.439.272.956.934 |
25 | 2.207.893.435.808.352 | 34.132.592 | 3.264 | 275.986.683.743.434 |
26 | 22.317.699.616.364.044 | 115.718.268 | — | 2.789.712.466.510.289 |
27 | ? | 320.403.024 | — | ? |
Splošni obrazec za točno število rešitev ni znan. Rešitev za n = 26 je 11. julija 2009 izračunala skupina Queens(AT)TUD s Tehniške univerze v Dresdnu.[1] Njen rezultat so potrdili 15. septembra istega leta s paralelnim programskim sistemom MC# na dveh superračunalnikih.[2]
Problem osmih dam je dober zgled preprostega vendar ne trivialnega problema. Zaradi tega se velikokrat uporablja kot zgled za različne programerske postopke, od katerih velja omeniti netradicionalne pristope kot so logično programiranje ali genetski algoritmi.
Največkrat se uporablja kot zgled problema, ki se ga da rešiti z rekurzivnim algoritmom tako, da se problemu n dam dodaja posamezna dama k poljubni rešitvi problema (n-1) dam. Z matematično indukcijo se tako pride do problema 0 dam, kar predstavlja prazno šahovnico.
Spodnji program rešuje nalogo v programskem jeziku pascal s pomočjo rekurzije. Izpiše vseh 92 rešitev.
program osemdam(output);
var st, j : integer;
a : array [ 1.. 8] of boolean;
b : array [ 2..16] of boolean;
c : array [-7.. 7] of boolean;
x : array [ 1.. 8] of integer;
procedure try(i:integer);
var j,k:integer;
begin
for j:=1 to 8 do begin
if a[j] and b[i+j] and c[i-j]
then begin
x[i] := j;
a[j] := false; b[i+j] := false; c[i-j] := false;
if i<8 then {rekurzivni klic}
try(i+1)
else
begin {izpis resitve}
inc(st); write(st:5,'. ');
for k:=1 to 8 do write(x[k]); writeln;
end;
a[j] := true; b[i+j] := true; c[i-j] := true;
end; {if}
end; {for}
end; {try}
begin {glavni program}
for j:= 1 to 8 do a[j]:=true;
for j:= 2 to 16 do b[j]:=true;
for j:= -7 to 7 do c[j]:=true;
st:=0;
try(1);
end.
Vir: N. Wirth, Računalniško programiranje I, Ljubljana, 1981.
Algoritem za reševanje problema n dam, zapisan v Q, ki uporablja postopek vračanja (backtracking):
queens N = search N 1 1 [];
search N I J P = write P || writes "\n" if I>N;
= search N (I+1) 1 (P++[(I,J)]) || fail if safe (I,J) P;
= search N I (J+1) P if J<N;
= () otherwise;
safe (I1,J1) P = not any (check (I1,J1)) P;
check (I1,J1) (I2,J2)
= (I1=I2) or else (J1=J2) or else
(I1+J1=I2+J2) or else (I1-J1=I2-J2);
Glej HP-41.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.