Problem osmih dam

Ena od 12-ih osnovnih rešitev

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.

Zgodovina

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.

Rešitve

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:

1, 5, 8, 6, 3, 7, 2, 4
1, 6, 8, 3, 7, 4, 2, 5
2, 4, 6, 8, 3, 1, 7, 5
2, 5, 7, 1, 3, 8, 6, 4
2, 5, 7, 4, 1, 8, 6, 3
2, 6, 1, 7, 4, 8, 3, 5
2, 6, 8, 3, 1, 4, 7, 5
2, 7, 3, 6, 8, 5, 1, 4
2, 7, 5, 8, 1, 4, 6, 3
3, 5, 2, 8, 1, 7, 4, 6
3, 5, 8, 4, 1, 7, 2, 6
3, 6, 2, 5, 8, 1, 7, 4

Rešitve splošnega problema

Splošni problem n dam ima število rešitev za n ≥ 1 (OEIS A000170):

1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884,

314666222712, 2691008701644, 24233937684440, ...

Šahovnici za n = 2, 3 nimata rešitev.

Število osnovnih rešitev splošnega problema za n ≥ 1 (OEIS A002562):

1, 0, 0, 1, 2, 1, 6, 12, 46, 92, 341, 1787, 9233, 45752, 285053, 1846955, 11977939, 83263591, 621012754, 4878666808,

39333324973, 336376244042, 3029242658210, ...

n	različne rešitve (A000170)	$C_{2}$ (A032522)	$D_{2}$ (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]

Sorodni problemi

Uporaba drugih figur

Na šahovnico 8 × 8 lahko postavimo 32 neodvisnih skakačev, 14 lovcev ali 16 kraljev. Lahko uporabimo tudi pravljične šahovske figure, na primer, amazonke.

Problem amazonk.

Amazonka (imenovana tudi superdama) je figura, ki se giblje kot dama in kot skakač. Postaviti je možno deset amazonk na šahovnico 10 × 10, da druga druge ne napadajo, na točno štiri načine. Na manjših šahovnicah ne obstaja rešitev problema z amazonkami.

Nestandardne šahovnice

Pólya je raziskoval problem n dam na šahovnici v obliki svitka. Raziskovali so tudi druge oblike. Na primer trirazsežno šahovnico.

Prevlada

Za dano šahovnico n × n je potrebno najti število prevlade, ki pomeni najmanjše število dam (ali drugih figur), da so napadena vsa polja. Pri tem velja, da je polje na katerem stoji figura že napadeno. Glej problem petih dam.

Problem devetih dam (v angleščini)

Postavitev devetih dam in enega kmeta, da se dame med sabo ne napadajo. Posplošitev, ki trenutno ni znana je, šahovnica n × n in m > n dam. Rešitev išče najmanjše število kmetov, da se spet dame ne bodo napadale.

Problem dam in skakačev Arhivirano 2005-10-16 na Wayback Machine. (v angleščini)

Postavitev m dam in m skakačev na šahovnico n × n, da se figure med seboj ne napadajo.

Celoštevilsko zaporedje

Paul B. Muljadi je pokazal, da če ostevilčimo 64 polj šahovnice zaporedoma od 1 do 64, lahko vse različne rešitve prikažemo z 92 celoštevilskimi zaporedji, kjer položaj dame predstavlja člen.

Ena rešitev je na primer

6,9,21,26,40,43,55,60\;

Ker mora vsaka dama biti v natančno eni vrstici ali stolpcu (in diagonali) in ker je enako število dam kot je vrstic in stolpcev, bo vsota takšnega zaporedja vedno ista. V zgornjem zaporedju bo vsota 8 + Σ(1..7) + 8 · Σ(1..7) = 260, kar predstavlja magično konstanto za problem osmih dam za vseh 92 različnih rešitev.

Seveda lahko rešitve zapišemo še drugače. Na primer za zgornjo rešitev s številčnim nizom:

6,1,5,2,8,3,7,4\;,

ali v algebrskem šahovskem zapisu:

a6, b1, c5, d2, e8, f3, g7, h4,

ali z matriko:

{\begin{bmatrix}0&0&0&0&0&1&0&0\\1&0&0&0&0&0&0&0\\0&0&0&0&1&0&0&0\\0&1&0&0&0&0&0&0\\0&0&0&0&0&0&0&1\\0&0&1&0&0&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&1&0&0&0&0\\\end{bmatrix}}\;.

Magični kvadrat

Muljadi je tudi odkril, da je magična konstanta problema osmih dam enaka kot magična konstanta magičnih kvadratov reda 8.

Problem osmih dam kot zgled uporabe različnih algoritmov

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.

Zgledi programov

Zgled programa v pascalu

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.

Zgled programa v Q

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);

Zgled programa za HP-41

Glej HP-41.

Glej tudi

Sklici

↑ »Queens@TUD« (v angleščini). Arhivirano iz prvotnega spletišča dne 10. novembra 2017. Pridobljeno 31. avgusta 2011.
↑ »MC#« (v angleščini). Arhivirano iz prvotnega spletišča dne 10. septembra 2011. Pridobljeno 31. avgusta 2011.

Zunanje povezave

http://chp.uni-mb.si/programiranje1/rekurzij/osem_dam/ Arhivirano 2004-11-02 na Wayback Machine.
http://www.ijp.si/DiskretnaMatematikaI/dm06_files/frame.htm#slide0224.htm Arhivirano 2004-10-31 na Wayback Machine. (deluje le v brskalniku MS Internet Explorer)
Weisstein, Eric Wolfgang. »Queens Problem«. MathWorld.
http://bridges.canterbury.ac.nz/features/eight.html (angleško)
http://www.liacs.nl/home/kosters/nqueens.html Arhivirano 2006-10-14 na Wayback Machine. (angleško)
http://www.durangobill.com/N_Queens.html (angleško)

Povezave do rešitev

Atari BASIC
Genetic algorithms
Haskell/Java hibrid Arhivirano 2006-04-30 na Wayback Machine.
Java
Standard ML
Celoštevilska zaporedja Arhivirano 2005-03-19 na Wayback Machine.

[1] »Queens@TUD« (v angleščini). Arhivirano iz prvotnega spletišča dne 10. novembra 2017. Pridobljeno 31. avgusta 2011.

[2] »MC#« (v angleščini). Arhivirano iz prvotnega spletišča dne 10. septembra 2011. Pridobljeno 31. avgusta 2011.

[1]

[2]