| |
/**
* Springer.java
*
* @author Martin Klöckner, Daniel Höpfl
*/
package SpringerPack;
import javax.swing.JProgressBar;
import javax.swing.JList;
import java.util.Vector;
import java.awt.Canvas;
/**
* This class implements the backtracing to solve the Springerproblem
*
* @see IOutput
* @see SpringerMain
*/
public class Springer extends Thread
{
/**
* Flag to indicate an interruption
*/
private boolean mKeepRunning = true;
/**
* Member for callback-function-calls
*/
SpringerMain mMain = null;
/**
* size of board
*/
int mSize = 2;
/**
* Starting field
*/
int mStartX = 0;
int mStartY = 0;
/**
* IOutput for showing the board
*/
IOutput mOutput = null;
/**
* element to show the deepth the backtracking is in
*/
JProgressBar mDeepth = null;
/**
* global progress
*/
int mProgressInt = 0;
JProgressBar mProgress = null;
/**
* board to use
*/
private Board mBoard = null;
/**
* lists of results
*/
JList mResultList = null;
Vector mResultVector = null;
/**
* initialisize Springer
*
* @param inMain MainFrame of the applet (used for callback in case of "natural" end)
* @param inSize size of Board
* @param inProgressBar global Progressbar
* @param inProgressDeepthBar element to display calculation deepth
* @param inOutput Object to show the board
* @param inResultList List to show the result
* @param inBoard board to store the data in
*
* @see IOutput
* @see Board
*/
Springer(SpringerMain inMain,
int inSize,
JProgressBar inProgressBar,
JProgressBar inProgressDeepthBar,
IOutput inOutput,
JList inResultList,
Board inBoard)
{
mKeepRunning = true;
mMain = inMain;
mSize = inSize;
mProgress = inProgressBar;
mDeepth = inProgressDeepthBar;
mDeepth.setMinimum(0);
mDeepth.setMaximum(mSize * mSize);
mDeepth.setValue(0);
mProgress.setMinimum(0);
mProgress.setMaximum(100000);
mProgress.setValue(0);
mProgressInt = 0;
mResultVector = new Vector();
mResultList = inResultList;
mResultList.setListData(mResultVector);
mBoard = inBoard;
setIOutput(inOutput);
}
/**
* set the starting field
*
* @param inX x-coordinate of the starting field
* @param inY y-coordinate of the starting field
*/
public void setStart(int inX, int inY)
{
if(inX < mSize)
mStartX = inX;
if(inY < mSize)
mStartY = inY;
}
/**
* set the IOutput Object
*
* @param inOutput Object to set
*/
public synchronized void setIOutput(IOutput inOutput)
{
mOutput = inOutput;
mOutput.setBoardSize(mSize);
mOutput.setBoard(mBoard);
}
/**
* get one step deeper in the backtracking algorithmus
*
* @param inSourceX x-coordinate of the source field
* @param inSourceY y-coordinate of the source field
* @param inDestX x-coordinate of the target field
* @param inDestY y-coordinate of the target field
*
* @see IOutput#deeper
*/
private synchronized void deeper(int inSourceX, int inSourceY, int inDestX, int inDestY) throws InterruptedException
{
mOutput.deeper(inSourceX, inSourceY, inDestX, inDestY);
mDeepth.setValue(mDeepth.getValue() + 1);
}
/**
* get one step higher in the backtracking algorithmus
* @param inSourceX x-coordinate of the source field
* @param inSourceY y-coordinate of the source field
* @param inDestX x-coordinate of the target field
* @param inDestY y-coordinate of the target field
*
* @see IOutput#higher
*/
private synchronized void higher(int inSourceX, int inSourceY, int inDestX, int inDestY) throws InterruptedException
{
mOutput.higher(inSourceX, inSourceY, inDestX, inDestY);
mDeepth.setValue(mDeepth.getValue() - 1);
}
/**
* insert a Result into the Result-List
*/
private synchronized void foundResult() throws InterruptedException
{
int xPos[] = new int[mSize*mSize];
int yPos[] = new int[mSize*mSize];
// get sequence of moves
for(int x = 0;x < mSize; x++)
{
for(int y = 0;y < mSize; y++)
{
xPos[mBoard.getXY(x,y) - 1] = x;
yPos[mBoard.getXY(x,y) - 1] = y;
}
}
// create string in chess-notation
String theResult = new String();
for(int i = 0;i < mSize * mSize; i++)
{
theResult += ("ABCDEFGHIJKLMNOP".charAt(xPos[i])) +
new Integer(mSize - yPos[i]).toString() +
" ";
}
// add result
mResultVector.addElement(theResult);
mResultList.setListData(mResultVector);
}
/**
* main recursive backtracking procedure
*
* @param xPos x-coordinate of the field to test
* @param yPos y-coordinate of the field to test
* @param Nr number of step
*/
private void DoIt(int xPos, int yPos, int Nr) throws InterruptedException
{
// have we been stopped?
if(!mKeepRunning)
{
interrupt();
return;
}
// array for all possible moves
int xDir[] = new int[8];
int yDir[] = new int[8];
xDir[0] = 2; yDir[0] = -1;
xDir[1] = 2; yDir[1] = 1;
xDir[2] = 1; yDir[2] = 2;
xDir[3] = -1; yDir[3] = 2;
xDir[4] = -2; yDir[4] = 1;
xDir[5] = -2; yDir[5] = -1;
xDir[6] = -1; yDir[6] = -2;
xDir[7] = 1; yDir[7] = -2;
// lock board to prevent the other thread from drawing
// half-changed fields, then set our move in and unlock
mBoard.lockBoard();
mBoard.setXY(xPos, yPos, Nr);
mBoard.unlockBoard();
// found a result?
if(Nr == (mSize * mSize))
{
foundResult();
}
else
{
// test all 8 possible moves
for(int testNr = 0;testNr < 8; testNr++)
{
// can we get there
if(mBoard.getXY(xPos + xDir[testNr], yPos + yDir[testNr]) == 0)
{
// update progress-bar
mProgressInt++;
mProgress.setValue((int) ((((float) mProgressInt)/134217728) * 10000));
// next step in backtracking
deeper(xPos, yPos, xPos + xDir[testNr], yPos + yDir[testNr]);
DoIt(xPos + xDir[testNr], yPos + yDir[testNr], Nr+1);
higher(xPos + xDir[testNr], yPos + yDir[testNr], xPos, yPos);
}
else if(Nr < 9)
{
// can't get deeper, progress faster
int reste[] = new int[9];
reste[0] = 16777216;
reste[1] = 2097152;
reste[2] = 262144;
reste[3] = 32768;
reste[4] = 4096;
reste[5] = 512;
reste[6] = 64;
reste[7] = 8;
reste[8] = 1;
mProgressInt += reste[Nr - 1];
mProgress.setValue((int) ((((float) mProgressInt)/134217728) * 10000));
}
}
}
// take back the move
mBoard.lockBoard();
mBoard.setXY(xPos, yPos, 0);
mBoard.unlockBoard();
}
// start thread
public void run() {
mDeepth.setValue(1);
try {
DoIt(mStartX,mStartY,1);
} catch (InterruptedException e){
}
mDeepth.setValue(0);
mProgress.setValue(0);
mProgressInt = 0;
mMain.ChildFinished();
}
// interrupt it.
public void Stop() {
mKeepRunning = false;
}
}
|