lab2_Backtraking

Backtraking
Feladatok:

Helyezzünk el n királynőt egy nxn méretű sakktáblán úgy, hogy ne üssék egymást (ne legyenek ugyanabba a sorba, oszlopba, illetve átlóba.) ( Pszeudokód )
Generáljuk ki az {1, 2, ... , n} halmaz:

p-szeres descartes szorzatának elemeit

pl. n=3, p=2: {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}

összes permutációit

pl. n=3: {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}

p-ed rendű variációit

pl. n=3, p=2: {(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)}

p-ed rendű kombinációit

pl. n=3, p=2: {(1,2), (1,3), (2,3)}

összes részhalmazát

pl. n=3: { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

összes particióját

pl. n=3:
{1,2,3}
{1,2}{3}
{1,3}{2}
{1}{2,3}
{1}{2}{3}

Adottak a₁, a₂, ... , a_n értékű pénzérmék, mindenik típusból bármennyi. Írjuk ki az összes lehetséges módot, ahogy egy s összeg kifizethető ezen pénzérmék segítségével.

Fel.1.

backtracking (x[], n, k)
   ha megoldas (x, n, k) akkor kiir (x, k-1) // ha k==n
   kulonben
      minden i = 0..n-1 végezd el
         // előállítjuk elő x[k]-ban az Ak halmaz i-edik elemét:
         x[k] = i
         ha megfelelo(x, k) akkor backtracking (x, n, k+1)
       vege ha
      vege minden
   vege ha

megfelelo(x[],k)
    minden i=0..k-1 végezd
    //ne legyenek ugyanabban az oszlopban és ugyanabban az átlón
    ha x[i] == x[k] vagy (k - i) == abs( x[k] - x[i]) akkor
      return HAMIS
    vege ha
    vege minden
return IGAZ
vege megfelelo