#include <stdio.h>
#include <conio.h>

#define NX 50
#define NY 50
#define DAME -1
#define FREI 0

int damen(int anzahl, int feld[NX][NY], int dimX, int dimY);

void setzeDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY);

void loescheDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY);

void initFeld(int feld[NX][NY], int dimX, int dimY);

void ausgabeFeld(int feld[NX][NY], int dimX, int dimY);

int main()
{
	int feld[NX][NY];

   int anzahl, dimX, dimY;

   printf("Wie gross soll das Feld sein (x,y)?\n");
   scanf("%d %d", &dimX, &dimY);
   printf("Wie viele Damen?\n");
   scanf("%d", &anzahl);

   initFeld(feld,dimX,dimY);

   if(damen(anzahl,feld,dimX,dimY)==1)
	   ausgabeFeld(feld,dimX,dimY);
   else
   	printf("Keine Lösung!\n");

   getch();
}

void initFeld(int feld[NX][NY], int dimX, int dimY)
{
	int x, y;
   for (y = 0; y <= dimY -1; ++y)
   	for (x = 0; x <=dimX-1; ++x)
      	feld[x][y] = FREI;
}

void ausgabeFeld(int feld[NX][NY], int dimX, int dimY)
{
	int x, y;

   printf("\n Feld: \n");
   for (y = 0; y <= dimY -1; ++y) {
   	for (x = 0; x <=dimX-1; ++x)
      	printf(" %3d", feld[x][y]);
      printf("\n");
   }
}


void setzeDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY)
{
	int x, y;

   for (x=0; x < dimX; ++x)
   	++feld[x][posY];

   for (y=0; y < dimY; ++y)
   	++feld[posX][y];

   if (posX + posY <= dimX -1) {
   	x = 0;
      y = posY+posX;
   	}
   else {
   	y = dimY -1;
      x = posX - (y-posY);
      }
   while (y >= 0 && x <= dimX-1) {
   	++feld[x][y];
      ++x;
      --y;
      }

   if (posX >= posY ) {
   	y = 0;
      x = posX-posY;
   	}
   else {
   	x = 0;
      y = posY - posX;
      }
   while (x <= dimX -1 && y <= dimY-1) {
   	++feld[x][y];
      ++x;
      ++y;
      }

   feld[posX][posY] = DAME;

}

void loescheDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY)
{
	int x, y;

   for (x=0; x < dimX; ++x)
   	--feld[x][posY];

   for (y=0; y < dimY; ++y)
   	--feld[posX][y];

   if (posX + posY <= dimX -1) {
   	x = 0;
      y = posY+posX;
   	}
   else {
   	y = dimY -1;
      x = posX - (y-posY);
      }
   while (y >= 0 && x <= dimX-1) {
   	--feld[x][y];
      ++x;
      --y;
      }

   if (posX >= posY ) {
   	y = 0;
      x = posX-posY;
   	}
   else {
   	x = 0;
      y = posY - posX;
      }
   while (x <= dimX -1 && y <= dimY-1) {
   	--feld[x][y];
      ++x;
      ++y;
      }

   feld[posX][posY] = FREI;
}

int damen(int anzahl, int feld[NX][NY], int dimX, int dimY)
{
	int x, y;

	if (anzahl == 0) return 1;
   else
   {
   for (y=0; y<dimY; ++y)
   	for (x=0; x<dimX; ++x)
      	if(feld[x][y] == 0)
         {
         	setzeDame(x,y,feld,dimX,dimY);
            if(damen(anzahl-1, feld, dimX, dimY)==1)
            	return 1;
            else
            	loescheDame(x,y,feld,dimX,dimY);
         }
    return 0;
    }
}



