Problém dám na šachovnici.

Program rieši úlohu, ako rozmiestniť na šachovnici daný počet dám, tak aby sa neohrozovali.

#include <cstdlib>
#include <iostream>
#define N 8;

const int n=8;

using namespace std;

bool st[n]; // obsadenie stlpcov;
bool u1[2*n+1];
bool u2[2*n+1]; //-n+1..n-1;
int stlpec[n];
int poc;

void ini(void)
{
     for(int i=0;i<n;i++)
     {
        st[i]=true;
        stlpec[i]=0;
     }
     for(int i=0;i<2*n;i++) u1[i]=u2[i]=true;
}

void vypis(void)
{
     for(int i=0;i<n;i++)
     {
        for(int j=0;j<n;j++)
        {
           if(stlpec[i]==j)cout<<"D";
           else cout<<" ";
        }
        cout<<endl;
     }
     poc++;
}

void hladaj(int r,int s)
{
    stlpec[r]=s;
    st[s]=false;u1[s+r]=false;u2[s-r+n+1]=false;
    if(r==n-1)vypis();
    else 
    for(int i=0;i<n;i++)
    {
       if(st[i]==true&&u1[i+r+1]==true&&u2[i-(r+1)+n-1]==true)hladaj(r+1,i);
    }
    st[s]=true;u1[s+r]=true;u2[s-r+n]=true;
}

void ries(void)
{
   for(int i=0;i<n;i++)
   {
      hladaj(0,i);
   }
}

int main(int argc, char *argv[])
{
    ini();
    ries();
    cout<<poc;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Informácie:

Autor: danciwo
www: http://www.danciwo.net
Kategória: Algoritmy
Jazyk: C/C++
Dátum:10/21/2009 1:10:35 PM