import java.util.Random;

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

public class NQueens {
    
    /**
     * Create a new N Quees chessboard
     * @param size   the size of the board to be created (8 is normal)
     * @param initial the number of queens to put onto the board
     * @return the board so created.
     */
    private char[][] newBoard(int size, int initial) {
        char[][] board = new char[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                board[i][j] = '.';
            }
        }
        Random r = new Random();
        for (int i = 0; i < initial; i++) {
            int row = r.nextInt(size);
            int col = r.nextInt(size);
            board[row][col] = 'A';
        }
        return board;
    }

    /**
     * Start solving.
     * Just call the internal recursive solver.
     * @param board the initial board to solve
     * @return the solution, or null is no solution
     */
    public char[][] doQueens(char[][] board) {
        return doQueensUtil(board, 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(char[][] board, int cc) {
        int fc = 0;
        for (int row = 0; row < board.length; row++) {
            if (board[row][cc] == 'Q' || board[row][cc] == 'A')
                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(char[][] board, int strt, int ci) {
        int fc = 0;
        int row = 0;
        int col = strt;
        for (int i = 0; i < board.length; i++) {
            if (col >= 0 && col < board.length) {
                if (board[row][col] == 'Q' || board[row][col] == 'A')
                    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(char[][]board) {
        for (int c = 0; c < board.length; c++) {
            boolean badCol = checkCol(board, c) > 1;
            if (badCol)
                return false;
        }
        for (int d = -board.length; d < board.length; d++) {
            boolean baddiag = checkDiag(board, d, 1) > 1;
            if (baddiag)
                return false;
        }
        for (int d = 0; d < board.length * 2; d++) {
            boolean baddiag = checkDiag(board, 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(char[][] board, int row) {
        for (int c = 0; c < board.length; c++) {
            if (board[row][c] == 'Q' || board[row][c] == 'A')
                return true;
        }
        return false;
    }
    

    /**
     * Copy the chess board and add a queen to the copy
     * @param oldBoard  the board to be copied
     * @param qRow row for the new queen
     * @param qCol col for the new qieen
     * @return the new board
     */
    private char[][] copyBoard(char[][] oldBoard, int qRow, int qCol) {
        char[][] board = new char[oldBoard.length][oldBoard[0].length];
        for (int r = 0; r < oldBoard.length; r++) {
            for (int c = 0; c < oldBoard[r].length; c++) {
                board[r][c] = oldBoard[r][c];
            }
        }
        board[qRow][qCol] = 'Q';
        return board;
    }
    
    /**
     * The recursaive solver.  This works by starting with the top row.
     * In that row work across the columns, recursing on a copy of the
     * bioard with a queen put in the column
     * @param board the current board
     * @param cc the row to work with
     * @return true if a solution has been found.  false otherwise
     */
    private char[][] doQueensUtil(char[][] board, int roww) {
        if (roww >= board.length)
            return board;
        if (rowOccupied(board, roww))
            return doQueensUtil(board, roww + 1);
        for (int col = 0; col < board[roww].length; col++) {
            if (OKBoard(board)) {
                // recurse; going to the next row.
                char[][] v = doQueensUtil(copyBoard(board, roww, col), roww + 1);
                if (v!=null)
                    return v;
            } else {
                //System.out.println("NOT OK");
                //showBoard(board);
                //System.out.println("NOT OK" + roww + " " + col);
            }
        }
        return null;
    }
    
    public void showBoard(char[][] board) {
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[r].length; c++) {
                System.out.print(board[r][c]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        NQueens nq = new NQueens();
        char[][] startBoard = nq.newBoard(8, 2);
        char[][] rslt = nq.doQueens(startBoard);
        if (rslt != null) {
            System.out.println("SOLVED!!!!");
            nq.showBoard(rslt);
        } else {
            System.out.println("NO Solution");
            nq.showBoard(startBoard);
        }

    }
}