main.java

puzzle program witch dfs bsf and a* algorithm

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package puzzle;

/** 
 *
 * @author Slayer86
 */

//import puzzle.Wezel;
//import puzzle.Drzewo;
import java.util.Random;
import java.io.BufferedReader;
import java.io.IOException;
//import java.io.InputStream;
import java.io.InputStreamReader;

//import java.util.ArrayList;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static boolean[] stanHash = new boolean[1324234];
    
    public static int hashF1(Wezel lisc)
    {
      int hash;
      hash = lisc.stan[0][0]*100000000+lisc.stan[0][1]*10000000;
      hash+= lisc.stan[0][2]*1000000+lisc.stan[1][0]*100000;
      hash+= lisc.stan[1][1]*10000+lisc.stan[1][2]*1000;
      hash+= lisc.stan[2][0]*100+lisc.stan[2][1]*10+lisc.stan[2][2];
      return hash;
    }
    
    public static void WypiszPuzzle(Wezel wezel)
    {
        for (int i = 0; i < 3; i++)        
        {
            for (int j = 0; j < 3; j++)
                System.out.print("[" + wezel.stan[i][j] + "]");
            System.out.print("\n");    
        }                
    }
    
    public static boolean Wygrana(Wezel wezel)
    {
        if (wezel.stan[0][0] == 1 &&
            wezel.stan[0][1] == 2 &&
            wezel.stan[0][2] == 3 &&
            wezel.stan[1][0] == 4 &&
            wezel.stan[1][1] == 5 &&
            wezel.stan[1][2] == 6 &&
            wezel.stan[2][0] == 7 &&
            wezel.stan[2][1] == 8 && wezel.stan[2][2] == 0)
            return true;
        else
            return false;
    }
    public static int licznik=0;
    public static int zero[][]=new int[3][3];
    public static int funOceniajaca1(Wezel temp)
    {
        int ocena=0;
        for (int i=0; i<3; i++)
            for (int j=0; j<3; j++)
                if (temp.stan[i][j]!=zero[i][j])
                    ocena++;
	return ocena;
    }
    public static int funOceniajaca2(Wezel temp)
    {
        int ocena=0;
        int w1=0,k1=0,w2=0,k2=0;
        for (int l=1; l<9; l++)
        {
            for (int i=0; i<3; i++)
                for (int j=0; j<3; j++)
                {
                    if (zero[i][j]==l)
                    {
                        w1=i;
                        k1=j;
                    }
                    if (temp.stan[i][j]==l)
                    {
                        w2=i;
                        k2=j;
                    }
                }
            if (w1!=w2) ocena+=Math.abs(w1-w2);
            if (k1!=k2) ocena+=Math.abs(k1-k2);
        }
        return ocena;
    }
    public static Wezel BudujDrzewo(Wezel wezel)
    {
        Drzewo tree=new Drzewo();
        int x0=0; 
        int y0=0;
        int hash=0;
        //boolean jest;
        tree.open.add(wezel);
        while(!tree.open.isEmpty())
        {
            Wezel lisc=tree.open.get(0);
            tree.open.remove(0);
            tree.closed.add(lisc);
            for (int i=0; i<3; i++)
                for (int j=0; j<3; j++)
                    if (lisc.stan[i][j] == 0)
                    {
                        x0 = i;
                        y0 = j;
                    }
            if (x0 - 1 >= 0) //gora
            {
                //jest=false;
                Wezel temp=new Wezel(lisc.stan);
                int pom = temp.stan[x0][y0];
                temp.stan[x0][y0] = temp.stan[x0 - 1][y0];
                temp.stan[x0 - 1][y0] = pom;
                
                //ustalenie hash-u
                hash = hashF1(temp);
                
                //sprawdzenie czy takiego sanu nie ma juz w drzewie, za pomoca tablicy hash-ow
                //1324234 oraz 1324213 losowe liczby przeciwdzalajace temu zeby 2 stany nie mialy tego samego hash-u
                if (stanHash[hash % 1324234] != true && stanHash[hash % 1324213] != true)
                {
                    stanHash[hash % 1324234] = true;
                    stanHash[hash % 1324213] = true;
                    temp.rodzic=lisc;
                    lisc.gora=temp;
                    tree.open.add(lisc.gora);
                    //wezel=lisc;
                    licznik+=1;
                }  
                
            }
            if (x0 + 1 <= 2) //dol
            {
                //jest=false;
                Wezel temp=new Wezel(lisc.stan);
                int pom = temp.stan[x0][y0];
                temp.stan[x0][y0] = temp.stan[x0 + 1][y0];
                temp.stan[x0 + 1][y0] = pom;
                
                 //ustalenie hash-u
                hash = hashF1(temp);
                
                //sprawdzenie czy takiego sanu nie ma juz w drzewie, za pomoca tablicy hash-ow
                //1324234 oraz 1324213 losowe liczby przeciwdzalajace temu zeby 2 stany nie mialy tego samego hash-u
                if (stanHash[hash % 1324234] != true && stanHash[hash % 1324213] != true)
                {
                    stanHash[hash % 1324234] = true;
                    stanHash[hash % 1324213] = true;
                    temp.rodzic=lisc;
                    lisc.dol=temp;
                    tree.open.add(lisc.dol);
                    //wezel=lisc;
                    licznik+=1;
                }  
               
            }
            if (y0 - 1 >= 0) //lewo
            {
                //jest=false;
                Wezel temp=new Wezel(lisc.stan);
                int pom = temp.stan[x0][y0];
                temp.stan[x0][y0] = temp.stan[x0][y0 - 1];
                temp.stan[x0][y0 - 1] = pom;
                
                 //ustalenie hash-u
                hash = hashF1(temp);
                
                //sprawdzenie czy takiego sanu nie ma juz w drzewie, za pomoca tablicy hash-ow
                //1324234 oraz 1324213 losowe liczby przeciwdzalajace temu zeby 2 stany nie mialy tego samego hash-u
                if (stanHash[hash % 1324234] != true && stanHash[hash % 1324213] != true)
                {
                    stanHash[hash % 1324234] = true;
                    stanHash[hash % 1324213] = true;
                    temp.rodzic=lisc;
                    lisc.lewo=temp;
                    tree.open.add(lisc.lewo);
                    //wezel=lisc;
                    licznik+=1;
                }  
               
            }
            if (y0 + 1 <=2) //prawo
            {
                //jest=false;
                Wezel temp=new Wezel(lisc.stan);
                int pom = temp.stan[x0][y0];
                temp.stan[x0][y0] = temp.stan[x0][y0 + 1];
                temp.stan[x0][y0 + 1] = pom;
                
                 //ustalenie hash-u
                hash = hashF1(temp);
                
                //sprawdzenie czy takiego sanu nie ma juz w drzewie, za pomoca tablicy hash-ow
                //1324234 oraz 1324213 losowe liczby przeciwdzalajace temu zeby 2 stany nie mialy tego samego hash-u
                if (stanHash[hash % 1324234] != true && stanHash[hash % 1324213] != true)
                {
                    stanHash[hash % 1324234] = true;
                    stanHash[hash % 1324213] = true;
                    temp.rodzic=lisc;
                    lisc.prawo=temp;
                    tree.open.add(lisc.prawo);
                    //wezel=lisc;
                    licznik+=1;
                }  
                
            }
        }
        return wezel;
    }
    
    public static Wezel metodaA(Wezel wezel, int funkcja)
    {
        Drzewo agwiazdka = new Drzewo();
         agwiazdka.open.add(wezel);
         Wezel wygrany=null;
         Wezel min=null;
         int indeks=0;
         while(!agwiazdka.open.isEmpty())
         {
            //wszerz.closed.add(wszerz.open.get(1));
            for( int i=0; i<agwiazdka.open.size(); i++ )
            {
                if(min == null) 
                {
                    min=agwiazdka.open.get(i); 
                    indeks=i;
		}
		if(min.ocena > agwiazdka.open.get(i).ocena) 
                {
                    min = agwiazdka.open.get(i);
                    indeks=i;
		}
            }
            agwiazdka.open.remove(indeks);
            Wezel temp=min;
            min = null;
            if (Wygrana(temp))
            {                
                wygrany = temp;
                break;
            }  
            if (temp.dol != null)
            {
                if (funkcja==1)
                    temp.dol.ocena=funOceniajaca1(temp.dol);
                else
                    temp.dol.ocena=funOceniajaca2(temp.dol);
                agwiazdka.open.add(temp.dol);
                agwiazdka.closed.add(temp.dol);