My Java OO solution with Board class

  • 0
    public class Solution {
       public List<String[]> solveNQueens(int n) {
            List<String[]> solutions = new ArrayList<String[]>();
            Board board = new Board(n);
            findPositions(0,-1, board, solutions);
            return solutions;
        private void findPositions(int x, int y, Board board, List<String[]> solutions){
            int size = board.size();
            if (y == size-1){ //we managed to reach last level and found available spot
            y++; //go to next level
        	List<Integer> availables = board.getAvailablePoisitions(y);
        	for (Integer _x: availables){
        		findPositions(_x, y, board, solutions);
        private class Board{
            private class Queen{
            	int x;
            	int y;
            	public Queen(int x, int y){
            		this.x = x;
            		this.y = y;
            	public boolean equals(Object o){
            		Queen other = (Queen)o;
            		if (other.x == this.x && other.y == this.y){
            			return true;
            		return false;
            	public int hashCode(){return x*100+y;}
            int[][] squares;
            public Board(int n){
                squares = new int[n][n];
            public int size(){
                return squares.length;
            public List<Integer> getAvailablePoisitions(int y){
            	List<Integer> result = new ArrayList<Integer>();
            	for (int i=0;i<squares.length;i++){
            		if (squares[i][y] == 0){
            	return result;
            private Set<Queen> queens = new HashSet<Queen>();
            public void occupy(int x, int y){
                occupy(x, y, true);
                queens.add(new Queen(x,y));
            public void free(int x, int y){
                queens.remove(new Queen(x,y));
            	Iterator<Queen> iter = queens.iterator(); //need to refresh the board
            	while (iter.hasNext()){
            		Queen q =;
            		occupy(q.x, q.y, true);
            public void occupy(int x, int y, boolean occupy){
                int n = size();
                int nM1 = n-1;
                for (int i=0;i<n;i++){//horizontal and vertical lines
                    squares[i][y] = occupy?1:0;
                    squares[x][i] = occupy?1:0;
                int i = x;
                int j = y;
                while (i>0 && j>0){//North West line
                i = x;
                j = y;
                while (i<nM1 && j<nM1){//South East line
                i = x;
                j = y;
                while (i>0 && j<nM1){ //South West line
                i = x;
                j = y;
                while (i<nM1 && j>0){//North East line
                squares[x][y] = occupy?2:0;  //Unavailable squares represented by 1 or 2. Use 2 If there is Queen in it.
            public String[] boardToString(){//String Array representation of the board
            	int size = size();
            	String[] result = new String[size];
            	for (int i=0;i<size;i++){
            		StringBuilder sb = new StringBuilder();
            		for (int j=0;j<size;j++){
            			if (squares[i][j] == 2){
            	return result;


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.