LeetCode 51: 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.."]
]

public class Solution {
    private int num; // Number of line of board
    private List<String[]> result;
    private int[] x; // Position of queens
    
    public List<String[]> solveNQueens(int n) {
        // Backtracking problem
        // Construct a (n+1) level tree: The ith (i = 0,1,...,n) level has n^i nodes
        // x[i] also represents there is a queen on the ith row x[i]th column
        num = n;
        result = new LinkedList<>();
        x = new int[n];
        
        backTrack(0);
        
        return result;
    }
    
    private void backTrack(int cnt)
    {
        if (cnt == num) // Passed the last row and get a possible solution
        {
            String[] str = new String[num];
            
            for (int i = 0; i < num; i++)
            {
                str[i] = "";
                
                for (int j = 0; j < num; j++)
                    if (x[i] == j)
                        str[i] += "Q";
                    else
                        str[i] += ".";
            }
            
            result.add(str);
        }
        else
        {
            for (int i = 0; i < num; i++) // Column traversal of (cnt)th row
            {
                x[cnt] = i;
                
                // Test if x[cnt] can be positioned
                if (place(cnt))
                    backTrack(cnt+1);
            }
        }
    }
    
    // Constrained rule: The queens can't be put in the same row, column or line with slope (-1 or +1)
    private boolean place(int j)
    {
        for (int i = 0; i < j; i++)
            if (x[i]==x[j] || Math.abs(i-j)==Math.abs(x[i]-x[j]))
                return false;
                
        return true;
    }
}