Komputada Leksikono: La 8 damoj

La 8 damoj

Algoritma solvo pri la 8 damoj
Paskala programo pri la 8 damoj: Ĉiuj solvoj

La Problemo pri ok damoj estas ŝuldata al Gaŭso (Gauß, 1777–1855).

Oni povas peti trovi ajnan unu solvon; aŭ trovi ĉiujn solvojn; aŭ trovi ĉiujn neekvivalentajn solvojn, t.e. kiuj ne estas produkteblaj unuj el aliaj per simplaj rotacioj aŭ simetriaj speguladoj.

En komputiko tiun problemon detale studis N. Wirth; ĝi estas interesa kiel ekzemplo pri la metodo de provoj kaj malavancoj kaj instrua pri maniero prezenti ŝaktabulajn aranĝojn per racie elektitaj datumstrukturoj.

Algoritma solvo pri la 8 damoj

Entute estas 64!÷(56!×8!), t.e. proks. 2∗∗32 lokadoj de La 8 damoj; do, estus malprudentaĵo ekzameni ĉiujn kombinojn por trovi la solvojn. La ĉi-suba programo damoj serĉos ĉiujn konvenajn aranĝojn per la metodo de provoj kaj malavancoj. Ĝi procedas rekursie: supozu, ke ĉiuj vertikaloj [1..x ], 1≤x<8 jam havas po unu bone lokitan damon; oni provu loki ankoraŭ unu damon sur la vertikalo x+1 (evidente, en la definitiva aranĝo sur ĉiu vertikalo kaj sur ĉiu horizontalo devas stari po ekzakte unu damo). Se la vertikalo x+1 malhavas taŭgan fakon, oni konstatas fiaskon; tiam necesas rekonsideri la decidon pri la lokado de la damo sur la vertikalo x — do, plenumi malavancon. Por decidi, ĉu koncerna fako estas sekura (taŭga), oportunas teni tri mallokajn vektorojn Buleajn pri la diagonaloj kreskaj (/) kaj sinkaj (\), kaj pri la vakaj horizontaloj, tiel ke fako (x,y) estas sekura SSE veras

horVak[y] KAJ sinko[x + y] KAJ kresko[x − y]

Paskala programo pri la 8 damoj

Ĉi-suba programo trovas ĉiujn solvojn.

PROGRAMO damoj(eligo); 
 
VAR horNro: TABELO [1..8] EL entjera; {damoj en la fakoj (x, horNro[x])} 
    horVak: TABELO [1..8] EL Bulea;   {horVak[y] SSE la vertikalo y vakas} 
    kresko: TABELO [-7..7] EL Bulea;  {la kreska (/) diag. x-y=i vakas} 
    sinko:  TABELO [2..16] EL Bulea;  {la sinka (\) diag. x+y=i vakas} 
    n:      entjera; 
 
PROCEDURO pretaTabulo; 
    VAR  x: entjera; 
STARTO 
    POR x:=1 SUPRE 8 FARU skribu(sgn(nro('a')-1+x):2, horNro[x]:-2); 
    skribuLin; 
FINO; 
 
PROCEDURO trovuHorizontalon(x: entjera); 
  VAR y:entjera; 
 
  PROCEDURO markuVakadon(vakstato: Bulea);      { ingita proceduro } 
    STARTO 
       horNro[x] := y; 
       horVak[y] := vakstato; 
       sinko[x + y] := vakstato; 
       kresko[x - y] := vakstato; 
    FINO; 
  STARTO                      { la korpo de "trovuHorizontalon": } 
    POR y := 1 SUPRE 8 FARU 
    SE horVak[y] KAJ sinko[x + y] KAJ kresko[x - y] TIAM STARTO 
    markuVakadon(malvero);              { okupu la fakon  (x, y) } 
    SE x < 8 TIAM trovuHorizontalon(x + 1) ALIE pretaTabulo; 
    markuVakadon(vero);               { malokupu la fakon (x, y) } 
  FINO 
FINO;                 { la proceduro "trovuHorizontalon" finitas } 
 
STARTO  { la korpo de la programo "damoj": } 
  POR n :=  1 SUPRE  8 FARU horVak[n] := vero;  { komencvalorizo } 
  POR n := -7 SUPRE  7 FARU kresko[n] := vero; 
  POR n :=  2 SUPRE 16 FARU sinko[n]  := vero; 
  trovuHorizontalon(1);                 { la radika procedurvoko } 
FINO.