N Queens Problem
by Isai Damier, Android Engineer @ Google

/******************************************************************
 * Author: Isai Damier
 * Title: N Queens Problem
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Description: This function solves the following classic
 *    problem: Given an n by n chessboard, place n queens on the
 *    board such that no queen is threatened.
 *
 * Technical Details: Since there can only be one queen per row, a
 *   one dimensional array is used to represent the board. The
 *   values inside the array represent the columns of the
 *   chessboard. As such, each element of the array can take a
 *   value between 0 and n-1.
 *
 *   The presented algorithm is based on the following personal
 *   observation. A queen on cell (x,y) dominates all cells in
 *   row x, in column y, or in any cell (j,k) where (j-k)==(x-y) or
 *   (j+k)==(x+y).
 *
 *   Beginning with the first row (i.e. x=0), the addQueen function
 *   is called recursively so as to dynamically adjust the board
 *   until all n queens are placed safely.
 *
 *****************************************************************/ 
 public int[] nQueenProblem(int n) {
  int[] queens = new int[n];
  addQueen(0, queens, n);
  return queens;
}

private void addQueen(int x, int[] queens, final int n) {
  for (int i = 0; i < n && 0 == queens[n - 1]; i++) {
    if (safeToAdd(x, i, queens)) {
      queens[x] = i;
      addQueen(x + 1, queens, n);
    }
  }
}

private boolean safeToAdd(int x, int y, int[] queens) {
  for (int i = 0; i < x; i++) {
    if (y == queens[i] || (x - y) == (i - queens[i])
            || (x + y) == (i + queens[i])) {
      return false;
    }
  }
  return true;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

  /**
   * Test of nQueenProblem method, of class Numbers.
   */
  @Test
  public void testNQueenProblem() {
    System.out.println("nQueenProblem");
    int n = 8;
    int[] expected = {0,4,7,5,2,6,1,3};
    Numbers chess = new Numbers();
    int[] queens = chess.nQueenProblem(n);
    assertTrue(Arrays.equals(expected, queens));
  }
}