import java.awt.*;
import java.awt.geom.*;


public class BackTracking  {   
	
	static	int		dimensioni, rigaIniziale,colonnaIniziale;
	static	int[][]	matrice;
		
	public static void main(String[] args)	{
		
		ConsoleReader	input=new ConsoleReader(System.in);
		BackTracking	back=new BackTracking();	
						
		System.out.print("Introdurre le dimensioni della matrice:");
		dimensioni=input.readInt();
		matrice=new int[dimensioni][dimensioni];
		for(int i=0;i<dimensioni; i++)	
			for(int j=0;j<dimensioni; j++)
				matrice[i][j]=0;
		rigaIniziale = dimensioni/2;
		colonnaIniziale = dimensioni/2;
		if (back.esplora(back, rigaIniziale,colonnaIniziale,1))	{
			System.out.print("\n\n******Soluzione trovata******\n\n");
			back.stampaMatrice();
		}
		else 	
			System.out.print("\n\n******Soluzione non trovata\n\n******");
 	}

	
	private boolean esplora(BackTracking back, int i, int j, int valore)	{
		
		int[]	nuovo_elemento=new int[2];	//conserva gli indici di riga e di colonna del prossimo elemento da esplorare
		
		System.out.println("esplora("+(i+1)+","+(j+1)+","+valore+")");
		
		if (back.occupato(i,j))
			return false;
		matrice[i][j]=valore;
 		stampaMatrice();
		if (valore==(dimensioni*dimensioni))
			return true;
		for(int k=0; k<8; k++)	{
			back.prossimoElemento(i,j,k,nuovo_elemento);
			if (!back.fuori(nuovo_elemento[0],nuovo_elemento[1]))
				if (back.esplora(back, nuovo_elemento[0],nuovo_elemento[1],valore+1))
					return true;
		}
		matrice[i][j]=0;
		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)	{
		
		if (k==0) {	nuovo[0]=i-2; nuovo[1]=j+1;   }
		if (k==1) {	nuovo[0]=i-1; nuovo[1]=j+2; }
		if (k==2) {	nuovo[0]=i+1; nuovo[1]=j+2; }
		if (k==3) {	nuovo[0]=i+2; nuovo[1]=j+1; }
		if (k==4) {	nuovo[0]=i+2; nuovo[1]=j-1;   }
		if (k==5) {	nuovo[0]=i+1; nuovo[1]=j-2; }
		if (k==6) {	nuovo[0]=i-1; nuovo[1]=j-2; }
		if (k==7) {	nuovo[0]=i-2; nuovo[1]=j-1; }
		
	}

	
	private void stampaMatrice()	{
		
		for(int i=0;i<dimensioni;i++)	{
			System.out.println(" ");
			for(int j=0;j<dimensioni;j++)	{
				if (matrice[i][j]<10)
					System.out.print(" ");
				System.out.print(matrice[i][j]+"  ");
			}
		}
		System.out.println(" ");
	}
    
}


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