import java.applet.Applet;
import java.awt.*;
import java.awt.geom.*;
import java.awt.geom.Rectangle2D;
import java.awt.geom.Line2D;


public class BackTracking2 extends Applet {   
	
	private	final int		L=40;
	private final int		RALLENTA=0;
	private	final int		DIMENSIONI=5, RIGAINIZIALE=DIMENSIONI/2,COLONNAINIZIALE=DIMENSIONI/2;
	private	final int[][]	matrice=new int[DIMENSIONI][DIMENSIONI];

	
	public void paint(Graphics g)    { 
		
		Graphics2D	g2=(Graphics2D)g;
		Rectangle2D.Float frame=new Rectangle2D.Float(0,0,getWidth(),getHeight());
		g2.setColor(Color.white);
		g2.fill(frame);
		g2.setColor(Color.black);
		disegnaGriglia(g2,DIMENSIONI);
		esplora(g2,RIGAINIZIALE,COLONNAINIZIALE,1);
	}

	private void disegnaGriglia(Graphics2D g,int DIMENSIONI)	{
		
		Line2D.Float	line=new Line2D.Float();
		
		for(int i=0; i<=DIMENSIONI; i++)	{
			line.setLine(L*(i+1),L,L*(i+1),L*(DIMENSIONI+1));
			g.draw(line);
			line.setLine(L,L*(i+1),L*(DIMENSIONI+1),L*(i+1));
			g.draw(line);
		}
	}
	
	private boolean esplora(Graphics2D g,int i, int j, int valore)	{
		Rectangle2D.Float toppaBianca=new Rectangle2D.Float();
		int[]	nuovo_elemento=new int[2];
		
		for (int k=0; k<RALLENTA; k++);
		if (occupato(i,j))
			return false;
		matrice[i][j]=valore;
 		g.drawString(valore+ " ",(float)(L*(i+1.3)),(float)(L*(j+1.7)));
		if (valore==(DIMENSIONI*DIMENSIONI))
			return true;
		for(int k=0; k<8; k++)	{
			prossimoElemento(i,j,k,nuovo_elemento);
			if (!fuori(nuovo_elemento[0],nuovo_elemento[1]))
				if (esplora(g, nuovo_elemento[0],nuovo_elemento[1],valore+1))
					return true;
		}
		matrice[i][j]=0;
		for (int k=0; k<RALLENTA; k++);
		toppaBianca.setRect(L*(i+1.25),L*(j+1.25),L/2,L/2);
		g.setColor(Color.white);
		g.fill(toppaBianca);
		g.setColor(Color.black);
		return false;
	}
	
	
	private boolean occupato(int i,int j)	{
		
		return	matrice[i][j]!=0;
	}

	
	private boolean fuori(int i,int j)	{
		
		return ((i>=DIMENSIONI)||(j>=DIMENSIONI)||(i<0)||(j<0));
	}

	private void prossimoElemento(int i,int j,int k,int[] nuovo)	{
		
		switch (k)	{	
			case 0:	nuovo[0]=i-2; nuovo[1]=j+1; break;
			case 1:	nuovo[0]=i-1; nuovo[1]=j+2; break;
			case 2:	nuovo[0]=i+1; nuovo[1]=j+2; break;
			case 3:	nuovo[0]=i+2; nuovo[1]=j+1; break;
			case 4:	nuovo[0]=i+2; nuovo[1]=j-1; break;
			case 5:	nuovo[0]=i+1; nuovo[1]=j-2; break;
			case 6:	nuovo[0]=i-1; nuovo[1]=j-2; break;
			case 7:	nuovo[0]=i-2; nuovo[1]=j-1; break;
		}
		
	}
    
}


Questa la bacheca di Informatica Grafica, corso di laurea specialistica in Ing. Edile-architettura
by FdA
ultima modifica: 02/02/2005 11.30