Damen implemented in C

/*
R.Lang
updated	96/12/25

N Damen Problem
Lösung basiert auf Algorhytmus von Karl Friedrich Gauss.

Algorhytmus:

1. Jede Dame wird in einer anderen Zeile positioniert.
   (n.te Dame in n.te Zeile). Herauszufinden bleibt, in
   welcher Spalte.

2. Backtracking Algorhytmus
	- Rücke Dame N um 1 Spalte vor.
	- Prüfe auf SCHACH (+Linien Kriterium)

	- Wiederhole dies, bis
		- keine Schach entsteht.
		- Fahre dann mit n„chster Dame N+1 nach gleichem Prinzip fort.
	  oder
		- die Dame ans Brettende ankommt.
		- Dann wird Dame N vom Brett genommen und vorherige Dame N-1 weitergerckt.
*/


/*-------------------- defines ---------------------------------------------*/
#define	MAXSeite 20
#define false 0
#define true !false
/*-------------------- includes --------------------------------------------*/
#include	<stdio.h>
#include	<time.h>
#include	<string.h>
/*#include	<process.h> */
#include	<stdlib.h>
#include	<time.h>
/*-------------------- Declare ---------------------------------------------*/
int		row[MAXSeite];				 	/* contains column position */
int		LINECHK=false;
int		HTML=false;
int		LIST=false;
static  time_t tt;

/*--------------------------------------------------------------------------*/
int 	GGT(a,b)
/*	returns GrӇter Gemeinsamer Teiler von a,b     							*/
int		a,
		b;
/*--------------------------------------------------------------------------*/
{
int c,n;
	a=abs(a);
	b=abs(b);
	if (b<a) {c=b;b=a;a=c;}
	for (n=1;n<=a+a;n++)
		if ((n*b/a)*a==n*b)
		return (a/n);  					/* found a value */
	return 1;							/* nothing found */
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

char *gettimestr()
{
        tt=time(NULL);
        return (asctime(localtime(&tt)));
}

/*--------------------------------------------------------------------------*/
void	display(n,sol)
int		n,								/* Max number of Queens */
		sol;						  	/* Solution number */
/*--------------------------------------------------------------------------*/
{
int		i,j;
	if (HTML) {
		
		if (sol%3==1) 	printf("<tr>");
		
		printf("<td>");
		printf("<b>L&ouml;sung %d</b>",sol);
		printf("\n<table border=4 cellspacing=0>\n");
		for (i=0;i<n;i++) {
			printf("<tr>\n");
			for (j=0;j<n;j++) {
				if ((i+j)%2==0) printf("\n\t<td bgcolor=#BBBBBB>"); else printf("\n\t<td bgcolor=#EEEEEE>");
				if (row[i]==j) printf("<b>&nbsp;D&nbsp;</b></td>"); else printf("&nbsp;</td>");
			}
			printf("\n</tr>\n");
		}
		printf("</table>\n");
		printf("</td>\n");
		//if (sol%3==1) 	printf("</tr>");
		
	
	}
	else {
		printf("\n\nLösung %d",sol);
		for (i=0;i<n;i++) {
			printf("\n");
			for (j=0;j<n;j++)
				if (row[i]==j) printf(" D "); else printf(" . ");
		}
	}
}

/*--------------------------------------------------------------------------*/
int 	QueensInLine(dx,dy,i,j,n,x)
int		dx,								/* Delta x between queens */
		dy,								/* Delta y between queens */
		i,          					/* Row of Queen 1 */
		j,								/* Row of Queen 2 */
		n,          					/* Max number of Queens */
		x;						   		/* Max Row to search */
/*--------------------------------------------------------------------------*/
/*
Example:
   dx = 4
   dy = 2
   i:			Q
				.
   j:			. . . . Q
						.   x
						. . . . ?   	row[j+dy]

									x
*/
{
int 	Dx, Dy,g;
	Dx=dx;
	Dy=dy;
	g=GGT(dx,dy);
	if (g>1) {dx=dx/g; dy=dy/g;}
	while ((j+dy)>=0 && (j+dy)<=x && (row[i]+dx) >= 0 && (row[i]+dx) < n)
	{
		if ((row[j+dy]) == (row[j]+dx))
		return -1;						/* At least 3 Queens are in Line */
										/* Try next Position */
		dx=dx+Dx;
		dy=dy+Dy;
	}
	return 0;					 		/* not in Line */
}

/*--------------------------------------------------------------------------*/
int		checkOK(x,n)
int		x,								/* Max Row to search */
		n;		  						/* Max number of Queens */
/*--------------------------------------------------------------------------*/
{
int		i,j;

	for (i=0;i<x;i++) {
		if (row[i] == row[x] ||
			row[i] == row[x]+x-i ||
			row[i] == row[x]-x+i )
			return 0;    				/* failed */
		}
	if (x>1&&LINECHK) {			 		/* 3 lines setup, so check if 3 queens in are in a line */
		for (i=0;i<x-1;i++) {
			for (j=i+1;j<x;j++) {
				if (QueensInLine(row[j]-row[i],j-i,i,j,n,x))
				return 0;				/* failed, 3 Queens in Line */
			}
		}
	}
	return -1;							/* ok */
}

/*--------------------------------------------------------------------------*/
int		nQueens(n)
int		n;								/* Max number of Queens */
/*--------------------------------------------------------------------------*/
{
int		ok,
		Solutions=0,					/* Solution counter */
		x=0;							/* active queen */
	row[0]=-1;
	while (x>=0 && x<n) {
		ok=0;
		while (!ok && row[x] < n-1)
			{
			row[x]++;					/* Queen number x GO in column */
			ok =checkOK(x,n);
			}
		if (!ok) x--;		     	  	/* try previous queen */
		else 	{
			if (x==n-1) {
				Solutions++;
				if (LIST) display(n,Solutions);
				x--;					/* continue with previous queen */
				}
			else {	x++;				/* try next queen */
				row[x]=-1;				/* Init queen position */
				}
			}
	}
	return Solutions;
}

/*--------------------------------------------------------------------------*/
void 	usage(exe)
char	*exe;							/* program name */
/*--------------------------------------------------------------------------*/
{
	printf("\n\n%s <Anzahl Damen (8)> <-list> <-line> <-usage> <-html>",exe);
	printf("\n\nBeispiele:\n%s 8      ",exe);
	printf("\tFindet alle Lösungen auf einem 8*8 Brett");
	printf("\n%s 8 -list",exe);
	printf("\tFindet alle Lösungen und zeigt sie");
	printf("\n%s 8 -line",exe);
	printf("\tFindet alle Lösungen mit dem zus„tzlichen Kriterium, dass die Damen nicht in einer Linie aufgestellt sein dürfen.");
	exit(1);
}

/*--------------------------------------------------------------------------*/
void 	main(argc,argv)
int		argc;
char	*argv[];
/*--------------------------------------------------------------------------*/
{
int 	i,n;

	if (argc==1) usage(argv[0]);
	for (i=0;i<argc;i++) {
		if (strstr(argv[i],"-list")) LIST=true;
		else if (strstr(argv[i],"-line")) LINECHK=true;
		else if (strstr(argv[i],"-html")) {HTML=true;LIST=true;}

		else if (strstr(argv[i],"-usage")) usage(argv[0]);
		else {
			if (i>2) {
		    printf("\nunknown option: %s\n",argv[i]); }
		}
	}
	n=atoi(argv[1]);
	if (HTML) 	printf("<HTML>\n<TITLE>Damen auf Schachbrett</TITLE><BODY>\n");
	
	if (n>0 && n<=MAXSeite)	{
		if (n==1)
			printf("<h3>%d Dame auf Schachbrett mit %d Feld<hr></h3>\n",n,n);
		else
			printf("<h3>%d Damen auf Schachbrett mit %d * %d Felder<hr></h3>\n",n,n,n);
		
		if (HTML) {
			printf("<table>\n");
			printf("\n</table>\n<b>%d</b> L&ouml;sungen gefunden f&uuml;r <b>%d</b> Damen\n",nQueens(n),n);
		}
		else {
			printf("\nStart:\t%s",gettimestr());
			printf("\n%d Lösungen gefunden\nfür %d Damen",nQueens(n),n);
		}
		if (LINECHK) printf(" (wobei die Damen nicht auf einer Linie aufgestellt sind.)");
		if (HTML) printf("<br>\n");	
		else
			printf("\nEnde:\t%s<hr>",gettimestr());
		}
	else
		printf("\nSorry, Anzahl der Damen ist sollte zwischen 1 und %d sein\nund nicht <%s>.\n",MAXSeite,argv[1]);

	if (HTML) printf("</BODY>\n");
	
}