/*
  Author:  James Pate Williams (c) 2001

  From Makoto Yokoo _Distributed Constraint Satisfaction_
  Weak-commitment search algorithm
*/

import java.lang.Integer;
import java.lang.Math;
import java.lang.Object;
import java.util.Date;
import java.util.Random;
import java.util.Vector;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class WCSAPanel extends JPanel {
	int deltaX, deltaY, n;
	int x0, x1, y0, y1;
	Vector s;
	
	public WCSAPanel(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 WCSAFrame 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();
	WCSAPanel wcsaPanel;
	
	// 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 WCSAFrame(Vector solution) {
		String title = "WCSA 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);
		wcsaPanel = new WCSAPanel(iWidth, iHeight, solution);
		contentPane.add(wcsaPanel, 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) {
		wcsaPanel.setSolution(solution);
		wcsaPanel.paintComponent(getGraphics());
	}
}

class WCSA implements Runnable {
  boolean solve = false;
  int numberCC, n;
  static WCSAFrame wcsaFrame;
  public WCSA(int N) {
    n = N;
  }
  class VariableValueTuple {
     private int value, variable;
     public VariableValueTuple() {
     }
     public VariableValueTuple(int var, int val) {
       variable = var;
       value = val;
     }
     public boolean equals(Object object) {
       VariableValueTuple vvt = (VariableValueTuple) object;
       return variable == vvt.getVariable() && value == vvt.getValue();
     }
     public int getVariable() {
       return variable;
     }
     public int getValue() {
       return value;
     }
     public void setVariable(int var) {
       variable = var;
     }
     public void setValue(int val) {
       value = val;
     }
  }
  private boolean violation(VariableValueTuple varValTuple1, VariableValueTuple varValTuple2) {
    int i = varValTuple1.getVariable();
    int j = varValTuple2.getVariable();
    int xi = varValTuple1.getValue();
    int xj = varValTuple2.getValue();
    numberCC++;
    if (xi == xj)
      return true;
    if (Math.abs(i - j) == Math.abs(xi - xj))
      return true;
    return false;
  }
	private void draw(int n, Vector solution) {
		Vector compoundLabel = new Vector(n);
		for (int i = 0; i < n; i++)
			compoundLabel.add(new Integer(- 1));
		for (int i = 0; i < solution.size(); i++) {
			VariableValueTuple aVVT = (VariableValueTuple) solution.elementAt(i);
			Integer clI = new Integer(aVVT.getValue());
			compoundLabel.setElementAt(clI, aVVT.getVariable());
		} 
		wcsaFrame.draw(compoundLabel);
		if (wcsaFrame.getNext())
			wcsaFrame.setNext(false);
		if (!solve) { 
			while (!wcsaFrame.getNext() && !wcsaFrame.getSolve())
				Thread.yield();
			solve = wcsaFrame.getSolve();
			wcsaFrame.setNext(true);
		}
	}

  private void preprocessor(int n, Random random, Vector solution) {
    int con, i, j, minConflict, value;
    int[] conflict = new int[n], v = new int[n];

    solution.add(new VariableValueTuple(0, random.nextInt(n)));
	draw(n, solution);
    for (i = 1; i < n; i++) {
      for (value = 0; value < n; value++) {
        VariableValueTuple varValTuple1 = new VariableValueTuple(i, value);
        for (con = j = 0; j < i; j++) {
          VariableValueTuple varValTuple2 = (VariableValueTuple) solution.get(j);
          if (violation(varValTuple1, varValTuple2))
            con++;
        }
        conflict[value] = con;
      }
      minConflict = conflict[0];
      for (value = 1; value < n; value++)
        if (conflict[value] < minConflict)
          minConflict = conflict[value];
      for (value = j = 0; value < n; value++)
        if (minConflict == conflict[value])
          v[j++] = value;
      j = random.nextInt(j);
      if (j < 0)
        j += n;
      solution.add(new VariableValueTuple(i, v[j]));
	draw(n, solution);
    }
  }
  private void printSolution(boolean s, Vector solution) {
    int i, j, n = solution.size();
    if (s) {
      if (n <= 16) {
        System.out.println();
        for (i = 0; i < n; i++) {
          for (j = 0; j < n; j++)
            System.out.print("----");
          System.out.println("-");
          VariableValueTuple vvt = (VariableValueTuple) solution.get(i);
          for (j = 0; j < vvt.getValue(); j++)
            System.out.print("|   ");
          System.out.print("| Q ");
          for (j = vvt.getValue() + 1; j < n; j++)
            System.out.print("|   ");
          System.out.println("|");
        }
        for (i = 0; i < n; i++)
          System.out.print("----");
        System.out.println("-");
      }
      else
        System.out.println("n is too large to print solution!");
    }
  }
  public void run() {
    boolean found = false;
    final int MaxIterations = 5000;
    int i, iterations = 0, j, r;
    long seed = (new Date()).getTime();
    Random random = new Random(seed);
    Vector constraint = new Vector(n * n);
    Vector partialSolution = new Vector(n);
    Vector varsLeft = new Vector(n);
    numberCC = 0;
    preprocessor(n, random, varsLeft);
    for (i = r = 0; i < n - 1; i++) {
      VariableValueTuple aVVT = (VariableValueTuple) varsLeft.elementAt(i);
      for (j = i + 1; j < n; j++) {
        VariableValueTuple bVVT = (VariableValueTuple) varsLeft.elementAt(j);
        if (violation(aVVT, bVVT))
          r++;
      }
    }
    if (r == 0)
      return;
    for (;;) {
      boolean cv = false;
      int s = varsLeft.size();
      VariableValueTuple varValTuple1, varValTuple2;
      Vector vvt = new Vector(s);
      iterations++;
      if (iterations > MaxIterations) {
        System.out.println("maximum number of iterations = " + MaxIterations +
          " exceeded!");
        found = false;
        break;
      }
      for (i = 0; i < s; i++) {
        varValTuple1 = (VariableValueTuple) varsLeft.get(i);
        for (j = 0; j < s; j++) {
          if (i != j) {
            varValTuple2 = (VariableValueTuple) varsLeft.get(j);
            cv = violation(varValTuple1, varValTuple2);
            if (cv) {
              if (!vvt.contains(varValTuple1))
                vvt.add(varValTuple1);
            }
          }
        }
        for (j = 0; j < partialSolution.size(); j++) {
          varValTuple2 = (VariableValueTuple) partialSolution.get(j);
          cv = violation(varValTuple1, varValTuple2);
          if (cv) {
            if (!vvt.contains(varValTuple1))
              vvt.add(varValTuple1);
          }
        }
      }
      if (vvt.size() == 0) {
        found = true;
        break;
      }
      r = random.nextInt() % vvt.size();
      if (r < 0)
        r += vvt.size();
      int x = ((VariableValueTuple) vvt.get(r)).getVariable();
      int d = ((VariableValueTuple) vvt.get(r)).getValue();
      Vector values = new Vector(n);
      for (i = 0; i < n; i++) {
        if (i != d) {
          VariableValueTuple newVVT = new VariableValueTuple(x, i);
          cv = false;
          for (j = 0; !cv && j < partialSolution.size(); j++) {
            VariableValueTuple vvt1 = (VariableValueTuple) partialSolution.get(j);
            cv = violation(newVVT, vvt1);
          }
          if (!cv)
            values.add(new Integer(i));
        }
      }
      if (values.size() == 0) {
        if (partialSolution.size() == 0) {
          System.out.println("no solution exists!");
          found = false;
          break;
        }
        else {
          for (i = 0; i < partialSolution.size(); i++) {
            VariableValueTuple lastVVT = (VariableValueTuple) partialSolution.get(i);
            if (!constraint.contains(lastVVT))
              constraint.add(lastVVT);
            partialSolution.remove(i);
            varsLeft.add(lastVVT);
          }
        }
      }  
      else {
        varsLeft.remove(vvt.get(r));
        int[] conVio = new int[values.size()];
        for (i = 0; i < values.size(); i++) {
          int dv = ((Integer) values.get(i)).intValue();
          conVio[i] = 0;
          for (j = 0; j < varsLeft.size(); j++) {
            cv = violation(new VariableValueTuple(x, dv),
              (VariableValueTuple) varsLeft.get(j));
            if (cv)
              conVio[i]++;
          }
        }
        int count = 0, min = conVio[0];
        for (i = 1; i < values.size(); i++)
          if (conVio[i] < min)
            min = conVio[i];
        int[] array = new int[values.size()];
        for (i = 0; i < values.size(); i++)
          if (min == conVio[i])
            array[count++] = ((Integer) values.get(i)).intValue();
        r = random.nextInt() % count;
        if (r < 0)
          r += count;
        int v = array[r];
        partialSolution.add(new VariableValueTuple(x, v));
      }
      Vector solution = new Vector(n);
      for (int k = 0; k < n; k++)
         solution.add(new VariableValueTuple(k, - 1));
      for (int k = 0; k < partialSolution.size(); k++) {
        VariableValueTuple vvt2 = (VariableValueTuple) partialSolution.get(k);
        solution.setElementAt(vvt2, vvt2.getVariable());
      }
      for (int k = 0; k < varsLeft.size(); k++) {
        VariableValueTuple vvt2 = (VariableValueTuple) varsLeft.get(k);
        solution.setElementAt(vvt2, vvt2.getVariable());
      }
	draw(n, solution);
    }
  }

	static void createFrame(Vector solution) {
		wcsaFrame = new WCSAFrame(solution);
	}

  public static void main(String[] args) {
    if (args.length != 1) {
      System.out.println("must specify the number of queens in command line!");
      System.exit(0);
    }
    int n = (new Integer(args[0])).intValue();
    if (n < 4) {
      System.out.println("number of queens must be greater than equal four");
      System.exit(0);
    }
    Vector solution = new Vector(n);
    for (int i = 0; i < n; i++)
	solution.add(new Integer(- 1));
    createFrame(solution);
    (new WCSA(n)).run();
  }
}