//
// Eight-Queens Puzzle Written in Java
// Written by Tim Budd, January 1996
// revised for 1.3 event model July 2001
//
// Generalized for n queens by Will Clinger.
// Modified for COM 1204 assignment #6 by Will Clinger.
//
// Usage:
//   java QueenSolver n


import java.awt.*;
import java.awt.event.*;
import javax.swing.*;


abstract class QueenConstants {

    // width and height of each square of the board, in pixels

    static final int SQUARE_PIXELS = 50;

    // extra margin around board, in pixels

    static final int MARGIN_PIXELS = 140;

    // offsets in pixels for drawing a single queen

    static final int x1 = 5;
    static final int x2 = 15;
    static final int x3 = 25;
    static final int x4 = 35;
    static final int x5 = 45;

    static final int y1 = 45;
    static final int y2 = 35;
    static final int y3 = 25;
    static final int y4 = 20;
    static final int y5 = 5;

}


// FIXME: Inheriting from QueenConstants is a hack
// to reduce the number of qualified names.

class Queen extends QueenConstants {

    private static final int INITIAL_ROW = 0;
    private static final int INVISIBLE = 0;

    private final int n;                 // n x n chessboard
    private int row;                     // row 0 means off the board
    private int column;
    private Queen neighbor;              // queen in column to the left

    // this observer will be told when all solutions have been found
    private SolutionObserver observer;

    // Creates a queen that searches for a solution.

    Queen (int n, int c, Queen neighbor, SolutionObserver observer) {
	this.n = n;
	this.row = INITIAL_ROW;
	this.column = c;
	this.neighbor = neighbor;
	this.observer = observer;
    }

    // Creates a queen that remembers a solution.

    private Queen (int n, int row, int column, Queen neighbor) {
	this.n = n;
	this.row = row;
	this.column = column;
	this.neighbor = neighbor;
	this.observer = null;
    }

    // Returns a near-copy of this queen and the queens to her left.
    // The copying is necessary because the original queens are mutable.

    public Queen solution () {
	Queen toLeft = null;
	if (neighbor != null)
	    toLeft = neighbor.solution();
	return new Queen (n, row, column, toLeft);
    }

    // returns true if this queen is visible

    private boolean isVisible() {
	return row != INVISIBLE;
    }

    // returns the number of visible queens starting with this one
    // and going to the left

    public int visible() {
	int thisOne = isVisible() ? 1 : 0;
	int others = neighbor == null ? 0 : neighbor.visible();
	return thisOne + others;
    }

    // Returns true if a possible solution can be found for this
    // queen and the queens to her left.
    //
    // This method is exactly as in Budd's original code.

    public boolean findSolution() {
	while (neighbor != null && neighbor.canAttack(row, column))
	    if (! advance())
		return false;
	return true;
    }

    // Returns true if a possible solution can be found by advancing
    // this queen's row or by wrapping around to the initial row.
    //
    // This method is almost the same as in Budd's original code.
    // (I changed the INITIAL_ROW from 1 to 0 and added the call
    // to  observer.done().)

    public boolean advance() {
	if (row < n) {
	    row++;
	    return findSolution();
	}
	if (neighbor != null) {
	    if (! neighbor.advance())
		return false;
	    if (! neighbor.findSolution())
		return false;
	}
	else {
	    // row == n && neighbor == null
	    // so we've found all of the solutions
	    observer.done();                             // changed from Budd's
	    return false;
	}
	row = INITIAL_ROW;                               // changed from Budd's
	return findSolution();
    }

    // Returns true if this queen, or any of the queens to its left,
    // can attack the specified square.
    //
    // This method is almost the same as in Budd's original code.
    // (I added the first line of the body to deal with row 0,
    // and the (column == testColumn) test so it would work when
    // column and testColumn are equal.)

    private boolean canAttack(int testRow, int testColumn) {
	if (isVisible() && (testRow != INVISIBLE)) {     // changed from Budd's
	    int columnDifference = testColumn - column;
	    if ((row == testRow) ||
		(column == testColumn) ||                // changed from Budd's
		(row + columnDifference == testRow) ||
		(row - columnDifference == testRow))
		return true;
	}
	if (neighbor != null)
	    return neighbor.canAttack(testRow, testColumn);
	return false;
    }

    // Do this queen and the queens to her left
    // attack every unoccupied square on the board?

    public boolean canAttackAll () {
	for (int i = 1; i <= n; i = i + 1) {
	    for (int j = 1; j <= n; j = j + 1)
		if (! canAttack (i, j))
		    return false;
	}
	return true;
    }

    // Draws this queen and the queens to her left.
    //
    // This method is almost the same as in Budd's original code.
    // (I modified it to draw only visible queens, to correct
    // Budd's transposition of rows and columns, and to eliminate
    // the last call to g.drawline(_, _, _, _).)

    public void paint (Graphics g) {
	// first draw neighbor
	if (neighbor != null)
	    neighbor.paint(g);
	// then draw ourself
	if (! isVisible())
	    return;
	// x, y is upper left corner
	int y = (row - 1) * SQUARE_PIXELS + MARGIN_PIXELS;
	int x = (column - 1) * SQUARE_PIXELS + MARGIN_PIXELS;
	g.drawLine(x+x1, y+y1, x+x5, y+y1);
	g.drawLine(x+x1, y+y1, x+x1, y+y5);
	g.drawLine(x+x5, y+y1, x+x5, y+y5);
	g.drawLine(x+x1, y+y2, x+x5, y+y2);
	g.drawLine(x+x1, y+y5, x+x2, y+y4);
	g.drawLine(x+x2, y+y4, x+x3, y+y5);
	g.drawLine(x+x3, y+y5, x+x4, y+y4);
	g.drawLine(x+x4, y+y4, x+x5, y+y5);
	//g.drawLine(x+20, y+20, 10, 10);
    }

}


// A SolutionObserver will visit the lastQueen of each possible
// solution and will be told when all solutions have been found.
// Then it will display a best solution.

class SolutionObserver extends JFrame {

    private int n;                 // n x n chessboard
    private int count = 0;         // number of solutions found so far
    private int best;              // fewest number of queens in a solution
    private Queen bestSolution;    // copy of best solution found so far
    private boolean allDone;       // set to true when all solutions found

    // imported constants (for convenience)

    private static final int SQUARE_PIXELS = QueenConstants.SQUARE_PIXELS;
    private static final int MARGIN_PIXELS = QueenConstants.MARGIN_PIXELS;

    SolutionObserver (int n) {
	this.n = n;
	this.best = n * n + 1;     // any real solution will do better
	bestSolution = null;
	allDone = false;
    }

    // Initialize the GUI part of this JFrame.

    void init () {
	int windowSize = n * SQUARE_PIXELS + 2 * MARGIN_PIXELS;
	// FIXME: JDK 1.3 for Solaris seems to shrink the window
	// size a bit, so this hack compensates for that.
	windowSize = windowSize + 2 * MARGIN_PIXELS;
	setTitle(n + " queens");
	setSize(windowSize, windowSize);
	addMouseListener(new MouseKeeper());
	addWindowListener(new CloseQuit());
    }

    // Visits all solutions.
    // (This code originally conformed to the visitor pattern,
    // but I rewrote a mutual tail recursion as a while loop
    // to prevent stack overflows in Java.)

    void visit (Queen lastQueen) {
	while (! allDone) {
	    if (lastQueen.canAttackAll()) {
		count = count + 1;
		if (lastQueen.visible() < best) {
		    best = lastQueen.visible();
		    bestSolution = lastQueen.solution();
		}
	    }
	    lastQueen.advance();
	}
    }

    // This method is called when all solutions have been found.

    void done () {
	allDone = true;
	show();
	repaint();
	System.out.println (count + " solutions found.");
	System.out.println ("The best solutions had " + best + " queens.");
    }

    public void paint(Graphics g) {
	int farEdge = n * SQUARE_PIXELS + MARGIN_PIXELS;
	super.paint(g);
	// draw board;
	for (int i = 0; i <= n; i++) {
	    g.drawLine(SQUARE_PIXELS * i + MARGIN_PIXELS,
                       MARGIN_PIXELS,
                       SQUARE_PIXELS * i + MARGIN_PIXELS,
		       farEdge);
	    g.drawLine(MARGIN_PIXELS,
		       SQUARE_PIXELS * i + MARGIN_PIXELS,
		       farEdge,
		       SQUARE_PIXELS * i + MARGIN_PIXELS);
	}
	g.drawString("Click Mouse to Exit",
		     MARGIN_PIXELS / 2,
		     farEdge + MARGIN_PIXELS / 2);
	// draw queens
	if (bestSolution != null)
	    bestSolution.paint(g);
    }

    private class CloseQuit extends WindowAdapter {
	public void windowClosing (WindowEvent e) {
	    System.exit(0);
	}
    }

    private class MouseKeeper extends MouseAdapter {
	public void mousePressed (MouseEvent e) {
	    System.exit(0);
	    //lastQueen.advance();
	    //repaint();
	}
    }

}


public class QueenSolver {

    public static void main(String[] args) {
	int n = 0;                 // first command-line argument

	if (args.length < 1)
	    error();

	try {
	    n = Integer.parseInt (args[0]);
	}
	catch (NumberFormatException e) {
	    error();
	}

	SolutionObserver observer = new SolutionObserver (n);
	observer.init();
	Queen lastQueen = null;
	for (int i = 1; i <= n; i++) {
	    lastQueen = new Queen(n, i, lastQueen, observer);
	}

	lastQueen.findSolution();
	observer.visit (lastQueen);
    }

    private static void error() {
	System.err.println ("Usage: java QueenSolver n");
	System.exit(1);
    }

}