import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * Demonstration of Stochastic Local Search (SLS) approach to the N-Queens Puzzle.
 * @author Todd W. Neller
 *
 */
public class NQueensPuzzleSLS {

	private int numQueens; // number of queens
	private int[] queenCol; // column of a queen indexed by row
	
	/**
	 * Create a solved n-queens puzzle given n.
	 * @param numQueens the number of queens
	 */
	public NQueensPuzzleSLS(int numQueens) {
		this.numQueens = numQueens;
		queenCol = new int[numQueens];
		// (Start with queens in unique columns.)
		for (int r = 0; r < numQueens; r++)
			queenCol[r] = r;
		solve();
	}

	private ArrayList<Integer> getConflictRows() {
		ArrayList<Integer> conflictRows = new ArrayList<Integer>();
		for (int r = 0; r < numQueens; r++)
			for (int r2 = r + 1; r2 < numQueens; r2++)
				if (Math.abs(queenCol[r] - queenCol[r2]) == Math.abs(r - r2)) { // queenCol[r] == queenCol[r2] not needed given initialization and column swaps 
					conflictRows.add(r);
					conflictRows.add(r2);
				}
		return conflictRows;
	}
	
	/**
	 * Attempt to find a solution to the n-queens puzzle from the given row onward, returning whether or not the solution search was successful.
	 * @param row current row for placing a queen,
	 * @return whether or not the solution search was successful
	 */
	private boolean solve() {
		final int ITERATIONS = 1000000;
		Random random = new Random();
		
		// Start with a random state and evaluate it as our minimum so far.
		// (Start with queens in unique columns.)
		ArrayList<Integer> conflictRows = getConflictRows();
		int numConflicts = conflictRows.size();
		int[] bestQueenCol = queenCol.clone();
		int minConflicts = numConflicts;
		// Iterate:
		int iter = 0;
		for (; minConflicts > 0 && iter < ITERATIONS; iter++) {
			// Make a random "local" change to the state and evaluate it.
			// Swap the column assignments of a conflict row with another random conflict row / random row.
			int r1 = conflictRows.get(random.nextInt(conflictRows.size()));
			int r2 = r1;
			while (r2 == r1)
				r2 = random.nextDouble() < .8 ? conflictRows.get(random.nextInt(conflictRows.size())) : random.nextInt(numQueens);
			// swap columns of two rows (at least one with conflict)
			int tmp = queenCol[r1];
			queenCol[r1] = queenCol[r2];
			queenCol[r2] = tmp;
			ArrayList<Integer> newConflictRows = getConflictRows();
			int newNumConflicts = newConflictRows.size();
			// If the evaluation is >, return to the previous state.
			if (newNumConflicts > numConflicts) { // swap back
				tmp = queenCol[r1];
				queenCol[r1] = queenCol[r2];
				queenCol[r2] = tmp;
			}
			// Else accept the change, and, if the evaluation is the new minimum so far, copy the state.
			else {
				numConflicts = newNumConflicts;
				conflictRows = newConflictRows;
				if (numConflicts < minConflicts) {
					minConflicts = numConflicts;
					bestQueenCol = queenCol.clone();
				}
			}
		}
		// Report the best state found.
		System.out.printf("After %d iterations, f(%s) = %d\n", iter, Arrays.toString(bestQueenCol), minConflicts);
		return minConflicts == 0;
	}

	/**
	 * Return the column of the queen for a given row.
	 * @param row the given row
	 * @return the column of the queen for a given row
	 */
	public int getQueenColumn(int row) {
		return queenCol[row];
	}

	/**
	 * Return a String representation of the solution.
	 * @return a String representation of the solution
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int row = 0; row < numQueens; row++) {
			for (int col = 0; col < numQueens; col++)
				sb.append(queenCol[row] == col ? "Q " : "+ ");
			sb.append("\n");
		}
		if (getConflictRows().size() == 0)
			sb.append("Solution.\n");
		return sb.toString();
	}
	
	/**
	 * Prompt the user for a number of queens and print a corresponding n-queens puzzle solution.
	 * @param args (unused)
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.print("Queens? ");
		int numQueens = in.nextInt();
		in.close();
		if (numQueens <= 100)
			System.out.println(new NQueensPuzzleSLS(numQueens));
		else
			new NQueensPuzzleSLS(numQueens);

	}


}