import java.util.Random;

/**
 * A recursive solver for the N Queens problem
 * 
 * @author gtowell
 * Created: April 2, 2021
 * **/

public class NQueens {
    // The board on which queens will be put
    private char[][] board;
    // the size of the board 
    private int size = 0;

    /**
     * Constructor.  Initialized the board
     * The board is an array of chars.  
     * . means it has never been tried, 
     * Q means a queen is there
     * - means it was tried at least once and rejected.
     * A a part of initialization, put a queen on a random square.
     * @param siz the size of the problem
     */
    public NQueens(int siz) {
        size = siz;
        board = new char[siz][siz];
        for (int i = 0; i < siz; i++) {
            for (int j = 0; j < siz; j++) {
                board[i][j] = '.';
            }
        }
        Random r = new Random();
        int row = r.nextInt(size);
        int col = r.nextInt(size);
        board[row][col] = 'Q';
    }

    /**
     * Start solving.
     * Just call the internal recursive solver.
     */
    public void doQueens() {
        doQueensUtil(0);
    }

    /**
     * return the numbe rof queens in the column
     * @param cc the column to be checked
     * @return the numbe rof queens in the column
     */
    private int checkCol(int cc) {
        int fc = 0;
        for (int row = 0; row < size; row++) {
            if (board[row][cc] == 'Q')
                fc++;
        }
        return fc;
    }

    /**
     * Check a diagonal
     * Works from row 0 down to size -1, going down one row at a time
     * @param strt the starting column number.  Note that this may be off of the board 
     * @param ci the direction to move ... columnwise  (+1 or -1)
     * @return the number of quees on the diagonal
     */
    int checkDiag(int strt, int ci) {
        int fc = 0;
        int row = 0;
        int col = strt;
        for (int i = 0; i < size; i++) {
            if (col >= 0 && col < size) {
                if (board[row][col] == 'Q')
                    fc++;
            }
            row++;
            col += ci;
        }
        return fc;
    }

    /**
     * Return true iff the board is legal.  That is, if no queen and take another
     * @return true iff the board is legal
     */
    private boolean OKBoard() {
        for (int c = 0; c < size; c++) {
            boolean badCol = checkCol(c) > 1;
            if (badCol)
                return false;
        }
        for (int d = -size; d < size; d++) {
            boolean baddiag = checkDiag(d, 1) > 1;
            if (baddiag)
                return false;
        }
        for (int d = 0; d < size * 2; d++) {
            boolean baddiag = checkDiag(d, -1) > 1;
            if (baddiag)
                return false;
        }
        return true;
    }
    
    /**
     * Return true if there already is a queen in the row.  This will only be true due to the 
     * initial, randomly placed queen.
     * @param row
     * @return
     */
    private boolean rowOccupied(int row) {
        for (int c = 0; c < size; c++) {
            if (board[row][c] == 'Q')
                return true;
        }
        return false;
    }
    
    /**
     * The recursaive solver.  This works by starting with the top row.
     * In that row work across the columns, placing a queen and recursing.If get back a bad, pick up the queen and move it one column
     * over.  In this way will eventually check every 
     * position in a row.
     * @param cc the row to work with
     * @return true if a solution has been found.  false otherwise
     */
    private boolean doQueensUtil(int roww) {
        if (roww >= size)
            return true;
        if (rowOccupied(roww))
            return doQueensUtil(roww + 1);
        for (int col = 0; col < size; col++) {
            board[roww][col] = 'Q';
            if (OKBoard()) {
                boolean v = doQueensUtil(roww + 1);
                if (v)
                    return true;
            } else {
                System.out.println("NOT OK");
                showBoard();
                System.out.println("NOT OK" + roww + " " + col);
            }
            board[roww][col] = '-';
        }
        return false;
    }
    
    public void showBoard() {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                System.out.print(board[r][c]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        int n = 8;
        NQueens nq = new NQueens(n);
        nq.doQueens();
        nq.showBoard();

    }
}