Rešitev: Šahovski konjiček s sestopanjem (Mathematica)

Iz MaFiRaWiki

Naloga: Šahovski konjiček s sestopanjem

Algoritem

SahovskiKonjicek[n_Integer, k_List] := Module[
    {A = n + 1, i = 0, j = 0, pot, koncnep, B = {0}, C, potezes, D, obmocje},
    pot = {{1, 1}};
    koncnep = {k};
    obmocje = n*n - 1;
    potezes = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
    D[l_List] := D[l] = Complement[Cases[Map[l + # &,potezes], {x_ /; 0 < x < A, y_ /; 0 < y < A}], koncnep];
    While[
      If[B == {}, B, First[B]] == 0 && i < 1,
      C = Complement[D[Last[pot]], pot];
      Which[
        C == {}, j++; pot = B〚-1〛; B = Drop[B, -1],
        Length[C] == 1, AppendTo[pot, If[C == {}, C, First[C]]];
        If[Length[pot] == obmocje, Which[Intersection[D[First[koncnep]], {Last[pot]}] == {Last[pot]}, i++]],
        True, B = Join[B, Map[Append[pot, #] &, Rest[C]]]; AppendTo[pot, If[C == {}, C, First[C]]]
        ]
      ];
    If[i == 1, Print["Obstaja vsaj ena resitev."], Print["Resitev ne obstaja."]]
    ]

Uporaba

SahovskiKonjicek[n_Integer,k_List] sprejme dva podatka:

(1) n=2, 4, 6, 8, 10, ... in n predstavlja velikost sahovnice n×n

(2) k={n, m}, m=1, 3, 5, ..., n-3,n-1 in k predstavlja crno polje v zgornji vrstici v katerem konjicek konca.

Konjicek zmeraj starta v polju {1,1}.

SahovskiKonjicek[4, {4, 1}] 
Resitev ne obstaja.

SahovskiKonjicek[4, {4, 3}]
Resitev ne obstaja.

SahovskiKonjicek[10, {10, 5}]
Obstaja vsaj ena resitev.
Osebna orodja