My Java OO solution with Board class


  • 0
    Q
    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
                solutions.add(board.boardToString());
                return;
            }
            y++; //go to next level
        	List<Integer> availables = board.getAvailablePoisitions(y);
        	for (Integer _x: availables){
        		board.occupy(_x,y);
        		findPositions(_x, y, board, solutions);
        		board.free(_x,y);
        	}
        }
       
        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){
            			result.add(i);
            		}
            	}
            	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){
                occupy(x,y,false);
                queens.remove(new Queen(x,y));
            	Iterator<Queen> iter = queens.iterator(); //need to refresh the board
            	while (iter.hasNext()){
            		Queen q = iter.next();
            		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
                    squares[--i][--j]=occupy?1:0; 
                }
                i = x;
                j = y;
                while (i<nM1 && j<nM1){//South East line
                    squares[++i][++j]=occupy?1:0;
                }
                i = x;
                j = y;
                while (i>0 && j<nM1){ //South West line
                    squares[--i][++j]=occupy?1:0; 
                }
                i = x;
                j = y;
                while (i<nM1 && j>0){//North East line
                    squares[++i][--j]=occupy?1:0;
                }
                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){
            			    sb.append('Q');
            			    continue;
            			}
            			sb.append('.');
            		}
            		result[i]=sb.toString();
            	}
            	return result;
            }
        }
    

    }


Log in to reply
 

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