### La 8 damoj

1. Algoritma solvo pri la 8 damoj
2. 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.