/*
	Author:	James Pate Williams, Jr. (c) 2001

	Chronological backtracking algorithm applied to the N-Queens CSP.
	Algorithm from _Foundations of Constraint Satisfaction_
	by E. P. K. Tsang section 5.4.3 page 37.	

	usage: java ChronoBT n
*/

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

class ChronoBTPanel extends JPanel {
	int deltaX, deltaY, n;
	int x0, x1, y0, y1;
	Vector s;
	
	public ChronoBTPanel(int iWidth, int iHeight, Vector solution) {
		x0 = iWidth / 8;
		x1 = 7 * x0;
		y0 = iHeight / 8;
		y1 = 7 * y0;
		s = new Vector();
		s = solution;
		n = s.size();
		deltaX = (x1 - x0) / n;
		deltaY = (y1 - y0) / n;
	}
	
	public void paintComponent(Graphics g) {
		int i, j, x, y;
  		int xUnit = deltaY / 9;
  		int yUnit = deltaY / 15;
		int[] triangle1x = new int[3], triangle1y = new int[3];
		int[] triangle2x = new int[3], triangle2y = new int[3];
		int[] triangle3x = new int[3], triangle3y = new int[3];
		
		super.paintComponent(g);
		x = x0;
		for (i = 0; i < n; i++) {
			y = y0;
			if (i % 2 == 0) {
				for (j = 0; j < n; j++) {
					if (j % 2 == 0) {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.white);
						g.fillRect(x, y, deltaX, deltaY);
					}
					else {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.black);
						g.fillRect(x, y, deltaX, deltaY);
					}
					y += deltaY;
				}
			}
			else {
				for (j = 0; j < n; j++) {
					if (j % 2 == 0) {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.black);
						g.fillRect(x, y, deltaX, deltaY);
					}
					else {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.white);
						g.fillRect(x, y, deltaX, deltaY);
					}
					y += deltaY;
				}
			}
			x += deltaX;
		}
		x = x0 + 2 * yUnit;
		for (i = 0; i < n; i++) {
			y = y0 + yUnit;
			Integer jI = (Integer) s.elementAt(i);
			if (jI.intValue() == - 1)
				continue;
			for (j = 0; j < jI.intValue(); j++)
				y += deltaY;
  			triangle1x[0] = x + xUnit;
  			triangle1y[0] = y + 13 * yUnit;
  			triangle1x[1] = x + 7 * xUnit;
  			triangle1y[1] = triangle1y[0];
  			triangle1x[2] = x + 4 * xUnit;
  			triangle1y[2] = y + 7 * yUnit;
  			triangle2x[0] = triangle1x[2];
  			triangle2y[0] = triangle1y[2];
  			triangle2x[1] = x + 2 * xUnit;
  			triangle2y[1] = y + 3 * yUnit;
  			triangle2x[2] = x + 6 * xUnit;
  			triangle2y[2] = triangle2y[1];
  			triangle3x[0] = triangle1x[2];
  			triangle3y[0] = y + 3 * yUnit;
  			triangle3x[1] = x + 3 * xUnit;
  			triangle3y[1] = y + yUnit;
  			triangle3x[2] = x + 5 * xUnit;
  			triangle3y[2] = triangle3y[1];
			g.setColor(Color.red);
			g.fillPolygon(triangle1x, triangle1y, 3);
			g.fillPolygon(triangle2x, triangle2y, 3);
			g.fillPolygon(triangle3x, triangle3y, 3);
			x += deltaX;
		}
	}

	public void setSolution(Vector solution) {
		s = solution;
	}
}

class ChronoBTFrame extends JFrame implements ActionListener, Runnable {
	boolean next, solve;
	int iHeight, iWidth;
	JButton jButton1 = new JButton();
	JButton jButton2 = new JButton();
	JPanel jPanel = new JPanel();
	BorderLayout borderLayout = new BorderLayout();
	ChronoBTPanel chronoBTPanel;
	
	// step 3 - percentage size the window
	void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		iWidth = screen.width * wPerc / 100;
		iHeight = screen.height * hPerc / 100;
		frame.setSize(iWidth, iHeight);
	}
	
	// step 4 - center the window
	void centerOnScreen(JFrame frame) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		Dimension window = frame.getSize();
		int iCenterX = screen.width / 2;
		int iCenterY = screen.height / 2;
		frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
	}
	
	public ChronoBTFrame(Vector solution) {
		String title = "ChronoBT by James Pate Williams, Jr. (c) 2001";
		next = true;
		solve = false;
		jButton1.setToolTipText("Perform one iteration of algorithm");
		jButton1.setText("Next");
		jButton1.setVerticalAlignment(SwingConstants.BOTTOM);
		jButton1.addActionListener(new java.awt.event.ActionListener() {
			public void actionPerformed(ActionEvent e) {
				jButton1_actionPerformed(e);
			}
    		});
		jButton2.setToolTipText("Solve Problem Instance");
		jButton2.setText("Solve");
		jButton2.setVerticalAlignment(SwingConstants.BOTTOM);
		jButton2.addActionListener(new java.awt.event.ActionListener() {
			public void actionPerformed(ActionEvent e) {
				jButton2_actionPerformed(e);
    	  		}
		});
    		this.getContentPane().setLayout(borderLayout);
		setTitle(title);
		addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent event) {
				System.exit(0);
			}
		});
		setDesktopSize(this, 100, 100);
		centerOnScreen(this);
		Container contentPane = getContentPane();
		contentPane.add(jPanel, BorderLayout.SOUTH);
		jPanel.add(jButton1, BorderLayout.EAST);
		jPanel.add(jButton2, BorderLayout.WEST);
		chronoBTPanel = new ChronoBTPanel(iWidth, iHeight, solution);
		contentPane.add(chronoBTPanel,	BorderLayout.CENTER);
		this.show();
		(new Thread(this)).run();
	}

	public void actionPerformed(ActionEvent event) {}

	public boolean getNext() {
		return next;
	}

	public boolean getSolve() {
		return solve;
	}

	public void setNext(boolean n) {
		next = n;
	}

	public void setSolve(boolean s) {
		solve = s;
	}

	void jButton1_actionPerformed(ActionEvent e) {
		next = true;
		solve = false;
	}
	
	void jButton2_actionPerformed(ActionEvent e) {
		next = false;
		solve = true;
	}
	
	public void run() {
		Thread.yield();
	}

	public void draw(Vector solution) {
		chronoBTPanel.setSolution(solution);
		chronoBTPanel.paintComponent(getGraphics());
	}
}

class ChronoBT implements Runnable {
	static boolean solve = false;
	static int steps = 0;
	static Date date;
	static ChronoBTFrame chronoBTFrame;
	static Integer negativeOneI;
	static Random random;
	static Vector compoundLabel = null, solution = null, unlabelled = null;

	static boolean satisfies(int x, int v, int y, int vp) {
		if (v == - 1 || vp == - 1) return true;
		if (x == y) return false;
		if (v == vp) return false;
		if (x - y == v - vp || x - y == vp - v) return false;
		return true;
	}

	static boolean Compatible(Vector vector) {
		int a, b, i, j, n = vector.size();
		
		for (i = 0; i < n - 1; i++) {
			a = ((Integer) vector.elementAt(i)).intValue();
			for (j = i + 1; j < n; j++) {
				b = ((Integer) vector.elementAt(j)).intValue();
				if (!satisfies(i, a, j, b))
					return false;
			}
		}
		return true;
	}

	static boolean BT1(Vector unlabelled, Vector compoundLabel, Vector solution) {
		boolean result;
		int i, j, x;
		Vector Dx = new Vector(compoundLabel.size());

		if (unlabelled.isEmpty()) {
			System.out.println("number of steps = " + steps);
			for (i = 0; i < compoundLabel.size(); i++)
				solution.setElementAt(compoundLabel.elementAt(i), i);
			return true;
		}
		for (i = 0; i < compoundLabel.size(); i++)
	   		Dx.add(new Integer(i));
		i = random.nextInt(unlabelled.size());
		Integer xI = (Integer) unlabelled.elementAt(i);
		x = xI.intValue();
		Vector param1 = new Vector(unlabelled.size());
		for (i = 0; i < unlabelled.size(); i++)
			param1.add(unlabelled.elementAt(i));
		param1.remove(xI);
		do {
			// pick a random value from domain of x
			j = random.nextInt(Dx.size());
			Integer vI = (Integer) Dx.elementAt(j);
			Dx.remove(vI);
			Vector param2 = new Vector(compoundLabel.size());
			for (i = 0; i < compoundLabel.size(); i++)
				param2.add(compoundLabel.elementAt(i));
			param2.setElementAt(vI, x);
			chronoBTFrame.draw(param2);
			if (chronoBTFrame.getNext())
				chronoBTFrame.setNext(false);
			if (!solve) { 
				while (!chronoBTFrame.getNext() && !chronoBTFrame.getSolve())
					Thread.yield();
				solve = chronoBTFrame.getSolve();
				chronoBTFrame.setNext(true);
			}
			steps++;
			if (Compatible(param2)) {
				result = BT1(param1, param2, solution); 
				if (result) {
					param1.add(xI);
					unlabelled = param1;
					compoundLabel = param2;
					return result;
				} 
			}
		} while (!Dx.isEmpty());
		return false;
	}

	static void createFrame(Vector solution) {
		chronoBTFrame = new ChronoBTFrame(solution);
	}
	
	public void run() {
		date = new Date();
		random = new Random(date.getTime());
		BT1(unlabelled, compoundLabel, solution);
	}

	static void main(String[] arg) {
		if (arg.length != 1) {
			System.out.println("usage: java ChronoBT n");
			System.exit(1);
		}
		Integer nI = new Integer(arg[0]);
		int i, n = nI.intValue();
		
		if (n < 4) {
			System.out.println("n is too small!");
			System.out.println("n >= 4");
			System.exit(1);
		}
		if (n > 32) {
			System.out.println("n is too large!");
			System.out.println("n <= 32");
			System.exit(1);
		}
		negativeOneI = new Integer(- 1);
		compoundLabel = new Vector(n);
		solution = new Vector(n);
		unlabelled = new Vector(n);
		for (i = 0; i < n; i++) {
			compoundLabel.add(negativeOneI);
   			solution.add(negativeOneI);
			unlabelled.add(new Integer(i));
		}
		createFrame(solution);
		(new ChronoBT()).run();
	}
}