/*
 * Created on Jul 7, 2005
 *
 * To change the template for this generated file go to
 * Window&gt;Preferences&gt;Java&gt;Code Generation&gt;Code and Comments
 */
package edu.unl.consystlab.sudoku;

/**
 * @author Klaas van der Lugt
 *
 * To change the template for this generated type comment go to
 * Window&gt;Preferences&gt;Java&gt;Code Generation&gt;Code and Comments
 */
public class Solver implements Runnable
{
	// Speed definitions in milliseconds, usable by Thread.sleep()
	public static final int SLOW = 250; // 1 second
	public static final int FAST = 0;
	public static final int DEFAULT_SPEED = 500;

	private Griddable grid;
	private Game game;

	// Thread stuff
	private Thread thread = null;
	private boolean pleaseStop = false;
	private int optimization = OptimizationMenu.DEFAULT;

	public Solver(Griddable grid, Game game)
	{
		this.grid = grid;
		this.game = game;
	}

	public void setOptimization(int level)
	{
		optimization = level;
	}

	private int getNext(int prev)
	{
		if (optimization == OptimizationMenu.WITHOUT)
			return prev + 1; // no optimization

		// calc best candidate
		int lowPos = -1;
		int lowEntropy = 0;
		for (int pos = 0; pos < (9 * 9); pos++)
		{
			// convert pos to [row][col]
			int row = pos / 9;
			int col = pos % 9;

			if (grid.getValue(row, col) != Grid.EMPTY)
				continue; // not a candidate

			int entropy = grid.getEntropy(row, col);
			if (lowPos == -1) // first possible entry
			{
				lowPos = pos;
				lowEntropy = entropy;
				continue;
			}
			if (entropy < lowEntropy) // lower entropy first
			{
				lowPos = pos;
				lowEntropy = entropy;
			}
		} // every position
		//System.out.println("getNext(): lowPos="+lowPos+" with entropy "+lowEntropy);
		return lowPos;
	} // getNext - with/without optimization

	public void clearSolved()
	{
		for (int row = 0; row < Grid.SZ; row++)
		{
			for (int col = 0; col < Grid.SZ; col++)
			{
				byte state = grid.getState(row, col);
				if (state == Grid.SOLVED||state==Grid.STRYING)
				{
					grid.clear(row, col);
				}
			}
		}
	} // clearSolved()

	public void showSolved()
	{
		for (int row = 0; row < Grid.SZ; row++)
		{
			for (int col = 0; col < Grid.SZ; col++)
			{

				byte state = grid.getState(row, col);
				if (state == Grid.STRYING)
				{
					grid.setState(row, col, Grid.SOLVED);
				}
			}
		}
	} //showSolved();	

	public void start()
	{
		if (thread == null)
		{
			thread = new Thread(this);
			thread.start();
		}
	}

	private void slowDown()
	{
		if (optimization == OptimizationMenu.WITHXTRA)
			return;
			
		int pct = game.getSpeedPct();
		//Debug.debug("Solver.slowDown(): pct="+pct);
		if (pct == 0)
			return;

		int msec = FAST + (pct * (SLOW - FAST)) / 100;
		//Debug.debug("Solver.slowDown(): "+msec);
		try
		{
			Thread.sleep(msec);
		}
		catch (Exception e)
		{
		}
	} // slowDown();

	public boolean solve(int prev)
	{
		int start = getNext(prev);
		if (start < 0)
		{
			// nothing to do - we are done!!!
			return true;
		}

		// convert single-valued start to row/col
		int row = start / 9;
		int col = start % 9;

		if (pleaseStop)
			return false;

		if (row >= 9 || col >= 9)
		{
			return true; // DONE
		}

		// if fixed or user specified value, skip this one
		if (grid.getState(row, col) != Grid.EMPTY)
			return solve(start);

		// let's go and try some!
		grid.setState(row, col, Grid.STRYING);
		for (byte v = 1; v <= 9 && pleaseStop == false; v++)
		{
			if (grid.isUsed(row, col, v))
				continue;
			grid.setValue(row, col, v);
			slowDown();
			boolean res = solve(start);
			if (res == true) // found!!!
				return true;
		} // try every possible combination
		grid.clear(row, col);
		return false; // :(
	} // solve()
	
	public void stop()
	{
		pleaseStop = true;
		game.inform("Stopping solving process...  ");
		//thread = null;
	}

	// call this method before you turn
	// of life visualization	
	public void initialize()
	{
		clearSolved();
		pleaseStop = false;
	}
	
	public void run()
	{
		// Debug.debug("Solver.run()");
		game.inform("Starting to solve - please wait...");		
		boolean res = solve(-1);
		showSolved();
		game.solverDone(res);
		thread = null;
	}

}
