#define N 8 
#define FREE N

int row[N];
int down[2*N];
int up[2*N];
int top; 			// Top of the trail stack
int qu[N];

2lp_main()
{
	initial_markings();
	solve_queens();
	output();
}

initial_markings()
{
	and(int k=0;k<N;k++) 
		row[k] = FREE;
	and(int k=0;k<2*N;k++) 
		down[k] = FREE;
	and(int k=0;k<2*N;k++) 
		up[k] = FREE;
	top = -1; 				// Initial stack is empty
}

check_free(int i,j)
{
	row[i] == FREE; 			// Check row free
	down[i-j+N] == FREE; 		// Check diagonals free
	up[i+j] == FREE;
}

label(int i,j,tag)				// row i, column j, label tag
{
	row[i] = tag; 						
	down[i-j+N] = tag; 						
	up[i+j] = tag;
}

solve_queens()
{
	// For jj < j, the queen in column jj is 
	// safely placed in the row and diagonals labeled jj
	// All unoccupied rows and diagonals are labeled FREE
	and(int j=0;j<N;j++) 						// j th column
		// top is equal to j-1
		// Placing queen j in rows 0,...,i-1 
		// does not lead to a solution
		or(int i=0;i<N;i++){ 					// If i==N, decrement j
			and(int k=top;k>=j;k--) 				// Untrail
				label(qu[k],k,FREE);
			check_free(i,j); 					//Check row i and diagonals
			label(i,j,j);						// Place j in row i
			qu[j] = i;							// Trail this fact
			top = j;							// Advance top of trail stack
		}
}

output()
{
	and(int i=0;i<N;i++)
		printf("The queen in row %d is in column %d \n", i, row[i]);
}
 