Write an algorithm to print all ways of arranging n queens on an n x n chess board so that none of them share the same row, column, or diagonal. In this case, "diagonal" means all diagonals, not just the two that bisect the board.
Notes: This problem is a generalization of the original one in the book.
Example:
Input: 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: 4 queens has following two solutions [ [".Q..", // solution 1 "...Q", "Q...", "..Q."], ["..Q.", // solution 2 "Q...", "...Q", ".Q.."] ]