import java.awt.*;
import java.awt.event.*;

/*
  
  8-Queens Applet, By Aaron Davidson <http://spaz.ca/>
  
  This code is released in the public domain. The author
  would appreciate it if any derivatives or distributions
  retain this comment & credit.
  
 */

public class Board extends Canvas implements MouseListener {
	int[][] grid = new int[8][8];
	Graphics gr = this.getGraphics();
	int gWidth,gHeight;
		
	public Board() {
		addMouseListener(this);
		initBoard();
	}
	
	public void initBoard() {
		for (int i=0;i<8;i++) 
			for (int j=0;j<8;j++)
				grid[i][j] = 0;
	}
	
	/**
	 * Paint the board 
	 */
	public void paint(Graphics g) {
		gr = g;
		gWidth = getBounds().width/8;
		gHeight = getBounds().height/8;
		for (int i=0;i<8;i++) 
			for (int j=0;j<8;j++) 
				drawCell(i,j);
	}

	/**
	 * Draw a specific cell on the board.
	 */
	private void drawCell(int x, int y) {
		int dark = 0;
		gr.setColor(Color.black);
		gr.drawRect(x*gWidth, y*gHeight, gWidth, gHeight);
		if ((x+y)%2 == 0) 	
			dark = 20;
		switch (grid[x][y]) {
			case 0: gr.setColor(new Color(230+dark,230+dark,230+dark)); break;
			case 1: gr.setColor(new Color(160+dark,110+dark,110+dark)); break;
			case 2: gr.setColor(new Color(0,0,0)); break;
		}
		gr.fillRect(x*gWidth+1, y*gHeight+1, gWidth-1, gHeight-1);
	}

	public void mouseExited(MouseEvent e) {}
	public void mouseReleased(MouseEvent e) {}
	public void mouseClicked(MouseEvent e) {}
	public void mouseEntered(MouseEvent e) {}

	/**
	 * Handle a mouse click.
	 */
	public void mousePressed(MouseEvent e) {
		int x,y;
		
		x = e.getX()/gWidth;
		y = e.getY()/gHeight;
		if (legal(x,y)) {
			if (grid[x][y] == 0) 
				addQueen(x,y,true);
			else if (grid[x][y] == 2) 
				addQueen(x,y,false);
		}
	}
	
	/**
	 * Adds (or removes) a queen to the given coordinates.
	 * If add is true, it adds a queen. If it is false, it removes a queen.
	 */
	private void addQueen(int x, int y, boolean add) {
		int i;
		gr = this.getGraphics();
		if (add)
			grid[x][y] = 2;
		else
			grid[x][y] = 0;
		for (i=0;i<8;i++) {
			if (i!=y) changeCell(x,i,add);
			if (i!=x) changeCell(i,y,add);
		}
		for (i=1; legal(x+i,y+i); i++)
			changeCell(x+i,y+i,add);
		for (i=1; legal(x+i,y-i); i++)
			changeCell(x+i,y-i,add);
		for (i=1; legal(x-i,y+i); i++)
			changeCell(x-i,y+i,add);
		for (i=1; legal(x-i,y-i); i++)
			changeCell(x-i,y-i,add);
		
		drawCell(x,y);
		if (!add)
			for (i=0;i<8;i++)
				for (int j=0;j<8;j++)
					if (grid[i][j] == 2)
						addQueen(i,j,true);
	}
	
	/**
	 * Add or remove a queen to the given cell
	 */
	private void changeCell(int x, int y, boolean add) {
		if (add && grid[x][y] == 0)
			grid[x][y] = 1;
		else if (!add && grid[x][y] == 1)
			grid[x][y] = 0;
		drawCell(x,y);
	}
	
	/**
	 * Returns true if the coordinates are a legal board position
	 */
	private boolean legal(int x, int y) {
		return (x >= 0 && x < 8 && y >= 0 && y < 8);
	}

	/**
	 * Solve the 8-queens puzzle with a very simple depth-first search.
	 */
	public boolean solve(int y) {
		int 	i,j;
		boolean r = false;
		
		for (i=0;i<8;i++) { 
			// for each row, try placing a queen
			if (grid[i][y] == 0) {
				addQueen(i,y,true);
				if (y == 7) {
					return true; // we have placed all queens successfully
				} else {
					if (solve(y+1)) {
						return true; // we solved it, return
					} else {
						addQueen(i,y,false); // remove the queen
					}
				}
			}
		}
		// unable to solve down this branch -- retreat!
		return false;
	}
	

}