N Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Use backtrack. Use a 2-D boolean matrix to store whether a cell has been placed a queen.

01 public ArrayList<String[]> solveNQueens(int n) {
02     char[][]board =new char[n][n];
03     boolean[][]visited=new boolean[n][n];
04     for(int i=0;i<n;i++)
05     {
06         for(int j=0;j<n;j++)
07         {
08             board[i][j]='.';
09         }
10     }
11     ArrayList<String[]>results=new ArrayList<String[]>();
12     placeQueen(results,board,visited,0);
13     return results;
14   
15 }
16 
17 public void placeQueen(ArrayList<String[]>results,  char[][]board, boolean [][]visited, int row)
18 {
19     if(row==board.length)
20     {
21         String [] str=new String[board.length];
22         for(int i=0;i<board.length;i++)
23         {
24             str[i]=new String(board[i]);
25         }
26         results.add(str);
27     }
28     else
29     {
30         for(int j=0;j<board.length;j++)
31         {
32             if(isValid(visited,row,j))
33             {
34                 board[row][j]='Q';
35                 visited[row][j]=true;
36                 placeQueen(results,board,visited,row+1);
37                 visited[row][j]=false;
38                 board[row][j]='.';
39             }
40           
41         }
42     }
43 }
44 public boolean isValid(boolean [][]visited, int x, int y)
45 {
46     for(int i=0;i<x;i++)
47     {
48         if(visited[i][y]==true)
49             return false;
50     }
51     for(int i=0;i<x;i++)
52     {
53         for(int j=0;j<visited.length;j++)
54         {
55             if(visited[i][j]==true)
56             {
57                 if((x-i)==Math.abs(y-j))
58                     return false;
59             }
60           
61         }
62     }
63     return true;
64 }