Rešitev: Problem n dam s sestopanjem (Mathematica)

Iz MaFiRaWiki

Naloga: Problem n dam s sestopanjem


Najprej povečamo sistemsko nastavitev RecursionLimit.

$RecursionLimit = 100000;

Rešitve shranjujemo v globalno spremenljivko.

Clear[resitve]
resitve = {};

Funkcija tolcena1 vrne tri tolčena polja (polje v isti vrstici in dve diagonalni polji) zaradi i-te dame, ki je v xi-ti vrstici, v (m+xi)-tem stolpcu.

Funkcija tolcena vrne vsa tolčena polja v (m+xi)-tem stolpcu, ki so tolčena od m-1 dam levo od tega stolpca.

Clear[tolcena1, tolcena]
tolcena1[xi_, i_, m_] := {xi, xi + m + 1 - i, xi - m - 1 + i}
tolcena[x_, m_] := Union[Flatten[Table[tolcena1[x[[i]], i, m], {i, m}]]]

Katera polja v (m+xi)-tem stolpcu so še prosta, če upoštevamo m-1 postavljenih dam levo od tega stolpca?

Clear[prosta]
prosta[n_, x_, m_, pmin_] := Complement[Range[pmin + 1, n], tolcena[x, m]]

Uporabimo sestopanje. Naj bo n velikost šahovnice in x delna rešitev (vsebuje lokacije / stolpce dam, ki so postavljene do tega koraka).

Clear[dame, konec]
dame[n_Integer:8] := Module[{}, resitve = {}; dame[n, {}, 0, Range[n]]]
dame[n_, x_, 0, {}] := konec
dame[n_, x_, m_, {}] := Module[{},
    If[n == m, AppendTo[resitve, x]; Print[x]];
    dame[n, Drop[x, -1], m - 1, prosta[n, Drop[x, -1], m - 1, Last[x]]]     
    ]
dame[n_, x_, m_, d_] := Module[{}, dame[n, Append[x, First[d]], m + 1, prosta[n, Append[x, First[d]], m + 1, 0]]]

Naredimo šahovnico.

Clear[sahovnica]
sahovnica[n_Integer:8] := sahovnica[n, {}]
sahovnica[n_Integer:8, {}] := Table["[ ]", {i, 1, n}, {j, 1,
 n}] // MatrixForm
sahovnica[n_Integer:8, l_List] := Module[{},
    Transpose[Map[ReplacePart[Table["[ ]", {n}], "[*]", #] &, l ]] // MatrixForm
    ]

Primeri

Problem osmih dam

In[18]:= dame[8]

{1,5,8,6,3,7,2,4}
{1,6,8,3,7,4,2,5}
{1,7,4,6,8,2,5,3}
{1,7,5,8,2,4,6,3}
{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}
{2,8,6,1,3,5,7,4}
{3,1,7,5,8,2,4,6}
{3,5,2,8,1,7,4,6}
{3,5,2,8,6,4,7,1}
{3,5,7,1,4,2,8,6}
{3,5,8,4,1,7,2,6}
{3,6,2,5,8,1,7,4}
{3,6,2,7,1,4,8,5}
{3,6,2,7,5,1,8,4}
{3,6,4,1,8,5,7,2}
{3,6,4,2,8,5,7,1}
{3,6,8,1,4,7,5,2}
{3,6,8,1,5,7,2,4}
{3,6,8,2,4,1,7,5}
{3,7,2,8,5,1,4,6}
{3,7,2,8,6,4,1,5}
{3,8,4,7,1,6,2,5}
{4,1,5,8,2,7,3,6}
{4,1,5,8,6,3,7,2}
{4,2,5,8,6,1,3,7}
{4,2,7,3,6,8,1,5}
{4,2,7,3,6,8,5,1}
{4,2,7,5,1,8,6,3}
{4,2,8,5,7,1,3,6}
{4,2,8,6,1,3,5,7}
{4,6,1,5,2,8,3,7}
{4,6,8,2,7,1,3,5}
{4,6,8,3,1,7,5,2}
{4,7,1,8,5,2,6,3}
{4,7,3,8,2,5,1,6}
{4,7,5,2,6,1,3,8}
{4,7,5,3,1,6,8,2}
{4,8,1,3,6,2,7,5}
{4,8,1,5,7,2,6,3}
{4,8,5,3,1,7,2,6}
{5,1,4,6,8,2,7,3}
{5,1,8,4,2,7,3,6}
{5,1,8,6,3,7,2,4}
{5,2,4,6,8,3,1,7}
{5,2,4,7,3,8,6,1}
{5,2,6,1,7,4,8,3}
{5,2,8,1,4,7,3,6}
{5,3,1,6,8,2,4,7}
{5,3,1,7,2,8,6,4}
{5,3,8,4,7,1,6,2}
{5,7,1,3,8,6,4,2}
{5,7,1,4,2,8,6,3}
{5,7,2,4,8,1,3,6}
{5,7,2,6,3,1,4,8}
{5,7,2,6,3,1,8,4}
{5,7,4,1,3,8,6,2}
{5,8,4,1,3,6,2,7}
{5,8,4,1,7,2,6,3}
{6,1,5,2,8,3,7,4}
{6,2,7,1,3,5,8,4}
{6,2,7,1,4,8,5,3}
{6,3,1,7,5,8,2,4}
{6,3,1,8,4,2,7,5}
{6,3,1,8,5,2,4,7}
{6,3,5,7,1,4,2,8}
{6,3,5,8,1,4,2,7}
{6,3,7,2,4,8,1,5}
{6,3,7,2,8,5,1,4}
{6,3,7,4,1,8,2,5}
{6,4,1,5,8,2,7,3}
{6,4,2,8,5,7,1,3}
{6,4,7,1,3,5,2,8}
{6,4,7,1,8,2,5,3}
{6,8,2,4,1,7,5,3}
{7,1,3,8,6,4,2,5}
{7,2,4,1,8,5,3,6}
{7,2,6,3,1,4,8,5}
{7,3,1,6,8,5,2,4}
{7,3,8,2,5,1,6,4}
{7,4,2,5,8,1,3,6}
{7,4,2,8,6,1,3,5}
{7,5,3,1,6,8,2,4}
{8,2,4,1,7,5,3,6}
{8,2,5,3,1,7,4,6}
{8,3,1,6,2,5,7,4}
{8,4,1,3,6,2,7,5}
Out[18]= konec


Koliko je rešitev?

In[19]:= resitve//Length
Out[19]= 92

Poglejmo si prvo rešitev.

sahovnica[8, resitve[[1]]]
\begin{bmatrix} *& & & & & & & \\  & & & &*& & & \\  & & & & & & &*\\  & & & & &*& & \\  & &*& & & & & \\  & & & & & &*& \\  &*& & & & & & \\  & & &*& & & & \\ \end{bmatrix}

Če imamo v prvem stolpcu damo v osmi vrstici, potem so v drugem stolpcu tolčena tri polja (7,8 in 9).

In[21]:= tolcena1[8,1,1]
Out[21]= {8,9,7}

V zadnjem stolpcu je samo eno prosto mesto (vsa ostala polja so tolčena).

In[22]:= tolcena[{8,4,1,3,6,2,7,5},7]
Out[22]= {-4,-2,-1,0,1,2,3,4,6,7,8,9,10,15}

In[23]:= prosta[8,{8,4,1,3,6,2,7,5},7,0]
Out[23]= {5}
Osebna orodja