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

	Backmarking algorithm applied to the N-Queens CSP.
	Algorithm from _Foundations of Constraint Satisfaction_
	by E. P. K. Tsang section 5.4.3 page 147.	
	Backmarking solution of the n-queens CSP.

	usage: java GraphicalBackmark n
*/

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

class GraphicalBackmarkPanel extends JPanel {
	int deltaX, deltaY, n;
	int x0, x1, y0, y1;
	Vector s;
	
	public GraphicalBackmarkPanel(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 * xUnit;
		for (i = 0; i < n; i++) {
			y = y0 + yUnit;
			Integer jI = (Integer) s.elementAt(i);
			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;
		}
	}
}

class GraphicalBackmarkFrame extends JFrame implements ActionListener {
	int iHeight, iWidth;
	
	// 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 GraphicalBackmarkFrame(String title, Vector solution) {
		setTitle(title);
		addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent event) {
				System.exit(0);
			}
		});
		setDesktopSize(this, 100, 100);
		centerOnScreen(this);
		Container contentPane = getContentPane();
		contentPane.add(new GraphicalBackmarkPanel(iWidth, iHeight, solution));
		this.show();
	}
	public void actionPerformed(ActionEvent event) {}
}

class GraphicalBackmark {
	static Date date;
	static Integer negativeOneI;
	static Random random;

	static boolean satisfies(int x, int v, int y, int vp) {
		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(int x, int v, int[] LowUnit, int[] Ordering, int[][] Mark,
					Vector compoundLabel) {
		boolean compat = true;
		int y = LowUnit[x];
		
		while (Ordering[y] < Ordering[x] && compat) {
			if ((Integer) compoundLabel.elementAt(x) != negativeOneI) {
				Integer	vpI = (Integer) compoundLabel.elementAt(y);
				if (satisfies(x, v, y, vpI.intValue()))
					y = Ordering[y] + 1;
				else
					compat = false;
			}
		}
		Mark[x][v] = Ordering[y];
		return compat;
	}

	static boolean BM1(int Level, int[] LowUnit, int[] Ordering, int[][] Mark,
		Vector unlabelled, Vector compoundLabel, Vector solution) {
		boolean commit, result;
		int i, v, x = 0, y;
		Integer xI = new Integer(0);
		Vector Dx = new Vector(compoundLabel.size());
		
		if (unlabelled.isEmpty()) {
			for (i = 0; i < compoundLabel.size(); i++)
				solution.setElementAt(compoundLabel.elementAt(i), i);
			return true;
		}
		for (i = 0; i < unlabelled.size(); i++) {
			xI = (Integer) unlabelled.elementAt(i);
			x = xI.intValue();
			if (Ordering[x] == Level) break;
		}
		result = false;
		for (i = 0; i < compoundLabel.size(); i++) {
			Integer iI = new Integer(i);
	   		Dx.add(iI);
		}
		do {
			// pick a random value from domain of x
			i = random.nextInt(Dx.size());
			Integer vI = (Integer) Dx.elementAt(i);
			Dx.remove(i);
			v = vI.intValue();
			if (Mark[x][v] >= LowUnit[x]) {
				compoundLabel.setElementAt(vI, x);
				commit = false;
				if (Compatible(x, v, LowUnit, Ordering, Mark, compoundLabel)) {
					unlabelled.remove(xI);
					result = BM1(Level + 1, LowUnit, Ordering, Mark, 
						unlabelled, compoundLabel, solution);
					if (!result) {
						commit = false;
						unlabelled.add(xI);
					}
					else
						commit = true;
				}
				if (!commit)
					compoundLabel.setElementAt(negativeOneI, x);
			}
		} while (!Dx.isEmpty() && !result);
		if (!result) {
			LowUnit[x] = Level - 1;
			for (i = 0; i < unlabelled.size(); i++) {
				Integer yI = (Integer) unlabelled.elementAt(i);
				y = yI.intValue();
				LowUnit[y] = LowUnit[y] < Level - 1 ? LowUnit[y] : Level - 1;
			}
		}
		return result;
	}

	static boolean Backmark1(Vector unlabelled, Vector compoundLabel, Vector solution) {
		int i = 0, n = compoundLabel.size(), v, x;
		int[] LowUnit = new int[n];
		int[] Ordering = new int[n];
		int[][] Mark = new int[n][n];
		
		date = new Date();
		random = new Random(date.getTime());
		for (x = 0; x < n; x++) {
			LowUnit[x] = 0;
			for (v = 0; v < n; v++)
				Mark[x][v] = 0;
			Ordering[x] = i++;
		}
		return BM1(0, LowUnit, Ordering, Mark, unlabelled, compoundLabel, solution);
	}

	static void createFrame(Vector solution) {
		new GraphicalBackmarkFrame("GraphicalBackmark by James Pate Williams, Jr. (c) 2000", solution);
	}
	
	static void main(String[] arg) {
		if (arg.length != 1) {
			System.out.println("usage: java GraphicalBackmark 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);
		Vector compoundLabel = new Vector(n), solution = new Vector(n), unlabelled = new Vector(n);
		for (i = 0; i < n; i++) {
			compoundLabel.add(negativeOneI);
   			solution.add(negativeOneI);
			Integer iI = new Integer(i);
			unlabelled.add(iI);
		}
		Backmark1(unlabelled, compoundLabel, solution);
		for (i = 0; i < n; i++) {
			Integer sI = (Integer) solution.elementAt(i);
			char c = (char)(sI.intValue() + 'A');
			System.out.println(i + " " + c);
		}		
		createFrame(solution);
	}
}