// uC example 11 -- n queens problem * 1996-12-20, 2001-03-18

// Finding the 724 solutions to the 10 queens problem takes 2.5
// seconds with an abstract machine implemented in Java and executed
// on Sun JDK 1.3 Hotspot on a 600 MHz AMD 7 running Linux.
// Generating and then executing JVM bytecode using HotSpot is faster
// by a factor of 10 --- and also faster than a functional
// implementation in Moscow ML.

void main(int n) {
  int i; 
  int u;
  int used[100];
  int diag1[100];
  int diag2[100];
  int col[100];

  u = 1;
  while (u <= n) {
    used[u] = false;
    u = u+1;
  }

  u = 1;
  while (u <= 2 * n) {
    diag1[u] = diag2[u] = false;
    u = u+1;
  }

  i = u = 1;
  while (i > 0) {
    while (i <= n && i != 0) {
      while (u <= n && (used[u] || diag1[u-i+n] || diag2[u+i]))
	u = u + 1;
      if (u <= n) { // not used[u]; fill col[i] then try col[i+1]
	col[i] = u; 
	used[u] = diag1[u-i+n] = diag2[u+i] = true; 
	i = i+1; u = 1;
      } else {			// backtrack; try to find a new col[i-1]
	i = i-1;
	if (i > 0) { 
	  u = col[i]; 
	  used[u] = diag1[u-i+n] = diag2[u+i] = false; 
	  u = u+1;
	} 
      }
    }

    if (i > n) {                // output solution, then backtrack
      int j;
      j = 1;
      while (j <= n) {
	print col[j];  
	j = j+1;
      }
      println;
      i = i-1; 
      if (i > 0) { 
	u = col[i]; 
	used[u] = diag1[u-i+n] = diag2[u+i] = false; 
	u = u+1;
      }
    }
  }
}