import java.io.*;

/**
 * NQueens class: an object for a chess board for the N-Queens problem.
 * It solves itself with the solve() method and displays its output by
 * outputting to the console and by writing its result to a file.<br>
 * <br>
 * The AI keyword for this bad boy is <b>Depth-First Search</b>
 *
 * @author Darnell Arford
 * @version 1.0
 */

public class NQueens{
	private int n;                  // size of one dimension of the chess board
	private boolean solved;
	private int[] col;              // tell which row a piece is placed in the column at [index], -1 if none
	private boolean[] bDiagClear;   // tell whether a piece is in a certain diagonal from top left to bottom right
	private boolean[] fDiagClear;   // " " from top right to bottom left
	// An array is not needed to tell if there is a conflict in a row because the algotithm always
	// advances to the next row after placing a piece in a row.

	public NQueens(int size){
		n = size;	// this is n, the number of queens to solve for
		solved = false;// keeps track of whether a solution was found
		col = new int[size];
		bDiagClear = new boolean[2*size - 1];
		fDiagClear = new boolean[2*size - 1];
		for(int i=0; i<size; i++){
			col[i] = -1;
		}
		for(int i=0; i<bDiagClear.length; i++){
			bDiagClear[i] = fDiagClear[i] = true;
		}
	}// NQueens()

	/**********************************************************************
	 * Resets the NQueens object to the default values (unsolved)
	 */
	public void reset(){
		solved = false;
		for(int i=0; i<n; i++){
			col[i] = -1;
		}
		for(int i=0; i<bDiagClear.length; i++){
			bDiagClear[i] = fDiagClear[i] = true;
		}
	}// reset()

	/* *********************************************************************
	 * Gives a number representing the forward diagonal of the given coordinates
	 * @param c	Column of the space
	 * @param r Row of the space
	 */
	private int backDiag(int c, int r){
		return c-r+n-1;
	}

	/* *********************************************************************
	 * Gives a number representing the forward diagonal of the given coordinates
	 * @param c	Column of the space
	 * @param r Row of the space
	 */
	private int forDiag(int c, int r){
		return 2*n -2-c-r;
	}

	/**********************************************************************
	 * Solves the NQueens puzzle recursively
	 * @return true if solution was found
	 */
	public boolean solve(){
		return solveHelper(0, 0);
	}

	/* *********************************************************************
	 * Recursive Helper method for solve()
	 */
	private boolean solveHelper(int c, int r){
		if(r == n){
			solved = true;
			return true;
		}
		if(c == n){
			return false;
		}
		if(hasNoConflicts(c, r)){
			placePiece(c, r);
			boolean done = solveHelper(0, r+1);
			if(done) return true;
			else{
				removePiece(c, r);
				return solveHelper(c+1, r);
			}
		}
		else{
			return solveHelper(c+1, r);
		}
	} // solveHelper

	/* *********************************************************************
	 * Tests whether a piece at a given coordinate has any conflicts
	 */
	private boolean hasNoConflicts(int c, int r){
		boolean x = (
			(col[c]== -1) &&
			bDiagClear[backDiag(c, r)] &&
			fDiagClear[forDiag(c, r)]
		);
		return x;
	}

	/* *********************************************************************
	 * Places a piece and adds its value to the arrays keeping track of diagonals
	 */
	private void placePiece(int c, int r){
		col[c] = r;
		bDiagClear[backDiag(c, r)] = false;
		fDiagClear[forDiag(c, r)] = false;
	}

	/* *********************************************************************
	 * Removes a piece for a spot and takes away its value from the arrays
	 * keeping track of the diagonals
	 */
	private void removePiece(int c, int r){
		col[c] = -1;
		bDiagClear[backDiag(c, r)] = true;
		fDiagClear[forDiag(c, r)] = true;
	}

	/**********************************************************************
	 * Prints the solution to the console
	 */
	public void print(){
		for(int r=0; r<n; r++){
			for(int c=0; c<n; c++){
				if(col[c] == r)
					System.out.print("Q ");
				else System.out.print("# ");
			}
			System.out.println();
		}
	}// print()

	/**********************************************************************
	 * Writes the solution to a file
	 * @param time	Time taken for the solve algorithm to run
	 */
	public void writeToFile(long time){
		if(!solved){
			System.out.println("Can not write to file, solution not found");
		}else{
			try{
				File f = new File(".\\dfNQsol\\dpthfrstNQ_" + n + ".sol");
				PrintWriter out = new PrintWriter(new FileWriter(f));
				for(int i = 0; i<n; i++){
					for(int j = 0; j<n; j++){
						if (col[j] == i){
							out.print( j + " ");
						}
					}
				}
				out.println(-1);
				out.println(makeMessage(time));
				out.close();
			}catch(IOException e){
				System.out.println("Problem writing solution to file");
			}
		}
	}// writeToFile()

	private String makeMessage(long time){
		String s = "<html><h4>";
		long hours = time/3600000;
		long millis = time%3600000;
		long minutes = millis/60000;
		millis = millis%60000;
		long seconds = millis/1000;
		millis = millis%1000;

		s = s.concat("This is a solution to the N-Queens problem for n equal to " + n +
			".<br>This solution was found with a recursive depth-first search.<br>");

		if(time==0){
			s = s.concat("It took less than a millisecond to find this solution");
		}else{
			s = s.concat("It took ");
			if(hours>0){
				s = s.concat(hours + " hours ");
			}
			if(minutes>0){
				s = s.concat(minutes + " minutes ");
			}
			if(seconds>0){
				s = s.concat(seconds + " seconds ");
			}
			if(millis>0){
				s = s.concat(millis + " milliseconds ");
			}
			s = s.concat(" to find this solution.");
		}
		s = s.concat("</h4></html>");
		return s;
	}

	/**********************************************************************
	 * MAIN METHOD: RUN THIS TO RUN THE PROGRAM AND GET RESULTS!
	 * @param args[0] The number of queens to solve for
	 */
	public static void main(String[] args){
		int size; // number of queens

		try{
			size = java.lang.Integer.parseInt(args[0]);
		}catch(ArrayIndexOutOfBoundsException e){
			System.out.println("You have to enter an integer argument equal to the number of queens");
			return;
		}

		NQueens nq = new NQueens(size);
		long start = System.currentTimeMillis();
		boolean foundSolution = nq.solve();
		long tot_time = System.currentTimeMillis() - start;
		nq.print();
		nq.writeToFile(tot_time);
		System.out.println("\nTotal time to complete: " + tot_time + " milliseconds");

	} // main()
}// NQueens class