LeetCodeN-Queens.java

/* Question Link: https://leetcode.com/problems/n-queens/
 * The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
 * Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
 * Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
 */






classSolution {
publicList<List<String>> solveNQueens(intn) {
List<List<String>> results = newArrayList<>();
if(n ==0) returnresults;
backtrace(results, newArrayList<String>(), 0, n, newboolean[n]);
returnresults;
 }

publicstaticvoidbacktrace(List<List<String>> result, List<String> list, intlevel, intn, boolean[] used){
if(level == n) result.add(newArrayList<String>(list));
else{
for(inti = 0; i < n; i++){
if(used[i]) continue;
if(isValid(list, level, i, n)){
list.add(createQueen(n, i));
used[i] = true;
backtrace(result, list, level + 1, n, used);
used[i] = false;
list.remove(list.size() - 1);
 }
 }
 }
 }
publicstaticbooleanisValid(List<String> list, introw, intcolumn, intn){
if(row > 0){
Stringcmp = list.get(row - 1);
for(inti = 0; i < row; i++)
if(list.get(i).charAt(column) == 'Q') returnfalse;
inttempRow = row;
inttempCol = column;
while(--tempRow >= 0 && --tempCol >= 0){
if(list.get(tempRow).charAt(tempCol) == 'Q') returnfalse;
 }
tempRow = row;
tempCol = column;
while(--tempRow >= 0 && ++tempCol <= n-1)
if(list.get(tempRow).charAt(tempCol) == 'Q') returnfalse;
 }
returntrue;
 }
privatestaticStringcreateQueen(intn, intindex){
StringBuildersb = newStringBuilder();
inti = 0;
for(; i < index; i++)
sb.append('.');
sb.append('Q');
for(++i; i < n; i++){
sb.append('.');
 }
returnsb.toString();
 }


}

/*contributed by: nilesh05apr */