import java.util.ArrayList;

import java.util.List;

public class Nqueue {

public List<List<String>> solveNQueens(int n) {

List<List<String>> res = new ArrayList<List<String>>();

/* one dimenttion array to represent the board

* each index in the array represents one row,

* each cell stores the column index of the target queen position */

int[] board = new int[n]; /* create a board */

putQueens(res, board, 0);

return res;

}

private void putQueens(List<List<String>> res, int[] board, int row){

if(row == board.length){

saveResults(res, board);

}else{

for(int col = 0; col < board.length; col++){

if(isLegal(board, row, col)){

board[row] = col;

putQueens(res, board, row + 1);

}

}

}

}

private boolean isLegal(int[] board, int row, int col){

for(int i = row-1; i>= 0; i--){

/* board[i] == col: check if any previous rows queen positions in the same colunm

* board[i] - col == Math.abs(row - i): check the diagonals difference */

if(board[i] == col || Math.abs(board[i] - col) == Math.abs(row - i)){

return false;

}

}

return true;

}

private void saveResults(List<List<String>> res, int[] board){

List<String> temp = new ArrayList<>();

for(int i = 0; i < board.length; i++){

StringBuilder sb = new StringBuilder();

for(int j = 0; j < board.length; j++){

if(j == board[i]){

sb.append('Q');

}else{

sb.append('.');

}

}

temp.add(sb.toString());

}

res.add(temp);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Nqueue oneNqueue=new Nqueue();

oneNqueue.solveNQueens(4);

}

}