/*
 * Copyright (C) 1998  Ralf Wiebicke
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package de.rw7;

import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Event;
import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.Panel;
import java.awt.TextArea;

class EightQueensState
{
	public int size = -1;
	public int curr;
	public int lastcollision;
	public int solnum;
	public int solmax;
	public int step;
	public int board[];

	public void setSize(int size)
	{
		this.size = size;
		curr = -1;
		lastcollision = -1;
		solnum = 0;
		solmax = 0;
		step = 0;
		board = new int[size];
	}

	public void copy(EightQueensState x)
	{
		if (x.size != size)
		{
			size = x.size;
			board = new int[size];
		}
		curr = x.curr;
		lastcollision = x.lastcollision;
		solnum = x.solnum;
		solmax = x.solmax;
		step = x.step;
		for (int i = 0; i <= curr; i++)
			board[i] = x.board[i];
	}

	/**
	   Performes a single step of backtracking. Does not care about repainting.
	   Is not synchronized due to performance reasons. When calling this method,
	   you have to care about synchronization for yourself.
	*/
	public void step()
	{
		step++;
		if ((lastcollision < 0) && (curr < (size - 1)))
		{
			curr++;
			board[curr] = 0;
		}
		else
		{
			do
			{
				board[curr]++;
				if (board[curr] >= size)
					curr--;
				else
					break;
			}
			while (curr >= 0);
			if (curr < 0)
			{
				lastcollision = -1;
				solnum = 0;
				step = 0;
				return;
			};
		};

		lastcollision = -1;
		for (int i = 0; i < curr; i++)
			if ((board[i] == board[curr])
				|| ((curr - i) == Math.abs(board[curr] - board[i])))
			{
				lastcollision = i;
				break;
			};

		if ((lastcollision < 0) && (curr == (size - 1)))
		{
			solnum++;
			if (solnum > solmax)
				solmax = solnum;
		};
	}

	public void computeSolution(int offset)
	{
		lastcollision = -1;
		for (int i = 0;(i < size) && (lastcollision < 0); i++)
		{
			board[i] = (2 * i + offset) % size;
			curr = i;
			for (int j = 0; j < curr; j++)
				if ((board[j] == board[curr])
					|| ((curr - j) == Math.abs(board[curr] - board[j])))
				{
					lastcollision = j;
					break;
				};
		}
	}

} // class EightQueensState

class EightQueensBoard extends Canvas implements Runnable
{
	private Thread running;
	private TextArea console;
	private EightQueensState state = new EightQueensState();
	private EightQueensState painted = new EightQueensState();

	EightQueensBoard(int size, TextArea console)
	{
		this.console = console;
		state.setSize(size);
	}

	void stopThreads()
	{
		synchronized (state)
		{
			stopSearch();
		}
	}

	/**
	   Does not use Thread.stop() due to deprecation in JDK 1.2
	   Method does not stop the thread directly, but sets a flag,
	   which causes the thread to abort at the next suitable posibility.
	   Calling thread must own lock of state
	   @see state
	*/
	private void stopSearch()
	{
		if (running != null)
		{
			running = null;
			try
			{
				state.wait();
			}
			catch (InterruptedException e)
			{
				System.out.println(e);
			};
		}
	}

	void setSize(int size)
	{
		if (size < 3)
			return;

		synchronized (state)
		{
			stopSearch();
			state.setSize(size);
			tell("board size is " + size + ".");
		}
		repaint();
	}

	int getBoardSize()
	{
		return state.size;
	}

	void computeSolution(int offset)
	{
		synchronized (state)
		{
			stopSearch();
			state.computeSolution(offset);
			if (state.lastcollision < 0)
				tell("pattern is a SOLUTION!");
			else
				tell("pattern is no solution.");
		}
		repaint();
	}

	private boolean searchall;
	private EightQueensState runningstate;
	void startSearchForSolution(boolean searchall)
	{
		synchronized (state)
		{
			stopSearch();
			if (searchall)
				tell("searching for all solutions...");
			else
				tell("searching for next solution...");

			this.searchall = searchall;
			if (runningstate == null)
				runningstate = new EightQueensState();
			runningstate.copy(state);

			running = new Thread(this);
			running.setPriority(Thread.MIN_PRIORITY);
			running.start();
		}
	}

	public void run()
	{
		EightQueensState x = runningstate;

		if (searchall)
			do x.step();
			while ((running != null) && (x.curr >= 0));
		else
			do x.step();
			while ((running != null)
				&& ((x.lastcollision >= 0) || (x.curr < (x.size - 1)))
				&& (x.curr >= 0));

		synchronized (state)
		{
			if (running == null)
				tell("searching stopped");
			running = null;
			state.notifyAll();

			state.copy(x);

			if (x.curr < 0)
				tell("end reached, total " + x.solmax + " solutions.");
			else if ((x.lastcollision < 0) && (x.curr == (x.size - 1)))
				tell("found solution #" + x.solnum + ".");
			else
				tell("up to now " + x.solmax + " solutions found.");

		}

		repaint();
	}

	void stepOnce()
	{
		synchronized (state)
		{
			stopSearch();
			state.step();

			if (((state.lastcollision >= 0) || (state.curr < (state.size - 1))))
				tell("stepped once.");
			else
				tell("stepped once, found solution #" + state.solnum + ".");
		};

		repaint();
	}

	/**
	   Puts some text on the console. Not synchronized due to performance.
	   Has to be synchronized on state by the calling method.
	   @see state
	*/
	private void tell(String s)
	{
		console.append("at " + state.step + ": " + s + "\n");
		console.setCaretPosition(console.getText().length());
	}

	public Dimension minimumSize()
	{
		final Dimension D = getParent().getSize();
		int i = Math.min(D.width, D.height);
		D.width = i;
		D.height = i;
		return (D);
	}

	public Dimension preferredSize()
	{
		return (minimumSize());
	}

	public void paint(Graphics g)
	{
		synchronized (state)
		{
			painted.curr = -1;
			painted.size = -1;
			this.update(g);
		};
	}

	public void update(Graphics g)
	{
		synchronized (state)
		{
			int size = state.size;
			int curr = state.curr;
			int[] board = state.board;
			final int Quad = Math.min(getSize().width, getSize().height) / size;

			if (painted.size != state.size)
			{
				g.setColor(getBackground());
				g.fillRect(0, 0, getSize().width, getSize().height);
				g.setColor(Color.white);
				g.fillRect(0, 0, size * Quad, size * Quad);
				g.setColor(Color.black);
				for (int j = 0; j < size; j++)
					for (int i = 0; i < size; i++)
						if (((i + j) & 1) > 0)
							g.fillRect(Quad * j, Quad * i, Quad, Quad);
				painted.size = size;
				painted.board = new int[size];
				painted.curr = -1;
			}

			for (int i = 0; i <= painted.curr; i++)
				if ((i > curr) || (painted.board[i] != board[i]))
				{
					g.setColor(
						(((i + painted.board[i]) & 1) == 0)
							? Color.white
							: Color.black);
					g.fillRect(Quad * painted.board[i], Quad * i, Quad, Quad);
				}

			for (int i = 0; i <= curr; i++)
			{
				g.setColor(
					((state.lastcollision >= 0)
						&& ((i == curr) || (i == state.lastcollision)))
						? Color.red
						: Color.green);
				g.fillOval(Quad * board[i], Quad * i, Quad - 1, Quad - 1);
				painted.board[i] = board[i];
			}
			painted.curr = curr;

		} // synchronized(state)
	}

} // class EightQueensBoard

public class EightQueens extends java.applet.Applet
{
	EightQueensBoard board;
	String Step = "Step Once",
		Sol = "Search for Solution",
		All = "Search for all Solutions",
		Comp = "Try Pattern",
		PgUp = "Larger Board",
		PgDn = "Smaller Board";

	TextArea console;

	public void init()
	{
		setLayout(new BorderLayout());
		{
			Panel Q = new Panel(new BorderLayout());
			console = new TextArea("Welcome to EightQueens!\n");
			console.setEditable(false);
			Q.add(console, BorderLayout.CENTER);
			{
				Panel P = new Panel(new GridLayout(0, 1));
				P.add(new Button(Step));
				P.add(new Button(Sol));
				P.add(new Button(All));
				P.add(new Button(Comp));
				P.add(new Button(PgUp));
				P.add(new Button(PgDn));
				Q.add(P, BorderLayout.SOUTH);
			}
			add(Q, BorderLayout.CENTER);
		}
		add(board = new EightQueensBoard(8, console), BorderLayout.WEST);
	}

	public void stop()
	{
		board.stopThreads();
	}

	public boolean action(Event evt, Object arg)
	{
		if (evt.target instanceof Button)
		{
			if (evt.arg == Step)
				board.stepOnce();
			else if (arg == PgUp)
				board.setSize(board.getBoardSize() + 1);
			else if (arg == PgDn)
				board.setSize(board.getBoardSize() - 1);
			else if (arg == Comp)
				board.computeSolution(0);
			else if (arg == Sol)
				board.startSearchForSolution(false);
			else if (arg == All)
				board.startSearchForSolution(true);
			else
				return (super.handleEvent(evt));
			return (true);
		}
		return (false);
	}

} // class EightQueens