private void search(int row, int n, ArrayDeque<Integer> columns,
                ArrayList<String[]> ans) {
            if (row == n) {
                ans.add(toSolution(columns));
                return;
            }
            for (int i = 0; i < n; i++) {
                if (isValid(row, i, columns)) {
                    columns.offerLast(i);
                    search(row + 1, n, columns, ans);
                    columns.removeLast();
                }
            }
        }