#include <us.h>

typedef unsigned int boolean;
#define FALSE 0
#define TRUE  1


typedef struct s{
    int *board,row;
}board_s;

int NQ;
int numSolutions = 0;
int checked = 0;

boolean legal(),solve();
main()
{
    int i,*board;
    unsigned long endTime,startTime;
    
    printf("enter board size> ");
    scanf("%d",&NQ);
    board = (int *) malloc(NQ*sizeof(int));

    for(i=0;i<NQ;i++)
	board[i] = -1;

    startTime = GetRtc();
    if (solve(board,0)){
/*	printf("solution found:\n");
	for(i=0;i<NQ;i++)
	    printf("row = %d  col = %d\n",i,board[i]);
*/
    }
/*    else
	printf("no solution found\n"); */

    endTime = GetRtc();
    printf("number of solutions = %d\n",numSolutions);
    printf("number checked = %d\n", checked);
    printf("time = %.1f\n",(endTime-startTime)*62.5);
}

boolean
solve(board,row)
     int *board,row;
{
    register int t;
    for(;;){
	do{
	    t=(++(board[row]));
	} while ((t < NQ) && !legal(board,row));
	if (NQ==t){
	    board[row] = -1;
	    return FALSE;
	}
	else if (row==NQ-1){
	    numSolutions++;
	    /* return TRUE; */
	}
	    
	else if (solve(board,row+1))
	    ;
	    /* return TRUE; */
    }
    
}


boolean
legal(board,row)
     int *board,row;
{
    register int col = board[row];
    register int ldiag = col - row;
    register int rdiag = col + row;
    register int i,t;

    checked++;

    for (i=0;i<row;i++){
	if (((t=board[i])==col)||
	    (t-i==ldiag)||
	    (t+i==rdiag))
	    return FALSE;
    }
    return TRUE;
}