package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LeetCode51 {

    /// 51. N-Queens
    /// https://leetcode.com/problems/n-queens/description/
    /// : O(n^n)
    /// : O(n)

    private boolean[] col;
    private boolean[] dia1;
    private boolean[] dia2;
    private ArrayList res;

    public List solveNQueens(int n) {

        res = new ArrayList();
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];

        LinkedList row = new LinkedList();
        putQueen(n, 0, row);

        return res;
    }

    // n, index
    private void putQueen(int n, int index, LinkedList row){

        if(index == n){
            res.add(generateBoard(n, row));
            return;
        }

        for(int i = 0 ; i < n ; i ++)
            // indexi
            if(!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
                row.addLast(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, row);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.removeLast();
            }

        return;
    }

    private List generateBoard(int n, LinkedList row){

        assert row.size() == n;

        ArrayList board = new ArrayList();
        for(int i = 0 ; i < n ; i ++){
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[row.get(i)] = 'Q';
            board.add(new String(charArray));
        }
        return board;
    }

    private static void printBoard(List board){
        for(String s: board)
            System.out.println(s);
        System.out.println();
    }

    public static void main(String[] args) {

        int n = 4;
        List res = (new LeetCode51()).solveNQueens(n);
        for(List board: res)
            printBoard(board);
    }
}