N Queens Optimaztion

http://algorithms.tutorialhorizon.com/backtracking-n-queens-problem-better-solution/

Solu­tion matrix takes O(N²) space. We can reduce it to O(N). We will solve it by tak­ing one dimen­sional array and con­sider solution[1] = 2 as “Queen at 1st row is placed at 2nd column.

result[i]=j means queen at i-th row is placed at j-th column.

Check if Queens placed at (x1, y1) and (x2,y2) are safe

• x1==x2 means same rows,
• y1==y2 means same columns
• |x2-x1|==|y2-y1| means they are placed in diagonals.

	static int[] result; // this array will store the resul
	// result[i]=j; means queen at i-th row is placed at j-th column.
	// Queens placed at (x1, y1) and (x2,y2)
	// x1==x2 means same rows, y1==y2 means same columns, |x2-x1|==|y2-y1| means
	// they are placed in diagonals.
	public boolean canPlace(int x2, int y2) {
	// This function will check if queen can be placed (x2,y2), or we can
	// say that Can queen at x2 row is placed at y2 column.
	// for finding the column for x2 row, we will check all the columns for
	// all the rows till x2-1.
	for (int i = 0; i < x2; i++) {
	//result[i] == y2 => columns are same
	//|i - x2| == |result[i] - y2| => in diagonals.
	if ((result[i] == y2)
	|| (Math.abs(i - x2) == Math.abs(result[i] - y2))) {
	return false;
	}
	}
	return true;
	}
	public void placeQueens(int x, int size) {
	for (int i = 0; i < size; i++) {
	//check if queen at xth row can be placed at i-th column.
	if (canPlace(x, i)) {
	result[x] = i; // place the queen at this position.
	if (x == size - 1) {
	System.out.println("Order of " + size + " queens"
	+ Arrays.toString(result));
	}
	placeQueens(x + 1, size);
	}
	}
	}

http://rosettacode.org/wiki/N-queens_problem#Java

  private static int[] b = new int[8];
  private static int s = 0;
 
  static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
      int t = b[y - i];
      if (t == x ||
          t == x - i ||
          t == x + i) {
        return true;
      }
    }
 
    return false;
  }
 
  public static void putboard() {
    System.out.println("\n\nSolution " + (++s));
    for (int y = 0; y < 8; y++) {
      for (int x = 0; x < 8; x++) {
        System.out.print((b[y] == x) ? "|Q" : "|_");
      }
      System.out.println("|");
    }
  }
 
  public static void main(String[] args) {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
      do {
        b[y]++;
      } while ((b[y] < 8) && unsafe(y));
      if (b[y] < 8) {
        if (y < 7) {
          b[++y] = -1;
        } else {
          putboard();
        }
      } else {
        y--;
      }
    }
  }

8 Queens Solver in 31 Bits